1
$\begingroup$

In a lecture at my university, the following proof of correctness of RSA is given (the lecture is not mainly on cryptography or even computer science):

$m^{ed} \equiv m^{ee^{-1}} \equiv m^{1} \equiv m \ \textrm{mod} \ N$

The given reasoning is: $d$ is chosen as the multiplicative inverse of $e$ in the modulo ring $\mathbb{Z}_{\phi(N)}$, therefore this holds.

Surely, this cannot be a proof, considering that $e$ is only an inverse of $d$ in the modulo ring $\mathbb{Z}_{\phi(N)}$ and not in the integers or even $\mathbb{Z}_N$, right?

Am I mistaken or is this proof insufficient? The given proofs on wikipedia and other lectures are significantly longer and involve either Fermat's, Euler's or the Chinese Remainder Theorem.

$\endgroup$
2
  • 2
    $\begingroup$ Actually it's sufficient for $d$ to be the inverse of $e$ modulo $\lambda(N)$ (Carmichael's totient rather than Euler's) and in decent implementations written after maybe 1985 it usually is. In addition to Wikipedia, we have tens if not hundreds of As (already) covering that, though mostly on Qs that didn't know enough to ask it clearly if at all. $\endgroup$ Jul 29, 2023 at 0:28
  • $\begingroup$ In the lecture given, only euler's not carmichael's totient is used. The proof on wikipedia is considerably longer than this single equation. It seems to me that in order to show that it is valid to take the exponent modulo phi(n) precisely the proof given on wikipedia would be required. $\endgroup$
    – JMC
    Jul 29, 2023 at 0:38

1 Answer 1

3
$\begingroup$

You're right it is not sufficient, see this question and answer here for a considerably more complicated argument.

In practice $m$ for typical parameters with very large primes $m$ lies in the multiplicative group with overwhelming probability so the issue does not come up. But this is irrelevant to the correctness of the argument.

$\endgroup$
7
  • $\begingroup$ Why do the exponents lie in such a group of cardinality? The exponential function here is implied to be a regular exponential taking any integer as its exponent, and not elements of the modulo ring over phi(N). $\endgroup$
    – JMC
    Jul 28, 2023 at 23:26
  • $\begingroup$ It is a product modulo $N$ in the base which corresponds to multiplication and reduction modulo $\phi(N)$ in the exponent. $\endgroup$
    – kodlu
    Jul 28, 2023 at 23:29
  • $\begingroup$ Why is that? N is not prime, m is not neccessarily coprime to N, so why should there be anything special about $\phi(N)$ in the exponent? Is there any other source or literature that goes into this relationship between N in the base and phi(N) in the exponent? $\endgroup$
    – JMC
    Jul 28, 2023 at 23:31
  • $\begingroup$ I could totally understand this argument for gcd(m,N)=1, considering Euler's theorem, but that is not given. $\endgroup$
    – JMC
    Jul 28, 2023 at 23:37
  • $\begingroup$ @JMC; This question with a detailed answer may help. crypto.stackexchange.com/questions/1004/… $\endgroup$
    – kodlu
    Jul 29, 2023 at 0:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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