[pycrypto] Why p<q in RSA code?

[Paul Koning]

On Jan 19, 2011, at 1:29 PM, Legrandin wrote:

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

If you do modular arithmetic mod q on p -- which is what is being done here -- you'd want to start with p having a legal value mod q.  Such a value is in the range 0..q-1, so that's why you'd have the check.

p^-1 mod q will deliver a value in that range.  You could argue that it should be valid even if p is outside the range -- effectively that means you're doing (p mod q)^-1 mod q.  But I would expect your typical modular arithmetic package not to go through that extra work.

	paul