CS 487/587: Cryptography

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 487/587: Cryptography

Final

Submission: Submit your answers on Blackboard by 11:59pm Sunday, May 5, 2024.

Your submission should include a .PDF file with all the answers.

1. Include your name and whether you take the class at 499 or 587 level.

2. Type out your answers, being very concise.

3. You are encouraged to use multiple sources and AI tools like ChatGPT. Ensure you cite all sources used, including discussions with other students.

4. Be transparent about any help received. There’s no penalty for disclosing sources and assistance.

5. While collaboration and resource use are encouraged, plagiarism is strictly pro-hibited. Submit original work only.

Exercise 1. Katz-Lindell Exercise 1.7 [20 points] The index of coincidence method relies on a known value for the sum of the squares of plaintext-letter frequen-cies. Why would it not work using the sum P i pi itself?

Exercise 2. Katz-Lindell Exercise 3.6 [40 points] Let G be a pseudorandom generator. For each of the following cases, determine whether G′ is necessarily a pseudorandom generator. If yes, give a proof; if not, provide a counterexample.

1. Define G′ (s) = G(s), where s is the complement of s.

2. Define G′ (s) = G(s).

3. Define G′ (s) = G(0|s| ∥ s).

4. Define G′ (s) = G(s) ∥ G(s + 1).

Exercise 3. Katz-Lindell Exercise 11.4 [40 points] Consider the following key-exchange protocol:

(a) Alice chooses uniform k, r ∈ {0, 1} n , and sends s := k ⊕ r to Bob.

(b) Bob chooses uniform t ∈ {0, 1} n , and sends u := s ⊕ t to Alice.

(c) Alice computes w := u ⊕ r and sends w to Bob.(d) Alice outputs k and Bob outputs w ⊕ t.

Show that Alice and Bob output the same key. Analyze the security of this protocol (i.e., either prove its security or show a concrete attack).

*** The question below is only for 587 students ***

Exercise 4. Katz-Lindell Exercise 12.15 [20 points] Consider the RSA-based encryption scheme in which a user encrypts a message m ∈ {0, 1} ℓ with respect to the public key ⟨N, e⟩ by computing ˆm := H(m) ∥ m and outputting the ciphertext ˆme mod N. (Here, let H : {0, 1} ℓ → {0, 1} n and assume ℓ + n < ∥N∥.) Is this scheme CPA-secure if H is modeled as a random oracle?