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

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

3 Answers 3


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.

  • $\begingroup$ Thanks a lot.Maybe i care too much for p is bigger than q. $\endgroup$
    – taolinke
    Jul 11, 2014 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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Jan 29, 2015 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.