[pycrypto] Why p<q in RSA code?

[Thorsten Behrens]

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 
exact opposite:

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

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...
URL: http://lists.dlitz.net/pipermail/pycrypto/attachments/20110119/a39e32b8/attachment.html