[pycrypto] Why p<q in RSA code?
Paul Koning
paul_koning at dell.com
Wed Jan 19 13:00:38 CST 2011
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
More information about the pycrypto
mailing list