HW3
 Due May 26, 2018 by 11:59pm
 Points 110
 Submitting a file upload
EE 595 (PMP) Introduction to Security and Privacy
Homework 3
Assigned: Monday, May 14, 2018, Due: Saturday, May 26, 2017
Instructor: Tamara Bonaci
Department of Electrical Engineering
University of Washington, Seattle
Problem 1
Let h: Z_{2}_{n} →Z_{2n }be a hash function with n > 1,defined by h(m)=m^{2}+ am + b mod 2^{n}
Prove that Eve can solve the Second Preimage problem for any message m without solving a quadratic equation.
Problem 2
Suppose that f : {0, 1}^{m }→ {0, 1}^{m }is a preimage resistant bijection. Define ^{h }: {0, 1}^{2m }→ {0, 1}^{m }as follows. Given x ∈{0,1}^{2m},write x = x′x′′ where x′, x′′ ∈ {0,1}^{m}.Then define h(x)=f(x′⊗x′′). Prove that h is not second preimage resistant.
Problem 3
Assume a good hash function h, and assume there exists a particular hash value d, and that you would like to find a message that has a hash value of d. Given that there are many more 2000bit messages that map to a particular 128bit hash than there are 1000bit messages, would you theoretically have to test fewer 2000bit messages to find one that has a hash of d than if you were to test 1000bit messages?
Problem 4

Assuming there exists a planet where a year has 25 months, and every month is equally likely to be someone’s birthday, what is the probability that no two people of 100 000 people living on that planet have a birthday in the same month?

Assume you are given a cryptographic hash function that produces a 512bits long hash output. Given some message m and its corresponding hash output h(m), what is the average probability that an attacker can find another message, m' not equal to m, that has the same hash output? In your computations, assume that attackers can make a maximum of 264 attempts.
Problem 5
Suppose h_{1 }: {0,1}^{2m }→ {0,1}^{m }is a collision resistant hash function. Define h_{2 }: {0,1}^{4m }→ {0,1}^{m }as follows:
1. Write x ∈ {0,1}^{4m }as x = x_{1}∥x_{2}, where x_{1}, x_{2 }∈ {0,1}^{2m}. Define h_{2}(x) = h_{1}(h_{1}(x_{1})h_{1}(x_{2})).
Prove that h_{2 }is collision resistant.
Problem 6
Consider the following digital signature scheme. The public key is given by (q,α,β), where q is a prime number, α is a primitive root of q, and β is an integer satisfying β < q. The private key is equal to a, for some positive integer a < q satisfying β ≡ α^{a }(mod q).
To sign a message m, compute y = h(m), the hash of the message. Assume that gcd(y, q − 1) = 1 (if this is not the case, append a random string to m and recompute the hash. Repeat the process until a message m is found satisfying gcd(y, q − 1) = 1). Then calculate z such that yz ≡ a (mod (q − 1)). The signature of the message is αz. To verify the signature, a user verifies that β = (α^{z})^{y }(mod q).
Show that the scheme is unacceptable by describing a simple technique for forging a user’s signature on an arbitrary message.