Proof of correctness

We now consider cd=med=mc^d = m^{ed} = mnecessary for the successful description of an RSA ciphertext. The core of this result is due to Euler's theorem which states

aϕ(n)1modna^{\phi(n)} \equiv 1 \mod n

for all coprime integers (a,n)(a,n) and ϕ(n)\phi(n) is Euler's totient function.

As a reminder, we say two integers are coprime if they share no non-trivial factors. This is the same statement that gcd(a,n)=1\gcd(a,n)=1.

From the definition of the protocol, we have that

ed1modϕ(n),ed=1+kϕ(n)ed \equiv 1 \mod \phi(n), \;\; \Rightarrow \;\; ed = 1 + k\phi(n)

for some kZk \in \mathbb{Z}. Combining this with Euler's theorem, we see that we recover mmfrom the ciphertext

When the requirement gcd(m,n)=1\gcd(m, n) = 1does not hold, we can instead look at the equivalences modulo ppand qqrespectively. Clearly, when gcd(m,n)=n,\gcd(m, n) = n,we have that cm0modnc \equiv m \equiv 0 \mod nand our correctness still holds. Now, consider the case m=kp,m = k\cdot p,where we have that cm0modpc \equiv m \equiv 0 \mod pand cd(me)d(modq).c^d \equiv (m^e)^d \pmod q.Since we have already excluded the case that gcd(m,q)=q,\gcd(m, q) = q,we can conclude that gcd(m,q)=1,\gcd(m, q) = 1,as qqis prime. This means that mϕ(q)1modqm^{\ell\phi(q)} \equiv 1 \mod qand by the multiplicative properties of the ϕ\phifunction, we determine that mnϕ(n)=mϕ(q)1modq.m^{\ell_n\phi(n)} = m^{\ell\phi(q)} \equiv 1 \mod q.We conclude by invoking the Chinese Remainder theorem with

that medmmodn.m^{e\cdot d} \equiv m \mod n.The case for m=kqm = k\cdot qfollows in a parallel manner.