Suppose Amelia sets up an RSA cryptosystem with a modulus n = pq, where p and q
Question:
Suppose Amelia sets up an RSA cryptosystem with a modulus n = pq, where p and q are large primes, and a pubic key k. The public key is chosen so that 2k > n. She asks Bertrand 'What day of the week will the secret meeting be held on?', and instructs him to reply using the cryptosystem by encoding 'Monday' as the message '2', 'Tuesday' as 3, ..., Sunday' as '8', then encrypting the message using the public key k. You have intercepted Bertrand's encrypted message M̅.
(a) Explain how you can easily determine the day of the secret meeting from M̅ without factoring the modulus n. That the we started the numbering at 2 since 0 and 1 always encrypt as 0 and 1.
(b) Now suppose that the actual modulus is n = 1073 and the public key is k = 17. You have intercepted Bertrand's encrpyted message M̅ = 709. Use your method from (a) to find the day of the secret meeting, without factoring 1073. (Of course, it is easy to factor 1073, but we are keeping the numbers small so that your computations are easy to do.)
Vector Mechanics for Engineers Statics and Dynamics
ISBN: 978-0073212227
8th Edition
Authors: Ferdinand Beer, E. Russell Johnston, Jr., Elliot Eisenberg, William Clausen, David Mazurek, Phillip Cornwell