0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – SEJPM Jan 8 '18 at 17:22
  • $\begingroup$ 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? $\endgroup$ – someonesomewhere Jan 8 '18 at 17:30
  • 1
    $\begingroup$ 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). $\endgroup$ – yyyyyyy Jan 8 '18 at 18:31
  • $\begingroup$ @ yyyyyyy Thanks a lot. That's what i was looking for. $\endgroup$ – someonesomewhere Jan 8 '18 at 18:45
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – someonesomewhere Jan 8 '18 at 17:43
  • $\begingroup$ 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?) $\endgroup$ – someonesomewhere Jan 8 '18 at 17:48
  • $\begingroup$ "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? $\endgroup$ – someonesomewhere Jan 8 '18 at 17:55
  • $\begingroup$ "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) $\endgroup$ – someonesomewhere Jan 8 '18 at 18:08
  • $\begingroup$ 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) $\endgroup$ – someonesomewhere Jan 8 '18 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.