|Math 210||Spring 2019|
Problem Set 10, Due: Never
- a). Write the number 3101 in base 2.
b). If a number is 100101 in base 2, what is it base 10?
- Compute 123101 mod 17
- Let p = 23 and q = 41.
a). Compute n = pq and ϕ(n) = (p - 1)(q - 1).
b). Let e = 41. Find d so that ed = 1 (mod ϕ(n)), so (e, n) is your public key.
c). Apply the RSA method with these values to encode the message: SELL. [Use A=00, B=01, C=02 ,..., Z=25 and then group these in blocks of two, so the first block is 18, the second 04, etc. Then encrypt each of these blocks of two separately. Note that since n < 10,000 we can't use blocks of four because they might involve numbers up to 9999 which is larger than n.]
c). Now decode this message by decrypting each block of four separately.
- a). Say n = pq and ϕ(n) = (p - 1)(q - 1). Find formulas for p and q in terms of n and ϕ(n).
b). Say you know that n = 39,247,771 is the product of two primes p and q. If somehow you learn that ϕ(n) = 39,233,944, find p and q. [Moral: You should really keep the number ϕ(n) secret.]
- Using RSA encryption with the key (e, n) = (5, 2669)‚ what is the cybertext that is produced when one encrypts the message BEST WISHES ?
- Using RSA encryption with the key (e, n) = (13, 2747), if the cyphertext is 2206 0755 0436 1165 1737, what was the plaintext message?