代写CS 487/587: Cryptography Assignment 2帮做R编程

CS 487/587: Cryptography

Assignment 2

Exercise 1. Secure MAC [20 points] Suppose MAC is a secure MAC algorithm.

Define a new algorithm:

MAC′ (k, m) = MAC(k, m)||MAC(k, m).

Prove that MAC’ is also a secure MAC algorithm via a security reduction. Follow these steps:

• Show how verification works.

• State the contrapositive.

• Describe your reduction.

• Write the Security Analysis for your reduction.

Exercise 2. Insecure Hash Functions [30 points] Show that the following hash functions are insecure. To do that explain how to find a specific collision pair.

1. Consider a function H : {0, 1} ∗ → {0, 1} n . On input a message m and two shares of it x, w such that m = x ⊕ w, the function outputs y = H(m) = H(x) ⊕ H(w). Show that this is NOT a collision resistance hash function (i.e., show two different messages m1, m2 such that they map to the same y).

2. Let Hs a (x1||x2) = Hs(x1)⊕Hs(x2) where H is a collision resistance hash function and x = x1||x2, where |x1| = |x2| and the size of x is an even number (i.e., x1, x2 are the 2 parts of x). Show that Ha is NOT collision resistance.

Exercise 3. Secure Hash Functions [25 points] Let Hs b (x) = Hs 1 (x)||Hs 2 (x)||Hs 3 (x) where H1 , H2 , H3 are different hash functions and only one of them is collision resis-tant. Show that Hs b (x) is a collision resistant function (via a reduction).

Exercise 4. Based on Katz-Lindell Exercise 7.14. Complementarity prop-erty of DES [25 points] Show that DES has the property that if you encrypt a plaintext x under a key k to get a ciphertext y, then encrypting the bitwise com-plement of x (x) with the bitwise complement of k (k) will produce the bitwise complement of y (y). Formally, prove that

DESk(x) = y ⇒ DESk (x) = y

for every key k and input x, where z denotes the bitwise complement of z. This is called the complementarity property of DES. Does this represent a serious vulnera-bility in the use of triple-DES as a pseudorandom permutation? Explain.

Exercise 5. Insecure MACs [20 points] Let F be a fixed-length PRF. In all questions below you cannot do a truncation attack. The schemes are defined for fixed length messages.

1. Show that the following MAC scheme for messages m of length ℓn where m = m1||...||mℓ (and each mi are of size n-bits) is not secure.

t = Fk(m1) ⊕ · · · ⊕ Fk(mℓ)

2. Show that the following MAC scheme for messages m of length 2n (where m = m1||m2 and each m1, m2 are of size n-bits) is not secure.

t = Fk(m1)||Fk(Fk(m2))