• 

Suppose Alice wants her friends to encrypt email messages before sending them to her. Computers represent text as long numbers (01 for "A", 02 for "B" and so on), so an email message is just a very big number. The RSA Encryption Scheme is often used to encrypt and then decrypt electronic communications. General Alice's Setup: Chooses two prime numbers. Calculates the product n = pq. Calculates m = (p-1)(g-1). Chooses numbers e and d so that ed has a remainder of 1 when divided by m. Publishes her public key (n. e). Bob encrypts a message M for Alice: Example Alice's Setup: p= 11 and q = 3. n = pq = 11 x 3 = 33. m=(p-1)(g- 1) = 10 x 2 = 20. = If e 3 and d= 7, then ed = 21 has a remainder of 1 when divided by m = 20. Publish (n, e) = (33,3). Bob encrypts message M = 14: Uses her private key (n. d). Finds remainder R when Cd is divided by n. R matches the message M that Bob wanted. to send to Alice! . Finds Alice's public key (n, e). Finds the remainder C when Me is divided by n. Sends ciphertext C to Alice. Sends ciphertext C = 5 to Alice. Alice receives and decrypts ciphertext C: Alice decrypts ciphertext C = 5: (n, e) = (33,3). When 14 mainder is C = 5. 2744 is divided by 33, the re- (n, d) = (33,7). . When 57 = 78125 is divided by 33, the re- mainder is R = 14. R = 14 = M, the original message from Bob! Questions 1. Callie wants to send the message M 13 to Alice. Using Alice's public and private keys, calculate the ciphertext C, and the value for R when Alice recovers the message. = 2. Dexter wants to set up his own public and private keys. He chooses p = 23 and q = 19 with e = 283. Find d so that ed has a remainder of 1 when divided by (p-1)(q 1).