Problem 1:  Multiple Choice Questions (only appear in midterm and final exams)

Note: Fill in one choice of the provided answers for each question. Filling multiple choices will be zero points.

1.  Cryptography CANNOT be used for           .

(A) Encryption

(B) Ransomware attack

(C)  Secure file system

(D) Hash function

(E) None of the above

2. Today, the security of RSA and Diffie-Hellman algorithms depends on the lack of knowledge of effective algorithms for some            problems.

(A) P

(B) NP

(C) NP-complete

(D) NP-hard

(E) None of the above

3. In the following,            is NOT a symmetric encryption algorithm.

(A)  Substitution cipher

(B) Vernam One-Time-Pad

(C) DES

(D) AES

(E) None of the above

4. AES (Advanced Encryption Standard) CANNOT support a key size of            bits.

(A) 64

(B)  128

(C)  192

(D)  256

(E) None of the above

5. In the following cryptographic methods,            is NOT designed for confidentiality.

Problem 3:  One Time Pad

Recall OTP. Assume that we have a random number k1 , which length is half the length of message m. Answer the following questions.

(a) If we use k1  two times (i.e., use k1 ||k1  as the key, where || denotes concatenation) to encrypt

m using the OTP scheme, would it affect the confidentiality of the message m? Why or why not? Justify your answer.

(b) We generate another random number, k2 , where k1    k2 .  If we concatenate k2  with k1 , the

total key length will be same with m (i.e., len(k1 ||k2 ) = len(m)). If we use k1 ||k2 , instead of generating a totally new key k\  where len(k\ ) = len(m), to encrypt m using the OTP scheme, would it affect the confidentiality of the message m? Why or why not? Justify your answer.

NOTE:

- Confidentiality of the message m is affected as long as the attacker Eve can obtain some function of the plaintext message m.

- Any bit mi  of the plaintext m is a function of m.

- mi ⊕ mj , where mi  and mj  are two distinct bits in m, is a function of m.

Limit your answer to 5 lines for each question (including the justification). An answer without a justification will result in an automatic 0.                                                                          

Solution:

Problem 4:  Block Cipher Modes of Operation

Consider a variant of the CBC mode, called CBC* mode, where the encryption formula for cipher- text block Ci  is

Ci  = EK (Pi ) ⊕ Ci −1,C0  = IV                                                   (1)

Where E() can be any strong block cipher, e.g. AES.

Note: P0  does not exist (i starts at 1 for the plaintext)

Answer the following questions:

(a) What is the formula for decrypting ciphertext block Ci

(b) Explain the precise consequence of the loss of ciphertext block Ci .  Assume a decryptor is

aware of that loss (i.e., knows the index, i, of the lost block).

(c) Are there any security problems in CBC* mode? If so, identify one problem and briefly justify your answer.  If not, explain why there are no problems.  (Hint:  What kind of patterns can the adversary see in the ciphertext based on a certain plaintext?) Limit your answer to 5 lines.

Solution:

Problem 5:  Probability of Collision

In the university of Crapoptamia, every student can design their own student ID. Here is the rules for getting the student ID:

1. The first character should be an upper-case English letter.  Students can randomly pick one letter.

2. The following two digits should be the month of student’s birthday.

3. The last four characters are 4 digits chosen by each student.

For example, Z051133 is an valid ID for a student who was born in May.

We assume that each student will randomly choose the first English letter and the four digits.

In a Computer Science class, the instructor tells the class that there is at least a 99% possibility that two or more students share the same first four characters in their student ID.

(a) At least how many students are there in the class? Explain your solution.  (Assume that the

distribution of the birth months is uniform.)

(b)  One student says that the first four characters are ‘A019’ and asks his classmates to raise

the hand if someone has the same first four characters.  However, no one responds.  Has the instructor made a mistake?  Think about relevant properties of hash functions and contrast the instructor’s logic and the student’s question.

Solution:

Problem 6:  Group Theory

1.  Consider [Zp , +] where p is a prime number, + is modular addition. Is this an Abelian group? Why or why not?

2. How many multiplications would you need to compute 1548    mod 53? (HINT: You don’t need to actually compute it.)

3. Does there exist an inverse of 26 in Z3 ?  Why or why not?  Provide the inverse element if there exists.

4.  Compute Φ(31) and Φ(110). Show your work.

Solution: