RSA - bitlength of p and q

Question

I'm just trying to understand the key generation part of RSA, and more specifically, selecting the p and q primes. Given a target bit length for the modulus, n, what range I should be generating p and q in?

The modulus, n, is the product of p and q, where p and q are both prime numbers. I've read that p and q should be relatively close to each other, and somewhere around sqrt(n). If the target bit length is, for example, 32 bits (very small I realise), then does that follow that p and q should be a random prime of a maximum 16 bits?

Thanks for any clarification

Rob

Answer 1

For a 32-bit modulus the question is a bit academic: your primary aim in choosing p and q is to make the product hard to factorize, but finding the prime factorisation of a number smaller than 2^32 is so easy that there's little point worrying about the sizes of p and q in this case. Note that the mathematics will work just fine so long as p and q are distinct primes.

For something more realistic, like a 1024-bit modulus, then yes, you're pretty safe choosing two 512-bit primes p and q at random: that is, choose p and q uniformly from the set of all primes in the range [2^511, 2^512]. There's a notion of 'strong primes', which are primes designed to avoid particular possible known attacks---for example, you'll see recommendations that p and q should be chosen so that p-1 and q-1 have large factors, to guard against easy factorizations using Pollard's 'p-1' algorithm. However, these recommendations don't really apply to large moduli and state-of-the-art factorization algorithms (GNFS, ECM). There are other possible cases that in theory could give an easy factorization, but they're so unlikely to turn up in practice from random choices of p and q that they're not worth worrying about.

Summary: just choose two random primes with equal bitlength, and you're done.

A couple of additional comments and things to think about:

1. Of course, if you do choose two 512-bit primes, you'll end up with either a 1023-bit or a 1024-bit modulus; that's probably not worth worrying about, but if you really cared about getting exactly a 1024-bit modulus you could either restrict the range of p and q further, say to [1.5 * 2^511, 2^512], or just throw out any 1023-bit modulus and try again.

2. Don't deliberately choose p and q so that they're near each other: if p and q are truly close to each other (e.g., less than 10^10 apart, say), then their product pq is easily factorized by Fermat's method. But if you're choosing random primes p and q in the range [2^511, 2^512], this isn't going to happen with any sort of realistic probability.

3. When choosing a prime at random, a tempting strategy is to pick a random (odd) integer in the range [2^511, 2^512] and then increment it until you find the first prime. But note that that does not give a uniform choice amongst all primes: primes occurring after a large gap would be more likely to come up than other primes. A better strategy is just to keep picking random odd numbers and keep the first one that's a prime (or more likely, a strong probable prime to so many randomly-chosen bases that you can be sure in practice that it's prime).

4. Make sure you've got a really good cryptographic source of random numbers on hand for your prime number generation.