Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
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

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
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.

share|improve this answer

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

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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