Score:0

When using prime factorization for key gen, is there a limit on the size of the prime factors?

it flag

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?

user avatar
in flag
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.
Score:1
ng flag

"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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.