- Question 2 Let N Pq For Two Different Primes P And Q This Exercise Shows That We Can Use The Rsa Even If Gcd M N 1 (81.24 KiB) Viewed 42 times
Question 2: Let n = pq for two different primes p and q. This exercise shows that we can use the RSA even if gcd(M, n) ‡ 1 (M is a message). = 1. Let j be a multiple of Þ(n). Show that for M such that gcd(M, n) ‡ 1, M³+¹ M mod p and Mi+¹ M mod q = 2. Let e and d be the be the encryption and decryption for RSA modulo n. Show that Med M mod n for any M. - 3. Explain why this means that we can use the RSA also if gcd(M, n) ‡ 1. 4. Explain why is gcd(M, n) = 1 highly likely for a large n = p.q.