Math 210 Spring 2019

### Problem Set 10, Due: Never

1. a). Write the number 3101 in base 2.
b). If a number is 100101 in base 2, what is it base 10?

2. Compute 123101 mod 17

3. 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.

4. 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.]

5. Using RSA encryption with the key (e, n) = (5, 2669)‚ what is the cybertext that is produced when one encrypts the message   BEST WISHES  ?

6. Using RSA encryption with the key (e, n) = (13, 2747), if the cyphertext is 2206 0755 0436 1165 1737, what was the plaintext message?