Question

Suppose we already proved the correctness of the RSA algorithm under the assumption that gcd(m, n) = 1. Prove the correctness of the RSA algorithm without this assumption, that is, m^de ≡ m (mod n) for all 1 ≤ m < n. (Hint: use the Chinese remainder theorem.)

Answer 1

Correctness of RSA :(M^e)^d ≡ M (mod n).
Proof:---
By the definition of d, we know that de ≡ 1 [mod (p−1)(q−1)].

• Thus by the definition of modular congruence,
  ∃k: de = 1 + k(p−1)(q−1).
• So, the result of decryption is
  C^d ≡ (M^e)^d = M^de = M^1+k(p−1)(q−1) (mod n)

Assuming that M is not divisible by either p or q,

• Which is nearly always the case when p and q are very large,
• Fermat’s Little Theorem tells us that M^p−1 ≡ 1 (mod p) and M^q−1 ≡ 1 (mod q)

Thus, we have that the following two congruences hold:

• First: C^d ≡ M·(M^p−1)^k(q−1) ≡ M·1^k(q−1) ≡ M (mod p)
• Second: C^d ≡ M·(M^q−1)^k(p−1) ≡ M·1^k(p−1) ≡ M (mod q)

And since gcd(p,q)=1, we can use the Chinese Remainder
Theorem to show that therefore C^d ≡ M (mod pq):

• If C^d ≡ M (mod pq) then ∃s: C^d=spq+M, so C^d≡M (mod p) and (mod q). Thus M is a solution to these two congruences, so (by Chinese Remainder Theorem) it’s the only solution.