=========================preview======================
(comp170)[2009](s)mid2~PPSpider^review_10161.pdf
Back to COMP170 Login to download
======================================================
COMP170 (Spring 2009)
Midterm 2 Review



Suppose Alice wants to send a message M to Bob using RSA encryption so that only Bob can read it. The plaintext M, as a single positive integer, is encrypted to the corresponding ciphertext C which is then sent to Bob. An adversary, Eve, intercepts the ciphertext in the communication channel and .nds that C = 22. From a public directory, Eve .nds that the public key (e, n) of Alice is (47, 391) and that of Bob is (173, 481). Eve wants to seek your help to break the RSA encryption to recover the original plaintext M.
What is the value of M? Describe in detail all steps required to compute it. In case you need to .nd the multiplicative inverse of a number, there is no need to show details of the extended GCD algorithm. You just need to provide a number and show that it is the multiplicative inverse.


RSA encryption: C = Me mod n

Public key of Bob (e, n) = (173, 481)
RSA decryption: M = Cd mod n n = 481 = 13 37 . p = 13, and q = 37 T =(p . 1)(q . 1) = 432 d is multiplicative of e . d =5



M = 225 mod 481 = ((222 mod 481)2 22) mod 481 = (32 22) mod 481 = 198



RSA encryption: C = Me mod n Public key of Bob (e, n) = (173, 481)


RSA decryption: M = Cd mod n n = 481 = 13 37 . p = 13, and q = 37 T =(p . 1)(q . 1) = 432 d is multiplicative of e . d =5



M = 225 mod 481 = ((222 mod 481)2 22) mod 481 = (32 22) mod 481 = 198



RSA encryption: C = Me mod n Public key of Bob (e, n) = (173, 481)


RSA decryption: M = Cd mod n

n = 481 = 13 37 . p = 13, and q = 37
T =(p . 1)(q . 1) = 432
d is multiplicative of e . d =5



M = 225 mod 481 = ((222 mod 481)2 22) mod 481 = (32 22) mod 481 = 198



RSA encryption: C = Me mod n Public key of Bob (e, n) = (173, 481)


RSA decryption: M = Cd mod n n = 481 = 13 37 . p = 13, and q = 37



T =(p . 1)(q . 1) = 432
d is multiplicative of e . d =5


M = 225 mod 481 = ((222 mod 481)2 22) mod 481 = (32 22) mod 481 = 198



RSA encryption: C = Me mod n Public key of Bob (e, n) = (173, 481)


RSA decryption: M = Cd mod n n = 481 = 13 37 . p = 13, and q = 37 T =(p . 1)(q . 1) = 432




d is multiplicative of e . d =5
M = 225 mod 481 = ((222 mod 481)2 22) mod 481 = (32 22) mod 481 = 198



RSA encryption: C = Me mod n Public key of Bob (e, n) = (173, 481)


RSA decryption: M = Cd mod n n = 481 = 13 37 . p = 13, and q = 37 T =(p . 1)(q . 1) = 432 d is multiplicative of e . d =5



M = 225 mod 481 = ((222 mod 481)2 22) mod 481 = (32 22) mod 481 = 198



RSA encryption: C = Me mod n Public key of Bob (e, n) = (173, 481)


RSA decryption: M = Cd mod n n = 481 = 13 37 . p = 13, and q = 37 T =(p . 1)(q . 1) = 432 d is multiplicative of e . d =5



M = 225 mod 481 = ((222 mod 481)2 22) mod 481 = (32 22) mod 481 = 198



Suppose Alice and Bob want to share a secret key but the communication channel between th