[pycrypto] Why p<q in RSA code?
sbehrens at gmx.li
Wed Jan 19 09:35:27 CST 2011
On 1/19/2011 4:41 AM, Legrandin wrote:
> Hi all,
> I have noticed that - when generating an RSA key - a special check is
> made to ensure that p<q.
That's interesting. This is what I found, which seems to suggest the
To generate the primes p and q, generate a random number of bit length
b/2 where b is the required bit length of n; set the low bit (this
ensures the number is odd) and set the /two/ highest bits (this ensures
that the high bit of n is also set); check if prime (use the
Rabin-Miller test); if not, increment the number by two and check again
until you find a prime. This is p. Repeat for q starting with a random
integer of length b-b/2. If p<q, swap p and q (this only matters if you
intend using the CRT form of the private key). In the extremely unlikely
event that p = q, check your random number generator. Alternatively,
instead of incrementing by 2, just generate another random number each
There are stricter rules in ANSI X9.31
<http://www.di-mgt.com.au/rsa_alg.html#x931> to produce strong primes
and other restrictions on p and q to minimize the possibility of known
techniques being used against the algorithm. There is much argument
about this topic. It is probably better just to use a longer key length.
Taken from http://www.di-mgt.com.au/rsa_alg.html
That snippet suggests that p>q is desired if using the CRT form of the
private key. And we seem to be doing the exact opposite, swapping p and
q if p>q.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the pycrypto