MA-410 Homework 4

Due on Wednesday April 25, 2007, at 4:59pm, in my mailbox in HA245


Solutions may be submitted in person in class, placed in my mailbox or you may email an ASCII text, html, or postscipt/pdf-formatted document to me.
Note my office hours on my schedule.

  1. 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.
  2. 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.

    See FINT, §22, Problem 22.6, page 154 for a description of El Gamal: Bob sends ciphers to Alice in the Problem; in class Alice encrypted her message with Bob's public key. In class the public key a was denoted by h and the private key k by s.

  3. FINT, §25, Problem 25.1(d), page 183.
  4. FINT, §25, Problem 25.6, page 184.