Recitation 7 3 But does it really work? A critical question is whether decrypting an encrypted message always gives back the original message! Mathematically, this amounts to asking whether md=m (mod pq) Note that the procedure ensures that de=1+k(p-1)(q-1) for some integer k This congruence holds for all messages m. First, use Fermat's theorem to prove that m=me(mod p)for all m(Fermat's Theorem says that ak mod p) if p is a prime that does not divide a Solution. If m is a multiple of p, then the claim holds because both sides are con gruent to 0 mod p. Otherwise, suppose that m is not a multiple of p. Then m1+k(p-1(q-1)=m (mod p m(mod p) The second step uses Fermat's theorem, which says that mP-=1(mod p) provided m is not a multiple of p By the same argument, you can equally well show that m med(mod q). Show that these two facts together imply that m= med (mod pq)for all m Solution We know that p|( Thus, both p and q appear in the prime factorization of m - med. Therefore, pq I n- n ana so m=m(mod pq)Recitation 7 3 3 But does it really work? A critical question is whether decrypting an encrypted message always gives back the original message! Mathematically, this amounts to asking whether: m de ≡ m (mod pq). Note that the procedure ensures that de = 1 + k(p − 1)(q − 1) for some integer k. • This congruence holds for all messages m. First, use Fermat’s theorem to prove that m ≡ mde (mod p) for all m. (Fermat’s Theorem says that ap−1 ≡ 1 (mod p) if p is a prime that does not divide a.) Solution. If m is a multiple of p, then the claim holds because both sides are con￾gruent to 0 mod p. Otherwise, suppose that m is not a multiple of p. Then: 1+k(p−1)(q−1) ≡ m · (mp−1 ) k(q−1) m (mod p) ≡ · 1 m k(q−1) (mod p) ≡ m (mod p) The second step uses Fermat’s theorem, which says that mp−1 ≡ 1 (mod p) provided m is not a multiple of p. • By the same argument, you can equally well show that m ≡ med (mod q). Show that these two facts together imply that m ≡ med (mod pq) for all m. Solution. We know that: p | (m − m ed), q | (m − m ed). Thus, both p and q appear in the prime factorization of m − med . Therefore, pq | (m − med), and so: m ed ≡ m (mod pq)