In RSA, why does $p$ have to be bigger than $q$ where $n=p \times q$?

In openSSL – during RSA key generation – if $q$ is bigger than $p$, they exchange them. Why is that?

-
You do realize that since $p \ne q$, one must be greater than the other, right? –  Thomas Jul 11 '14 at 4:03
so that means there is no such restrictions like m can not greater than n,because the well known reason. –  taolinke Jul 11 '14 at 5:54

There's no real difference between $p$ and $q$ in RSA. It looks like OpenSSL just has the agreement "$p$ has to be bigger than $q$" for conveniences. One of the numbers has to be bigger than the other (otherwise they would be the same number, and $p = q$ is very bad in RSA).

Just use two examples: $p = 13$ and $q = 11$. $p$ is bigger than $q$, all right. What about $p = 11$ and $q = 13$? In RSA, there is no difference between the two prime numbers, so you can exchange them at will. Both are the same prime pair for RSA, even when the two numbers for $p$ in the examples are different, and "the same prime pair" means in praxis the same key.

-
Thanks a lot.Maybe i care too much for p is bigger than q. –  taolinke Jul 11 '14 at 5:56

I do not know why the OpenSSL implementation specifically does this.

However, a branch-less (constant time) implementation of the RSA private key operation, might be slightly more efficient if the parameter $c = q^{-1} \bmod p$ is calculated for $p$ being the greatest prime of the two. Otherwise the value of $J_q = I^{d \bmod q-1} \bmod q$ has to be taken $\bmod p$ prior to combining it with $J_p = I^{d \bmod p-1} \bmod p$ using a CRT formula.

The problem that is most likely to be solved using the check, is that $H = c(J_p-J_q) \bmod p$ might be negative "in more ways" if $p \lt q$ and checking for that in a branch-less way, rather than ensuring that $J_p+p \ge J_q$, is not efficient.

Also note that checking that $p \gt q$ at key generation time, is not sufficient, should this be the reason for the check. If the private key is generated using partly compatible software, there is no guarantee that $p \gt q$ unless it is explicitly checked when the private key is loaded as well.

Branch-less implementations are cryptographically important since they prevent timing attacks.

-

It comes from the (somehow abusive) software simplifications when computing the CRT.

Here is the simplified code (as in pkcs#1 v2.1)

m1 = (c^dP) % p
m2 = (c^dQ) % q
h = (q_inv*(m1 - m2)) % p
m = m2 + h*q


Agggh, Outch. when m2 > m1, we enter the realm of negative numbers unfriendly to unsigned crypto libraries.

Then many authors suggested this modifications

h = (q_inv*(p + m1 - m2)) % p


e.g. (Cryptographic Hardware and Embedded Systems -- CHES 2003: Volume 5 edited by Colin D. Walter, Çetin K. Koç, Christof Paar)

In fact, it still has a corner case when q > p, because m2 could still be larger than p + m1. I.e. you have this inequality p < p+m1 < m2 < q, which tend to be rare when p and q are more or less the same size (e.g. when their 2 msb are set like in openssl). It is not easy to generate such test vector if you do not know the private key p and q.

However, this implementation is considered friendly for small embedded devices with limited computations capabilities , or limited software size .... To make that modified code safe, you need to add the constraint p > q .

Note that on small embedded devices, you may trigger another bug when the modular reduction implementation requires that a product must be less than m^2 (in order to require only one subtraction at the end of a montgomery reduction), because the modified product is clearly larger than p^2.

I corrected it recently in http://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Using_the_Chinese_remainder_algorithm where the constraint p > q is not mentioned, you have to add multiple times p

If your biginteger package handles properly negative numbers (like gmp) none of this is relevant.

-
The question was based on behavior seen within OpenSSL; the OpenSSL bignum library handles negative numbers properly, and hence this answer is irrelevant in the context of the original question. –  poncho Jan 29 at 2:20