Problem Set 10, Due: Never

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

2. Verify that 12⁷⁰⁴ is congruent to 1 (mod 391).

3. For a simple RSA encryption, you use n = pq , where p = 5 and q = 11.
   a). Find a public exponent e and a private exponent d.
   b). Say the entire message Alice want to send you is the number 6. What is Alice's encryption of this message?

4. Let p = 23 and q = 41.
   a). Compute m = pq and k = (p - 1)(q - 1).
   b). Let e = 41. Find d so that ed = 1 (mod k), so (m, e) 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 05, etc. Then encrypt each of these blocks of two separately. Note that since m < 10,000 we can't use blocks of four because they might involve numbers up to 9999 which is larger than m.]
   c). Now decode this message by decrypting each block of four separately.

5. a). Say m = pq and k = (p - 1)(q - 1). Find formulas for p and q in terms of m and k.
   b). Say you know that m = 39,247,771 is the product of two primes p and q. If somehow you learn that k = 39,233,944, find p and q. [Moral: You should really keep the number k secret.]