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

-