In RSA, do I calculate d from e or e from d?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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 

so

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

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