CS134: Computer and Network Security Fall 2022 Homework 2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Fall 2022
CS134: Computer and Network Security
Homework 2
Problem 1: RSA
Assume the following RSA parameters: p = 11, q = 7, d = 37. The ciphertext C = 8.
1. Use Extended Euclidean Algorithm to find the value of public exponent e. Show your work.
2. Use Chinese Remainder Theorem to find the value of plaintext M . Show your work.
Problem 2: El Gamal Encryption Scheme
Alice and Bob agree to use the El Gamal public key encryption scheme to exchange a message. Alice chooses 13 as her prime number p and 9 as her secret x. Answer the following questions. Remember to show your work.
1. Recall that the public residue can be calculated using y = bx mod p. What are the public value(s) that Alice will hand over to Bob?
2. Bob chooses a random value r = 6 and encrypts message m = 10 using the value(s) he received from Alice. What is the ciphertext that Bob sends to Alice?
3. Given the ciphertext from Bob, show how Alice derives the message back from the ciphertext.
4. Explain how Eve can conduct a Man-in-the-Middle attack to this cryptosystem. Limit your answer to 5 lines.
Problem 3: Zero-Knowledge with Fizz and Buzz
You and Alice have stumbled upon two unlabeled bottles of lemonade and a bunch of empty cups. Alice insists that the bottles contain the same type of lemonade, but you know better: you know by taste that one is Fizz and the other Buzz. How could you prove to your friend that lemonades are different, without revealing which is Fizz and which is Buzz? You may assume that the bottles of lemonade will never run out.
Problem 4: Authentication Protocol Security
Assume that A and B share a long-term 256-bit AES key K . Our key exchange protocol has two goals: (1) let A and B agree on a new fresh session key Ks to be used for a current session, and (2) perform mutual authentication. Nb is a nonce and Ks is a new session key generated by B. Assume that Ks and Nb are of the same bit-length and both are always chosen at random. EK (.) denotes AES encryption of everything inside () with key K . HMACK (.) denotes SHA2-based HMAC of everything inside () using key K .
Protocol:
1. A −→ B: EK (“A” , “B” , “Hello”)
2. B −→ A: EK (Ks ,Nb ,HMACK (“A” , “B” , “Hello”))
3. A −→ B: HMACK (Ks ,Nb , 1)
What (if any) are the vulnerabilities of this protocol? If there are any, how can you fix them? For fix, you need to show modification of the protocol.
Limit each answer (vulnerabilities and their fixes separately) to 10 lines.
Problem 5: Interleaving Attack
Consider the mutual authentication protocol with a pre-shared symmetric key K:
1. A → B : “A”,S
2. B → A : EK (S + 1, “A”)
3. A → B : EK (S + 2, “B”)
Assume EK () is a secure block cipher (e.g., AES) and S is a 32-bit monotonically increasing sequence number and maintained by both A and B. A and B reject the authentication if S in the first step is less than or equal to their maintained value.
Does the interleaving attack work on this protocol? If so, write down how the attack can be carried out and how to fix it (need to show modification of the protocol and explain why). Otherwise, explain why the attack won’t work.
Limit each answer (vulnerabilities and their fixes separately) to 10 lines.
2022-11-05