Problem 2: Alice's RSA public key is P = (e.n) = (3.1633). Bob sends Alice the...

  

Transcribed Image Text:

Problem 2: Alice's RSA public key is P = (e.n) = (3.1633). Bob sends Alice the message by encoding it as follows. First he assigns numbers to characters: A is 3. B is 4. .... Z is 28, a blank is 29, quotation marks: 30, a period: 31. a coma: 32, an apostrophe: 33. Then he uses RSA to encode each number separately. Bob's encoded message is: 872 14 1111 933 27 1331 1527 1527 14 1096 1331 27 109 87 1331 14 1527 1527 1468 729 1331 27 830 27 830 850 27 397 830 1527 109 1527 14 1096 343 830 512 729 1527 109 729 11 95 872 512 14 1527 343 1527 1468 850 343 108 1096 14 27 512 1527 512 216 1468 850 343 1000 1527 1527 1527 1468 1527 736 850 850 343 1096 928 343 343 850 850 27 1331 1468 1111 14 928 1096 108 14 1527 1527 1000 1000 1527 850 Decode Bob's message. Notice that you don't have Bob's secrete key, so you need to "break" RSA to decrypt his message. For the solution, you need to provide the following: (a) Describe step by step how you arrived at the solution: find p and q, o(n) and d. (b) Show your work (the computation) for one number in the message. (c) Give the decoded message (in integers). (d) Give Bob's message in plaintext (also, what does it mean and who said it). (e) To decode the remaining numbers, you need to write a program in C++, test it on Codeforces and attach the code. Your program should : (i) Take three integers, e, n (the public key for RSA), and m the number of characters the message has as inputs to your program. • (ii) Then take m integers as inputs to your program. This will be the encoded message. 1 • (iii) Check to see if the public key is a valid pair. If not, output a single line "Public key not valid!" and quit the program. • (iv) Decode the message. . (v) Output p and q, o(n) and d. • (vi) On a new line, output the decoded message in integers. (vii) On a new line, output the decoded message in English. The characters should be all uppercase. You can assume that the numbers will be assigned to characters according to the mapping above: A is 3, B is 4, Please upload your code to Codeforces to test. There are two open test cases and 3 hidden ones. If you implement everything correctly, codeforces will say you have 5 points. The link on how to register/submit code for the RSA project is here. Problem 2: Alice's RSA public key is P = (e.n) = (3.1633). Bob sends Alice the message by encoding it as follows. First he assigns numbers to characters: A is 3. B is 4. .... Z is 28, a blank is 29, quotation marks: 30, a period: 31. a coma: 32, an apostrophe: 33. Then he uses RSA to encode each number separately. Bob's encoded message is: 872 14 1111 933 27 1331 1527 1527 14 1096 1331 27 109 87 1331 14 1527 1527 1468 729 1331 27 830 27 830 850 27 397 830 1527 109 1527 14 1096 343 830 512 729 1527 109 729 11 95 872 512 14 1527 343 1527 1468 850 343 108 1096 14 27 512 1527 512 216 1468 850 343 1000 1527 1527 1527 1468 1527 736 850 850 343 1096 928 343 343 850 850 27 1331 1468 1111 14 928 1096 108 14 1527 1527 1000 1000 1527 850 Decode Bob's message. Notice that you don't have Bob's secrete key, so you need to "break" RSA to decrypt his message. For the solution, you need to provide the following: (a) Describe step by step how you arrived at the solution: find p and q, o(n) and d. (b) Show your work (the computation) for one number in the message. (c) Give the decoded message (in integers). (d) Give Bob's message in plaintext (also, what does it mean and who said it). (e) To decode the remaining numbers, you need to write a program in C++, test it on Codeforces and attach the code. Your program should : (i) Take three integers, e, n (the public key for RSA), and m the number of characters the message has as inputs to your program. • (ii) Then take m integers as inputs to your program. This will be the encoded message. 1 • (iii) Check to see if the public key is a valid pair. If not, output a single line "Public key not valid!" and quit the program. • (iv) Decode the message. . (v) Output p and q, o(n) and d. • (vi) On a new line, output the decoded message in integers. (vii) On a new line, output the decoded message in English. The characters should be all uppercase. You can assume that the numbers will be assigned to characters according to the mapping above: A is 3, B is 4, Please upload your code to Codeforces to test. There are two open test cases and 3 hidden ones. If you implement everything correctly, codeforces will say you have 5 points. The link on how to register/submit code for the RSA project is here.

Answer rating: 100% (QA)

Steps in RSA algorithm Consider two large prime numbers p and q Calculate n p q Now public key is gi... View the full answer