DEPARTMENT OF COMPUTER SCIENCE
|CPSC 467b: Cryptography and Computer Security||Handout #8|
|Professor M. J. Fischer||April 3, 2013|
Problem Set 5
Due on Thursday, April 11, 2013.
Work the problems below, prepare your answers in electronic form, and submit your solutions using the submit script on the Zoo. Remember to specify “5” 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.
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: Quadratic Residues and the Legendre Symbol
Problem 2: 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.)
Problem 3: ElGamal Authentication
Once Happy understood ElGamal signatures, he was excited to use them for authentication. He wants to send an authenticated message m to Bob so that Bob can verify that m came from him.
Here’s his idea. Assume that Happy has an ElGamal signing key (g,p,x) and Bob has the corresponding verification key (g,p,a). We denote the signing algorithm using that key pair by S and the verification algorithm by V .
|1.||Choose random string r.|
|2.||Compute s = SA(r)||Check V A(r,s).|
|Accept m as coming from Happy if check succeeds.|