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.

While studying the RSA algorithm I referred to some books and some sites such as RSA (wikipedia) and all of them chose {d,n} as the secret (private) key and release {e,n} as the public key but as d and e are multiplicative inverse of each other, can't we keep {e,n} as private key and use the other as public key? Is it a standard rule to choose the {d,n} as the private key?

share|improve this question

migrated from security.stackexchange.com May 27 '13 at 12:21

This question came from our site for Information security professionals.

2 Answers 2

up vote 7 down vote accepted

The letters d and e are just a notation -- what matters is that there are two exponents, each undoing what the other does, and making one public does not intrinsically reveal the other. By tradition, the one made public is called e.

However, there is a twist: the exponent that is not made public, i.e. the private key, can be really private only if it is sufficiently big. If the private exponent is very small (e.g. it fits on 20 bits), then it is easy to rebuild it from the public key, if only by trying all possibilities. If the private exponent is not so small but still substantially smaller than the modulus n, more advanced attacks are possible, to the same effect (there is an attack by Coppersmith which works as long as the private exponent length is no more than 29% of the length of n).

Conversely, there is no issue in the public exponent being small. That exponent can be as small as the value 3, although, there again by tradition (and also out of a solid dose of historical confusion), 65537 is often used as public exponent. Small exponents promote faster computations. Since the public exponent can be small, we thus make them very small.

So if you generate your key pair and choose both exponents as big numbers (more or less the same size as n), then you can choose either one to be the public exponent (which will be thereafter called e). However, if you selected one of the exponents to be small, then the small exponent shall be the public one, because otherwise your key would be very weak and prone to cracking.

Some widespread implementations of RSA don't tolerate big public exponents; e.g. the one in Windows CryptoAPI, used by Internet Explorer when doing SSL, requires the public exponent to fit on 32 bits.

share|improve this answer
1  
It is important to ensure that the greatest common divisor between (p-1)(q-1) and e is equal to 1, however. You cannot simply choose 65537 to be the public exponent unless you are checking this condition. –  Brendon May 27 '13 at 11:27
    
@Brendon 65537 is prime so that condition is just doing a modulo of (p-1)%65537 and (q-1)%65537 if either is equal to 0 then you need to choose a different p or q (depending on which was 0) –  ratchet freak May 27 '13 at 11:50
    
@Brendon: it normally goes the other way round. e is chosen first, then p and q are selected such that p-1 and q-1 are both coprime to e. That's how many (most ?) RSA key generation engines work. –  Thomas Pornin May 27 '13 at 21:09

There's nothing special about e -- it's simply a number you select so that e and (p-1)(q-1) are coprime. In general, e will be a small prime, e.g. 7 or 65537 (as per Wikipedia page). d is the multiplication inverse of e modulo (p-1)(q-1). This does not mean that d is simply equal to 1/e -- it is very difficult to obtain d from e unless you also have (p-1)(q-1).

In essence, e is just a degree of freedom in the algorithm -- the reason for the flexibility is because e and (p-1)(q-1) will need to be coprime, which may not hold for every choice of e. So the public key is really just n and the decryption key is just {d,n}.

Just to use some numbers, suppose we chose the primes:

  • p = 67706614564338235002765566951242539340333032205026461307043629937913994975109
  • q = 90947554097423668858730894787242356004957551116627660855305597239344082875989

Then N=p*q=6157750990843564899040526104103265719297860652172632823400065455699068450255812459659898039342299176739625908677540037844125877114187853026418999188757801

Taking e=29 ensures that gcd((p-1)(q-1), e) = 1. We can use Euclid's algorithm to determine

  • d=2972707374889996847812667774394680002419656866566098604400031599302998562192384595754389927039245776685876687343128498677629624892701967351358081915610133.

Just looking at the length of d compard to e, I hope, is enough to convince you why keeping d secret is the important.

For encryption, the calculation is M^e mod N, where M is your plaintext message. For decryption, it is E^d mod N, where E is your encrypted message.

share|improve this answer
    
yes, you are right but what if both are equivalent in length? –  Chirayu Chiripal May 27 '13 at 11:41
    
If the public exponent is selected uniformly from $\mathbb Z_{\phi((p-1)(q-1))}^*$, it doesn't matter which exponent you call $e$ and which you call $d$, just as long you keep the private one consistently private. –  Henrick Hellström May 28 '13 at 9:52

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.