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

2 Answers 2

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

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.