Score:1

Crypto

Is this proof of RSA's correctness sufficient?

JMC

7/28/24, 11:08 PM

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.

302

1 + 2

modular-arithmetic

dave_thompson_085

7/29/24, 12:28 AM

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.

JMC

7/29/24, 12:38 AM

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.

Score:3

Crypto

kodlu

7/28/24, 11:20 PM

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.

+ 7

JMC

7/28/24, 11:26 PM

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

kodlu

7/28/24, 11:29 PM

It is a product modulo $N$ in the base which corresponds to multiplication and reduction modulo $\phi(N)$ in the exponent.

JMC

7/28/24, 11:31 PM

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?

JMC

7/28/24, 11:37 PM

I could totally understand this argument for gcd(m,N)=1, considering Euler's theorem, but that is not given.

kodlu

7/29/24, 12:36 AM

@JMC; This question with a detailed answer may help. https://crypto.stackexchange.com/questions/1004/does-rsa-work-for-any-message-m/1006#1006

JMC

7/29/24, 12:42 AM

That's the usual proof I am familiar with. It is considerably more complex than this simple equation given in my OP. It seems to me that the equation in your answer would only be valid given this proof. But on its own, it doesn't seem sufficient to me. In the lecture I am referring to, no proof similar to the linked answer is ever given.

JMC

7/29/24, 1:54 AM

consider the case N=33, phi=20, 6^20 mod 33 = 12 != 6^0 It is not generally true that the exponent can be taken modulo phi, if gcd(m,N) != 1. However, it seems that it can be shown that for square-free N it holds that m^(phi+1) = m mod N which would allow the modulo in the exponent for all cases except when the exponent is congruent to 0, which is sufficient for this proof to hold, see https://math.stackexchange.com/questions/786526/a-phi-n-1-equiv-a-pmod-n-carmichael-generalization-of-fermat-e?noredirect=1&lq=1

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is this proof of RSA's correctness sufficient?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.