number 6 please
Homework 3 (Math 415) due November 9, 2020 (1) The ciphertext 5859 was obtained from RSA using n = 11413 = 101 x 113 and e = 7467. Recover the plaintext. (Use a calculator.) (2) The ciphertext 75 was obtained using RSA with n = 437 and e = 3. You know the plaintext is either8 or 9. Determine which one without factoring n. (3) Naive Nelson uses RSA to receive a single ciphertext c, corresponding to the message m. Everyone knows the modulus n and the encryption key e. Since he feels guilty that he only used his system once, he offers to decrypt any ciphertext anyone sends him, as long as it's not c, and return the answer to the person. Evil Eve sends him 2c mod n. Show how this allows Eve to find m. (4) What is wrong with using e=1 in RSA? What is wrong with using e = 2? (5) You know that 5161072 = 7 (mod 642401) and 1877222 = 28 (mod 642401). Use this information (and a calculator) to factor 642401. (6) Suppose you are given two large primes p and q. How can you (using the Chinese Remainder Theorem) find an integer such that r = 49 (mod pq) but I +7 (mod pq)? (7) Suppose n is a large odd number, and you calculate that 2(n-1)/2 = k (mod n), where k#+1 (mod n). (a) Explain why, if k? #1 (mod n), then you know n is not prime. (b) Explain why, if k2 = 1 (mod n), you can use this information to factor n (and hence n is not prime). (8) Suppose both Alice and Bob are using RSA with the same n but different e. (Let's call them e, and ez.) Suppose ged(e1,e2) = 1. Now someone sends the same message to both of them. How can someone who knows only me and me (both modulo n) figure out m? (Hint: Finding solutions to rei + ye2 = 1 is relevant.) (9) Are there solutions to the following? (a) x2 = 123 (mod 401) (b) r2 = 43 (mod 179) (c) r2 = 1093 (mod 65537). Homework 3 (Math 415) due November 9, 2020 (1) The ciphertext 5859 was obtained from RSA using n = 11413 = 101 x 113 and e = 7467. Recover the plaintext. (Use a calculator.) (2) The ciphertext 75 was obtained using RSA with n = 437 and e = 3. You know the plaintext is either8 or 9. Determine which one without factoring n. (3) Naive Nelson uses RSA to receive a single ciphertext c, corresponding to the message m. Everyone knows the modulus n and the encryption key e. Since he feels guilty that he only used his system once, he offers to decrypt any ciphertext anyone sends him, as long as it's not c, and return the answer to the person. Evil Eve sends him 2c mod n. Show how this allows Eve to find m. (4) What is wrong with using e=1 in RSA? What is wrong with using e = 2? (5) You know that 5161072 = 7 (mod 642401) and 1877222 = 28 (mod 642401). Use this information (and a calculator) to factor 642401. (6) Suppose you are given two large primes p and q. How can you (using the Chinese Remainder Theorem) find an integer such that r = 49 (mod pq) but I +7 (mod pq)? (7) Suppose n is a large odd number, and you calculate that 2(n-1)/2 = k (mod n), where k#+1 (mod n). (a) Explain why, if k? #1 (mod n), then you know n is not prime. (b) Explain why, if k2 = 1 (mod n), you can use this information to factor n (and hence n is not prime). (8) Suppose both Alice and Bob are using RSA with the same n but different e. (Let's call them e, and ez.) Suppose ged(e1,e2) = 1. Now someone sends the same message to both of them. How can someone who knows only me and me (both modulo n) figure out m? (Hint: Finding solutions to rei + ye2 = 1 is relevant.) (9) Are there solutions to the following? (a) x2 = 123 (mod 401) (b) r2 = 43 (mod 179) (c) r2 = 1093 (mod 65537)
