YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer SecurityHandout #8
Professor M. J. Fischer   March 19, 2012



 

Problem Set 4

Due on Wednesday, March 28, 2012.

Instructions

Work the problems below, prepare your answers in electronic form, and submit your solutions using the submit script on the Zoo. Remember to specify “3” for the problem number argument to submit.

Some of the problems require computation. You may use a calculator or computer for the calculations, but you must show your work. For example, in problem 1, your answer should contain a table of the relevant values of g(p-1)∕q mod p to demonstrate that the Lucas test gives the result you claim.

Some of the problems use terminology that we have not covered in class, even though we have talked about the concepts. You may use external resources to find out what these terms mean. As always, you must properly cite all resources that you use to solve the problems.

Problem 1: Primitive roots

  1. Find a primitive root g of p = 761 and use the Lucas test to prove that you have one.
  2. Find a non-trivial1 number g ∈ Z* 761 that fails to be a primitive root of p, and use the Lucas test to prove your answer correct.

Problem 2: Security of Digital Signatures

  1. What is existential forgery of a digital signature scheme?
  2. What are practical mechanisms to prevent existential forgery? Describe the mechanisms and explain why it would be hard to produce a forged message-signature pair.
  3. Is the ElGamal signature scheme susceptible to the existential forgery attack? If yes, show how an attacker can produce a valid message-signature pair. If no, explain why the scheme is resistant to this attack. State all assumptions you make.

Problem 3: Quadratic Residues and the Legendre Symbol

  1. Let p = 19, q = 37, and n = p×q = 703. For each i,j ∈{-1,1}, find a number xi,j ∈ Z*n such that
    ( xi,j)            ( xi,j)
  ----  = i  an d    ---- =  j.
   p                 q

  2. Use the Euler criterion to justify your answers to part (a).

Problem 4: Miller-Rabin Test

Let n = 703. Find a witness a for which the Miller-Rabin test succeeds in showing the compositness of n. Show the sequence of values b0,b1,b2, that the test generates from a, and explain clearly why you can conclude from this sequence that n is not a prime.

Problem 5: Properties of Hash Functions

Hash functions are frequently used for cryptographic applications. A cryptographic hash function must have at least the properties listed below in order to withstand known attacks. For each of these properties, (1) say what it is, (2) give a plausible scenario whereby an attack exploiting a hash function lacking such property might be carried out, and (3) say whether there is an efficient hash function that has that property. (If yes, list that hash function; if no, explain why.)

  1. Preimage resistance
  2. Second-preimage resistance
  3. Collision resistance