1 of 1

Proof of correctness

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

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

for all coprime integers $(a,n)$ and $\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$ .

From the definition of the protocol, we have that

for some . Combining this with Euler's theorem, we see that we recover from the ciphertext

When the requirement does not hold, we can instead look at the equivalences modulo and respectively. Clearly, when we have that and our correctness still holds. Now, consider the case where we have that and Since we have already excluded the case that we can conclude that as is prime. This means that and by the multiplicative properties of the function, we determine that We conclude by invoking the Chinese Remainder theorem with

that The case for follows in a parallel manner.

Proof of correctness

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

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

for all coprime integers $(a,n)$ and $\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$ .

From the definition of the protocol, we have that

for some . Combining this with Euler's theorem, we see that we recover from the ciphertext

that The case for follows in a parallel manner.