## Homework 1 (On topics 1 and 2)

Due by 2/21/05

### Independent Work

You must solve this problem set individually without any assistance from anyone.

1. (5 points) Consider slide 12 in the handout for topic 2.2. Prove that the decryption process of a one-round Feistel cipher is the same as the input of the corresponding encryption process. That is, (L'2, R'2)=(L0, R0).
2. (5 points) Problem 2 on page 57. Random J. Protocol-Designer has been told to design a scheme to prevent messages from being modified by an intruder. Random J. decides to append to each message a hash of that message. Why doesn't this solve the problem? (We know of a protocol that uses this technique in an attempt to gain security).
3. (5 points) Problem 3 on page 92. How many DES keys, on the average, encrypt a particular block to a particular ciphertext block?
4. (5 points) Alice developed a message authentication code (MAC) based on DES. Her algorighm works as follows: For a given input message M, represent M as M=(X1||X2||...||Xm), where Xi is a 64-bit block and "||" represents concatenation. Compute Delta(M) = X1^X2^...^Xm, where "^" represents bit-wise XOR. Then the MAC for M is computed as CK(M)=EK(Delta(M)), where E is DES encryption algorithm and K is the secret key. Unfortunately, this scheme is vulnerable. Describe an attack against it. (You need to list the specific steps.)
5. (5 points) Problem 5 on page 114. Let's assume that someone does triple encryption by using EEE with CBC on the inside. Suppose an attacker modifies bit x of ciphertext block n. How does this affect the decrypted plaintext? See Figure 4-16 and related text for triple EDE DES with CBC on the inside. But note that the question is about triple EEE DES with CBC on the inside. (Make sure you read Chapter 4.4 before working on this problem.)
6. (5 points) Problem 18 on page 145. How do you decrypt the encryption specified in 5.2.3.2 Mixing in the plaintext?
7. (20 points) A and B want to establish a secure communication channel between them. They do not care about the confidentiality of the messages being transmitted, but they do want to ensure the integrity and authenticity of the messages. Answer the following questions by drawing diagrams that show the procedures of sending and receiving messages. Assume A and B share a common key K.
• (5 points) How can they achieve their goal only with secret key cryptography?
• (5 points) How can they achieve their goal only with hash function (e.g., MD5)?
• (5 points) Can they get non-repudiation? (2 points) If yes, how? If no, why? (3 points)
• (5 points) Describe a way A and B can get non-repudiation. Explain your assumption and draw a diagram to show the procedure.
8. (5 points) The DSA algorithm requires a random number each time a digital signature is generated. Demonstrate that the DSA algorithm is vulnerable if this random number is used twice.
9. (20 points) Manually complete the following operations. Explain your reason for each step. (Hints: Use Fermat Theorem, Euler Theorem, etc.) (Grading policy: You lose 4 points for each mistake you make until you lose all 20 points. Not justifying your answer is considered a mistake.)
1. (a) 123416 mod 17
(b) 5451 mod 17
(c) 5397 mod 51
(d) gcd (33, 121)
(e) 2-1 mod 17
(f) log2, 5 (4)

10. (5 points) Consider the polynomial xp-1 = 1 (mod p), where p is a prime number. It has at most p - 1 roots (because it is a polynomial of degree p - 1). Show exactly the roots of this polynomial using Fermat Theorem. (Hints: You should end up with p-1 of them.)
11. (5 points) Assume that p is a prime number and a is a positive integer not divisible by p. Prove that {a mod p, 2a mod p, …, (p-1)a mod p} = {1, 2, …, (p-1)}.
12. (15 points) Implement DES CBC mode and DES OFB modes with a parameter k. You are required to use Java for this implementation. You should use the basic DES algorithm as the block cipher. Each time when you call the encryption/decryption function, you should supply one block. Your algorithm should implement the actual feedback modes.
Requirements and notes.