Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the original paper introducing RSA, it is implied that one should first choose $d$ and then calulate $e$ from $p$, $q$, and $d$. However, I have found in other places (such as the wikipedia article on RSA) that one should first calculate $e$, and only then calclulate $d$ from it.

Which of these two methods are preferred, and why?

share|improve this question
It appears that the wiki link has transposed, or reversed the meaning of $d$ and $e$. That is, the wiki link refers to $d$ as $e$ and vice-versa. – user476 Sep 25 '11 at 2:20
In general, I would trust this site for crypto more than wikipedia since things are vetted here pretty much immediately after they're written. – Fixee Sep 27 '11 at 5:05
up vote 10 down vote accepted

Well, as far as the mathematics of RSA are concerned, $d$ and $e$ are symmetric; they are related by the relationship:

$$ e·d \equiv 1 \pmod{\operatorname{lcm}(p-1, q-1)}$$

So, from the perspective of making it work, it doesn't matter which you choose first.

Now, it is not sufficient that the RSA encrypts and decrypts properly, it also has to be secure. From a security perspective, these values are not symmetric; $e$ (the encryption or verifying exponent) is public and $d$ (the decryption or signing exponent) is private. This means that $d$ must be a hard to guess value. On the other hand, we couldn't care less if someone could guess $e$; we're going to tell him that value anyways.

That means that if we choose $e$ (and then compute $d$), we can choose $e$ to be a small value. This has a real advantage; it makes the public operation (public key encryption, signature verification) go much faster, without any loss of security.

In contrast, if we choose $d$ and then compute $e$, we have to select a large value for $d$ (both so that it is not guessable, and to avoid subtler attacks that can factor $n$ given an $e$ that corresponds to a small $d$), and so we end up with $d$ and $e$ both being large. This slows down the operation without any corresponding advantage.

Because of this, common practice is to select a small $e$ (65537 is the most common value), select primes $p$ and $q$ such that $p\not\equiv 1 \pmod e$ and $q \not\equiv 1 \pmod e$ (so that $d$ exists), and then compute the corresponding $d$ value.

share|improve this answer
we'll $\mapsto$ we're $\:$ – Ricky Demer Jun 13 '13 at 5:15

When choosing $d$ first:

  • guarantees with probability 1 that $d$ is large enough to prevent various attacks
  • side-effect: guarantees with high probability that $e$ will be large, making encryption slow.

When choosing $e$ first:

  • can choose very small or pre-determined value of $e$ (e.g. 3 or $65537 = 2^{16}+1$). A small value speeds up encryption. A pre-determined value may be useful in some situations.
  • side-effect: when $e$ is small, this guarantees with high-probability that $d$ is large so various attacks still don't work.

Also note that the original paper was written in 1977, and since them many more developments have been made, so you should stick to the state-of-the-art (i.e. choosing $e$ first as a small number).

share|improve this answer

well I sort of came up with this method , I dont know whether most people already know this or not. For every example in my text book this method has worked

d= [ɸ(n) * (y)]+1 divided by e. here y = 1 , 2 ...

eg p=5 , q=11 e=3 n will be 56 and ɸ(n) = 40

 d= (40 * 1) +1 / 3

    =  41/3 
    = 13.66 --- but this is not an whole number 


 d= (40 *2 )+1 /3
   =  80+1/3
   = 81/3
    = 27.

so your d must be 27!! I hope this helped . good luck :)

share|improve this answer
How does this answer the question? Yes, we know that we can calculate $e$ from $d$ and $d$ from $e$ (and we know better ways to do it); which is preferred? BTW: in your example, $d=7$ works as well... – poncho Nov 20 '15 at 15:16

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.