1
$\begingroup$

In this thread Henrick Hellström says that when $ed \equiv 1\ (mod\ \phi(n))$ then $(m^e)^d \equiv m\ (mod\ n)$. So I thought this is how Euler's theorem is related to RSA. But at least I thought that due to Euler's theorem the prerequisite for $(m^e)^d \equiv m\ (mod\ n)$ was $ed \equiv 1\ (mod\ \phi(n))$, until I read the comments of the answer and @poncho says that

Minor nit: it's not true that e,d must meet (satisfy) the equation $ed \equiv 1\ (mod\ \phi(n))$. One counterexample is $n=133, e=5, d=11$. That has $ed \equiv 55\ (mod\ \phi(n)=108)$, however $(m^e)^d \equiv m\ (mod\ n)$ for all m. This is a minor point, however we should avoid telling beginners things which aren't true.

So $ed \equiv 1\ (mod\ \phi(n))$ doesn't need to be true in order for $(m^e)^d \equiv m\ (mod\ n)$ to work. At this point I am really confused about the relation between Euler's theorem and RSA, and why we need $gcd(e,d)=1$.

EDIT: Also this website says that $(m^e)^d \equiv m^{\phi(n)}\ (mod\ n)$. How could this be true? Wouldn't this imply that $ed =\phi(n)$?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ If you don't know what your question is, well, it's really hard to answer. BTW: did you mean $\gcd(e, d) = 1$? That doesn't need to be true, and I can't think of anyone claiming that it is. Did you mean $\gcd(m, n) = 1$ (which also doesn't need to be true, but might be implied if you use Euler's theorem as your proof) $\endgroup$ – poncho Feb 1 '19 at 21:22
  • $\begingroup$ @poncho Oh poncho thank you for showing up! I just don't understand your comment. You showed that ed≡1 (mod ϕ(n)) doesn't need to be true for (me)d≡mϕ(n) (mod n) to work. I thought that Euler's theorem basically proved that, for (me)d≡mϕ(n) (mod n) to work, ed≡1 (mod ϕ(n)) must be true. If that is not the case: 1. Why does (me)d≡mϕ(n) (mod n) work? 2. How is Euler's theorem related to this? $\endgroup$ – Uzi Feb 1 '19 at 21:36
3
$\begingroup$

I thought that Euler's theorem basically proved that, for $(m^e)^d \equiv m \pmod n$ to work, $ed \equiv 1 \pmod {\phi(n)}$ must be true

No; a direct application of Euler's theorem shows that if $ed \equiv 1 \pmod {\phi(n)}$ is true (and $\gcd(m,n)=1$, Euler's theorem needs that as well), then we always have $(m^e)^d \equiv m \pmod n$

However, it does not imply the converse (and in fact, the converse is not true).

A stronger statement would be (assuming $n = pq$ for distinct primes $p, q$) that if $ed \equiv 1 \pmod{ p - 1}$ and $ed \equiv 1 \pmod{ q - 1}$, then we have $(m^e)^d \equiv m \pmod n$ for all $m$.

And, in this case, the converse is true; if we have $(m^e)^d \equiv m \pmod n$ for all $m$, then we necessarily have $ed \equiv 1 \pmod{ p - 1}$ and $ed \equiv 1 \pmod{ q - 1}$. In fact, if we have either $ed \not\equiv 1 \pmod{ p - 1}$ or $ed \not\equiv 1 \pmod{ q - 1}$, then we'll necessarily have $(m^e)^d \not\equiv m \pmod n$ for at least 1/3 of the possible $m$ values.

Another (perhaps more common) way of writing these two equivalences is to express it as $ed \equiv 1 \pmod{ \lambda(n) }$ for the function $\lambda(n) = \text{lcm}(p-1, q-1)$.

How does these stronger statements relate to your original relation? Well, if we have $ed \equiv 1 \pmod{\phi(n)}$, then we necessarily have $ed \equiv 1 \pmod{\lambda(n)}$ (and hence RSA "works")

Improve this answer
$\endgroup$
  • $\begingroup$ So by setting ed≡1(modϕ(n) and gcd(m,n)=1 as true we are basically guaranteeing that (m^e)^d≡m(mod n) is also true. But these are not the only conditions where (m^e)^d≡m(mod n) is true, but with these conditions it is guaranteed that this is true (hence the decryption will work). Did I understand this correctly? And is your stronger statement utilised in RSA or the first one? Because from what you wrote, I understand that RSA works because if ed≡1(modϕ(n)) is true, then ed≡1(modλ(n)) is true as well? I thought Carmichael's function is just an interchangable function with the totient function $\endgroup$ – Uzi Feb 2 '19 at 8:31
  • 2
    $\begingroup$ "And is your stronger statement utilised in RSA or the first one?"; well, real RSA implementations typically use $d = e^{-1} \bmod{ \lambda(n) }$, and so I believe the answer would be "typically the stronger statement". "I understand that RSA works because if $ed \equiv 1 \pmod{\phi(n)}$, then $ed \equiv 1 \pmod{\lambda(n)}$ as well"; yes, that's why the first formulation guarantees correctness. "I thought Carmichael's function is just an interchangable function with the totient function"; obviously not, as those two functions return different values when passed a composite. $\endgroup$ – poncho Feb 2 '19 at 14:40
  • $\begingroup$ Sorry to bother you again but I am not sure if I am understanding this correctly. (m^e)^d≡m(mod n) works because ed≡1(modλ(n)) is true? And this works because of Euler's Theorem? $\endgroup$ – Uzi Feb 2 '19 at 17:11
  • $\begingroup$ @Uzi: while it is true that (for squarefree $n$), $(m^e)^d \equiv m \pmod n$ holds for all $m$ exactly when $ed \equiv 1 \pmod{\lambda(n)}$, however we can't really say "because", as there really isn't any causality in math; one equation being true doesn't really cause other expression to be true; both are true or both are not. Similarly, while we might be able to show this using Euler's theorem (although it would not be straightforward), there really isn't any causality... $\endgroup$ – poncho Feb 2 '19 at 17:26
  • 2
    $\begingroup$ @Uzi: that is correct; however a straight-forward application of Euler's theorem doesn't directly prove that; it shows the weaker relation I originally mentioned. $\endgroup$ – poncho Feb 2 '19 at 18:03

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.