# RSA: Does it matter if you use e or d to encrypt?

In RSA: Suppose I have already chosen p,q and constructed phi(n).

Now my question is if it’s important whether I encrypt with e or with d? I don’t think so, e.g. because when encrypting I take plainoneofthe2numbers = cipher and then decrypting I take ciphertheotherofthe2numbers = plain, which is the same as taking plainoneofthe2numberstheotherofthe2numbers, which is the same as plainoneofthe2numbers * theotherofthe2numbers and since in multiplication both sides can be switched there doesn’t seem to be any possible difference whether e or d was “oneofthe2numbers”.

However our lecturer said that e is to encrypt and d is to encrypt (might have said so for pedagogical reasons), so now I’m unsure. In addition his slides say that when signing a message the roles are reversed. So that you encrypt/sign with d, but decrypt/verify with e. However if there really is no mathematical difference in their role in the decryption/encryption process this differentiation wouldn’t really be needed. (I realize that when signing “key-knowledge” is reversed, meaning the key to encrypt is secret, and the one used to decrypt is public, but my question only concerns the mathematical aspect.) Thanks for any answers

EDIT: It has been said now by both commenters that knowing d and n, with the secret key being a small e it would be possible to factor N. Can somebody explain how? Aside from brute-forcing phi(n) and then going from there? (Pls note that I never suggested using a small e as the private key, but was just interested in the mentioned hypothetical.)

• Usually the difference is that e is small and d is large. If d would be small and you knew e, you could factor the modulus.
– SEJPM
Jan 8 '18 at 17:22
• I don't understand. Can you explain further? If e was large and known, and d was small and unknown how could you factor the modolus? Do you just mean that you could brute-force the equation (e*d mod phi(n) = 1) by trying some d and and then a lot of numbers for phi(n) and see if the result is 1? Or something different with a more "elegant" mathemtical background? Jan 8 '18 at 17:30
• Wiener's attack efficiently factors $n$ if you know $e$ and $d$ such that $ed\equiv1\pmod{\varphi(n)}$ and $d<\frac13N^{1/4}$. This means the private exponent $d$ cannot be "small", whereas the public exponent $e$ typically is (for performance reasons). Jan 8 '18 at 18:31
• @ yyyyyyy Thanks a lot. That's what i was looking for. Jan 8 '18 at 18:45

Yes it matters if one uses $e$ or $d$ to encrypt. One must use for encryption whichever of $e$ or $d$ is published as part of the public key, and the other exponent must not be chosen small.

There is however no problem in choosing $d$ small (or large and random), publishing it, and computing $e$ from $d$ and the known factorization of the public modulus $N$; that will in all likelihood make $e$ large, for otherwise correct choice of $N$ and $d$; that is merely changing the letters used to name the exponents.

Update per comment: whatever $e$ or $d$ is chosen first, successfully computing the other exponent such that $ed\equiv1\pmod{\varphi(N)}$ insures that both $\gcd(e,\varphi(N))=1$ and $\gcd(d,\varphi(N))=1$. Thus if we choose large enough $N$ of known secret factorization, then $e$ large and random with $\gcd(e,\varphi(N))=1$, compute $d$, publish $(N,d)$, then it is fine to use $d$ to encrypt and $e$ to decrypt; we have only changed the letters used to name the exponents, and tested that the published $d$ verifies $\gcd(d,\varphi(N))=1$ in a slightly unusual way.

In RSA, a public key is made public, hence its name. Usually that is taken to be $(N,e)$. It is critical that encryption is with the exponent in that public key, because encryption must be public, and decryption private.

Also: as pointed by SEJPM's comment, $e$ is often chosen small ($e\le65537$ is typical); that makes $e$ is guessable; hence publishing $d$ and using it for decryption would allow anyone to decipher by guessing $e$ . As an aside, knowing $d$ and $N$, and that $e$ is small, it is possible to factor $N$ . Therefore, if in this comment "construct two new keys" is about reusing $N$ after $(N,e)$ or $(N,d)$ was published and the other exponent was small, published, or otherwise leaked, that's insecure.

Note: contrary to the question's statement, encryption of plaintext $M$ should not be as $M^e\bmod N$. One reason is that a guess of $M$ can be checked by anyone knowing $(N,e)$, that is by hypothesis any adversary; which can be a disaster e.g. when $M$ is a name on the public class roll. That's why we use RSA random encryption padding (e.g. RSAES-OAEP).

Final note: $p=3$, $q=5$ makes a much too small example for RSA: raising to the power $e$ or $d$ modulo $N=15$ has the exact same effect for all valid choices of $e$ and $d$, which all verify $e\equiv d\equiv1\pmod4$ or $e\equiv d\equiv3\pmod4$ ! In fact, until $p$ and $q$ have at least a few dozen decimal digits each, $N$ can be factored easily, thus there's no security, and size requirements on $e$ or $d$ are pointless.

• Is there a problem with choosing d to be small and using it to encrypt and choosing e to be large and using it to decrypt? Or is it just much easier calculatory to find an an number x for (e*x mod phi(n) = 1) when e is small, so that choosing e large is never really considered? (You wrote "As an aside, knowing d and N, and that e is not too big, it is possible to factor N." But is there a mathematical reason for that independent of the size of the conventional size of e and d?) Jan 8 '18 at 17:43
• Concerning your first two paragraphs: I think (although not sure) that I understand this. My question concerns only if I construct two new keys etc., not if one is already published of course. Concerning the "the other exponent must not be chosen small"-part see my comment above. (Basically, if i choose d to be small and to encrypt and e to be large and to decrypt, is it then still problematic?) Jan 8 '18 at 17:48
• "There is however no problem in choosing d small (or large and random), publishing it, and computing e from d and the known factorization of the public modulus N; that will in all likelihood make e large, for otherwise correct choice of N and d; that is merely changing the letters used to name the exponents." Well, but e would still have to fulfill (gcd(e, phi(n) =1), while both together would have to fulfill (e*d mod phi(n) = 1), right? So you would change which to use to encrypt/decrypt and some "conventional properties" but the basic mathematical requirements would be the same, or not? Jan 8 '18 at 17:55
• "Therefore, if in this comment "construct two new keys" is about reusing N after (N,e) or (N,d) was published and the other exponent was small, published, or otherwise leaked, that's insecure." No, you seem to be very concerned about a potential security "disaster". Rest assured, i'm just a confused first term CS-student and didn't publish any secret keys or similar. What I meant by constructing two new keys was that I was trying to mathematically construct 2 new keys. I had already choosen p, q and then constructed n and phi(n). Just as an hypothetical, let's say i choose them with the (1/2) Jan 8 '18 at 18:08
• following values: p = 3, q = 5, n = 15, phi(n) = 8 (I realize that’s not secure, just as an thought experiment). Now I need to decide on an e and a d, and this time I want d to be small and to be used to encrypt and e to be large and to be used to encrypt. That’s basically what I meant. (2/2) Jan 8 '18 at 18:08