Homework 3, Due March 12, 11am

  1. Compute 13635 + 16060 + 8190 + 21363 (mod 29101) in two ways and verify the equivalence: by reducing modulo 29101 after each addition and by computing the entire sum first and then reducing modulo 29101. (Show your work.)

  2. Compute the result of 12358 * 1854 * 14303 (mod 29101) in two ways and verify the equivalence: by reducing modulo 29101 after each multiplication and by computing the entire product first and then reducing modulo 29101. (Show your work.)

  3. Use the ExtendedGCD algorithm to compute the inverse of 74 modulo the prime 167. (Show your work.)

  4. Compute 2735 (mod 569) using repeated squaring (see slides for Lecture 19). How many multiplications did you have to perform? (Show your work.)

  5. Assume 200 people wish to communicate securely using symmetric keys, one symmetric key for each pair of people. How many symmetric keys would this system use in total? (To elaborate on "one symmetric key for each pair of people", the answer to this question would be 1 if there were 2 people, and 3 if there were 3 people.)

  6. Let p = 83, q = 101, n = pq, and e = 3. Is (n, e) a valid RSA public key? If so, compute the corresponding private RSA key d. If not, why not? (Provide enough details to justify your answer -- don't just give your answer -- but OK not to show every step of your calculations.)

  7. Let p = 79, q = 89, n = pq, and e = 3. Is (n, e) a valid RSA public key? If so, compute the corresponding private RSA key d. If not, why not? (Provide enough details to justify your answer -- don't just give your answer -- but OK not to show every step of your calculations.)

  8. Let p = 71, q = 89, n = pq, and e = 3. First find d. Then compute the signature on m1 = 5416, m2 = 2397, and m3 = m1*m2 (mod n) using the basic RSA operation. Show that the third signature is equivalent to the product of the first two signatures. (Provide enough details to justify your answer -- don't just give your answer -- but OK not to show every step of your calculations.)

  9. Consider a PKI, and suppose a CA is malicious. What bad things could the CA accomplish?

  10. How many root SSL certificates are hard-coded into your Web browser of choice? (Tell us both your web browser and the number of root SSL certificates.) Pick five of these and tell us: the name of the CA; when the certificate was created (or the date at which it first became valid); and when the certificate expires.