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

I see, thanks.

Both Crypto.Util.number.inverse() and mpz_invert() work correctly if the
number to invert is larger than the modulus though, therefore I
understand that the check is actually redundant.

Note that I am not advocating to remove the check (if it's not broken
don't fix it). The problem I was considering is that a private key imported
as PEM could have p>q, because the standard does not prescribe any ordering.
Given that, should p and q be swapped (p to becomes q, q to become p) when p>q
or not?

I believe it is not necessary, but I had no hard proof that a flaw was
not lurking by doing that.

I would adjust the comment "# p shall be smaller than q (for calc of u)"
though because it is simply not right, along with the test cases that verify
that p<q....