10. (RSA Public Key Cryptosystem) Let us pick two prime numbers p = 41,q = 67....

 

Transcribed Image Text:

10. (RSA Public Key Cryptosystem) Let us pick two prime numbers p = 41,q = 67. Then, n pq 41 67 = 2747 (n) (p 1)(q-1) = 40 66 = 2640 We pick a small prime numbers, with gcd (s, (n)) = 1. s = 13. Then, t=s mod (n) = 13 mod 2640 = 2437. (This inverse is computed by Euclid's algorithm.) The public keys are (s, n) and the private key (t,n). (a) Suppose a sender wants to send a number x = 2169. Compute the encrypted message y. Make sure you perform a mod operation after each multiplication so the intermediate results does not become too large. Use the recursive algorithm Power to compute the exponentiation. (You may use an Excel sheet to generate the data.) Show the computation. (b) Compute the decrypted message z and verify that z = x. Show the computation. 10. (RSA Public Key Cryptosystem) Let us pick two prime numbers p = 41,q = 67. Then, n pq 41 67 = 2747 (n) (p 1)(q-1) = 40 66 = 2640 We pick a small prime numbers, with gcd (s, (n)) = 1. s = 13. Then, t=s mod (n) = 13 mod 2640 = 2437. (This inverse is computed by Euclid's algorithm.) The public keys are (s, n) and the private key (t,n). (a) Suppose a sender wants to send a number x = 2169. Compute the encrypted message y. Make sure you perform a mod operation after each multiplication so the intermediate results does not become too large. Use the recursive algorithm Power to compute the exponentiation. (You may use an Excel sheet to generate the data.) Show the computation. (b) Compute the decrypted message z and verify that z = x. Show the computation.