MA-410 Homework 4

Due at the beginning of class, Wednesday, April 23, 2008


Solutions may be submitted in person in class, or you may email an ASCII text, html, or postscipt/pdf-formatted document to me.
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.