[pycrypto] Why p<q in RSA code?

[Legrandin]

> 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 [...] If p<q, swap
> p and q (this only matters if you intend using the CRT form of the private
> key) [...]
>>>
>
> 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.

Makes sense actually...

The rsaDecrypt() routine in _fastmath.c (and possibly soon in
_slowmath.py ;-)) uses pInv = p^{-1} mod q, that is the u member in a
pycrypto RSA object.
In other words, the page you mention and pycrypto are the same if you
swap p and q.

But still it does not explain *why* it must be p<q or p>q.

PKCS#1 states that qInv must be less than p (and in pycrypto it would
be pInv to be less than q), but that's fine. All other papers on the
net (including Handbook of Applied Cryptography) don't set any
constraint on the relative size of p with respect to q...

I have tried to remove the p/q swappings in pycrypto and the trivial
test cases that fail if p>q, and everything passes. Not that it proves
much (there may be probabilistic failures), but still...

On a separate note, LOL for the Nov 15 2010 comment in the page you
sent the link of.... :-D