Take the 2-minute tour ×
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
1  
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

2 Answers 2

up vote 8 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 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

Your Answer

 
discard

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.