MA-410 Homework 4

Due at the beginning of class, Wednesday, April 22, 2009


Solutions may only be submitted in person in class. Note my office hours on my schedule.

  1. Show that the El Gamal public key crpytosystem is malleable even if Alice encrypts with a randomly chosen r every time. For the example p = 13, g = 2, s = 6, show how Charlie can encrypt M/2 with his own random r' seeing Alice's ciphertext of M which is assumed to be an even residue.
  2. Let p be an odd prime such that 3 does not divide p-1. Prove that for any residue a modulo p there exists a residue b modulo p such that b3 is congruent to a modulo p.
  3. ENT, §9.3, Problem 1(d), page 190. Please use Eisenstein's method.
  4. ENT, §12.1, Problem 4, page 251.