CS-235. Problem Set 4

 

  1. Ex. 5 in Supplemental material
  2. Ex. 7 in Supplemental material
  3. Ex.2.8
  4. Ex.2.9
  5. Extra Credit: Ex.2.10
  6. Ex. 3.24 (a: assigned, b: extra credit)
  7. Solve the following equalities (or prove that there is no solution):
    Note: "=" is used here in place of the 3-bar "congruence" symbol
    1. 15x + 21 = 2 (mod 31)
    2. 15x + 21 = 2 (mod 33)
    3. 15x + 21 = 3 (mod 33)
    4. 15x + 21 = 2 (mod 31) AND 15x + 21 = 3 (mod 33) [that is x must satisfy both]
    5. 2x+3 = 4 (mod 5) AND 4x+3=2 (mod 7) AND 8x+9=10 (mod 11)
  8. RSA: compute RSA public and private keys using the primes 11 and 13, and write Encrypt and Decrypt algorithms for it.
    1. You can pick any e,d. Test your result by encrypting and then decrypting 1, 2, 3, 5, 10, 100.
    2. It is customary to fix e to be something small and always the same, e.g., 3 or 5. What would be the corresponding d for each of these values of e? Can you use e=4? How about e=7?
    3. Now, what would the public and secret key be if you use primes 101 and 113 instead?
      Use the smallest possible value of e.