0
$\begingroup$

If there is a limit, does that leave a limited number of prime numbers that can be used for key gen? And, if that is the case is the encryption system vulnerable?

$\endgroup$
1
  • $\begingroup$ Yes, if you can enumerate every 16kb (or whatever arbitrary bit size) large composite number's prime factors, then you can break 16kb RSA and similar cryptosystems that rely on the difficulty of prime factorization. Those are pretty huge numbers by the way. $\endgroup$
    – user
    Jul 9, 2021 at 18:59

1 Answer 1

1
$\begingroup$

"Prime factorization" is not worth interest, for primes are their own factorization.

Factorization into primes is not used for key generation.

I conclude the question asks:

When generating primes during generation of public/private key pairs for crytosystems based on hardness of factorization (RSA, Rabin, Pailler…), is there a limit on the size of the prime factors? If so, does that leave a limited number of prime numbers that can be used for key gen? And, if so, does that leave the encryption system vulnerable?

Mathematically, there is no upper limit on the size of the prime factors. There are infinitely many primes, and (thus) primes over any size.

Some standards put a limit. For example FIPS 186-4 has an upper limits of $1536$ bit; more precisely, for this size, each of the two primes that form the composite modulus must be in the interval $[2^{1535.5},2^{1536}]$, so that the product is $3072$-bit. By the prime number theorem, there are about about $2^{1524}$ primes in this interval. That's about $600\underbrace{\text{ million }\ldots\text{ million }}_{76\text{ times the word million}}$. That's limited, but so large that it does not make the system vulnerable for any practical purpose.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.