We now consider necessary for the successful description of an RSA ciphertext. The core of this result is due to Euler's theorem which states
for all coprime integers and is Euler's totient function.
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.