Instructions:

This is a closed book examination. Answer any 5 of the following 6 questions. Write the numbers of the five questions that you want graded on the cover of your bluebook. All questions count equally. You have 75 minutes. Remember to write your name on your bluebook and to justify your answers. Good Luck!

___________________________________________________________________________________

Problem 1: Symmetric Cryptosystems and Information Security

Consider the encryption function for a symmetric cryptosystem described by the table below, where = = = {0,1,2,3}:

1. Give the corresponding decryption function.
2. What does it mean for a cryptosystem to be information-theoretically secure?
3. Is this cryptosystem information-theoretically secure? Why or why not?

Solution:

1. From the original encryption function, we can easily derive the decryption function as:

2. For the cryptosystem to have perfect secrecy (be information-theoretically secure), it means that the random variables c and m are statistically independent, that is,

   (1)

   for all m₀ and c₀ . An equivalent definition in terms of conditional probability is

   (2)

   for all m₀ and c₀ such that prob[c = c₀]≠0. Hence, even after Eve receives the ciphertext c₀, her opinion of the likelihood of each message m₀ is the same as it was initially, so she has learned nothing about m₀.

3. No, this cryptosystem is not information-theoretically secure. A simple observation is that prob[m = 3] = 1∕4, but prob[m = 3∣c = 0] = 0. Similarly, prob[m = 2] = 1∕4, but prob[m = 2∣c = 1] = 0. Therefore, after receiving c = 0 or c = 1, we have learned partial information about m.

Problem 2: Attacks

We have discussed a number of different possible attacks on a cryptosystem by a passive eavesdropper Eve, depending on what information is available to her.

1. Describe the following three kinds of attack on a cryptosystem: ciphertext only, known plaintext, chosen plaintext. For each, give a scenario in which such an attack might be plausible for Eve to carry out.
2. Consider the following simple cryptosystem: A message m = m₁m₂…m_t is a t-bit string. A key is a single bit k {0,1}. The encryption function is E_k(m) = c, where c = c₁c₂…c_t and c_i = m_i ⊕ b, for i = 1,…,t. Discuss the security of this system under each of the three kinds of attacks (from part (a) above). Where the system is insecure, describe carefully the sense in which it insecure. Be sure to say also how the security is affected by the choice of t.

Solution:

1. Ciphertext-only

   Eve knows only c and tries to recover m. Eve is able to perform such attack if she has access to the communication channel between Alice and Bob, for example, if she controls the gateway through which Alice accesses the Internet.

   Known plaintext

   Eve knows a sequence of plaintext-ciphertext pairs (m₁,c₁), …, (m_r,c_r). Now she obtains a new ciphertext c ⁄ {c₁,…,c_r} and wants to recover the corresponding message m. Eve is able to perform such an attack if the previous plaintext-ciphertext pairs are revealed by Alice or Bob. Eve might also get information about the previous plaintext-ciphertext pairs by looking into Alice’s swap files.

   Chosen plaintext

   This is like a known plaintext attack, except that before getting c, Eve gets to choose messages m₁, …, m_r and somehow get Alice (or Bob) to encrypt them for her and supply her with the corresponding ciphertexts c₁, …, c_r. Eve is able to perform such attack if Alice is a server that provides encryption service. Eve can also perform such an attack on an asymmetric cryptosystem such as RSA where she has access to the public encryption key.

2. Ciphertext-only

   When t = 1, this cryptosystem is information-theoretically secure. When t > 1, Eve is able to get partial information about the plaintext. In particular, if the ciphertext is c = c₁…c_t, she knows that the plaintext is either c or (the complement of c).

   Known plaintext

   Whatever length the message is, one plaintext-ciphertext pair is sufficient to recover the key and break the cryptosystem.

   Chosen plaintext

   A chosen plaintext attack is stronger than a known plaintext attack, so again, whatever length the message is, one plaintext-ciphertext pair is sufficient to recover the key and break the cryptosystem.

Problem 3: DES

Recall that the heart of DES is a round of the form:

Consider a simplified DES-like cryptosystem consisting of n such rounds, where the function f is defined by f_K(X) = K ⊕ X. Here we assume that the key K is 32-bits long and that the same key is used at each round, that is, K_i = K for each round i.

This system is used to encrypt a 64-bit message M as follows: L₀ is the leftmost 32-bits of M and R₀ is the rightmost 32-bits of M. The ciphertext E_K(M) is L_n ⋅ R_n.

1. Describe how to decrypt messages encrypted with E_K.
2. Express L₁, R₁, L₂, R₂ in terms of L₀, R₀, and K.
3. Show why increasing the number of rounds n can actually decrease security.

Solution:

1. This is a simplified DES-like cryptosystem. Like DES, decryption can be done by starting with the left and right halves of the ciphertext, L_n and R_n respectively, and working backwards round by round to the plaintext message M = L₀ ⋅ R₀. In round i of encryption, the algorithm works as follows:
   
   To decrypt, we solve (3) to express L_i and R_i in terms of L_i+1 and R_i+1. This yields
   
   Applying (4) for i = n - 1,n - 2,…,0 yields the desired plaintext.

   We remark that, also like DES, the encryption and decryption functions for each round are almost the same. Let E_K(L_i ⋅ R_i) = L_i+1 ⋅ R_i+1 be the encryption function defined by (3). Let D_K(L_i+1 ⋅R_i+1) = L_i ⋅R_i be the corresponding decryption function defined by (4). One can easily verify that

   (5)

   Thus, if S(L⋅R) = R ⋅L is the function that swaps the left and right halves of its 64-bit argument, then it follows from (5) that

   (6)

2. 
3. If we continue the encryption to the third round, we will find that
   
   Therefore, increasing the number of rounds from 2 to 3 results in the ciphertext being identical to the plaintext, so there is no security at all.

Problem 4: Chaining Modes

Let (E,D) be a block cipher and let m₁,m₂,…,m_t be a sequence of t plaintext blocks. Happy Hacker was not happy with the chaining modes he learned about in CPSC 467, so he invented his own. He defines a sequence of t + 2 ciphertext blocks c₀,c₁,c₂,…,c_t,c_t+1 which satisfies the equation

1. Describe how to reconstruct m₁,…,m_t given c₀,…,c_t+1.
2. Happy was having trouble figuring out how to compute the c_i’s because of the cirular dependencies. Please help him by showing how to compute c_i+1 from c_i-1, c_i, and m_i, where 1 ≤ i ≤ t. How should he choose c₀ and c₁?

Solution:

1. For i = 1, …, t, we have the condition

   (10)

   Applying decryption function to both sides of (10) gives

   
   Adding (using ⊕) the expression (⊕c_i-1 ⊕ c_i+1) to (11) and swapping the two sides gives

   (12)

2. Adding (using ⊕) (⊕c_i-1 ⊕ m_i) to (11) and swapping the two sides gives

   (13)

   where 1 ≤ i ≤ t. In order to get started, we set c₀ and c₁ to some fixed initialization vectors.

Problem 5: RSA

My toy RSA key is N = 187,e = 107. You observe a ciphertext c = 2. What is the plaintext? (Note: 187 = 11 * 17.)

Solution:

Given N = 187 = 11 × 17, it is easy to compute ϕ(N) = (11 - 1) × (17 - 1) = 160.

Next, given e = 107, which is relative prime to 160, we use extended Euclidean algorithm to compute d such that ed ≡ 1 (mod 107):

The result from the table is d = v₄ = 3.

Finally we apply the decryption function of RSA to get the plaintext

(14)

Problem 6: Euler’s Theorem

1. Define Euler’s totient function ϕ(n), and state Euler’s theorem.
2. Calculate 2⁵⁴⁹ mod 29.

   (Hint: This problem is easily solved by hand using Euler’s theorem to reduce the size of the exponents.)

Solution:

1. Let Z* _n = {a Z_n∣gcd(a,n) = 1}, then Euler’s totient function ϕ(n) is the cardinality of Z*_n. If we represent an integer n by its prime factors as follows

   (15)

   then ϕ(n) can be calculated as

   (16)

   Euler’s theorem says, for every x that is relative prime to n,

   (17)

2. Given n = 29, it is easy to compute ϕ(29) = 29-1 = 28, and ϕ(ϕ(29)) = (2-1)×2^2-1 ×(7-1) = 12.

   After verifying gcd(5,28) = 1, applying Euler’s theorem gives

   (18)

   Therefore after verifying gcd(2,29) = 1, we have

   (19)

   which implies 2⁵⁴⁹ mod 29 = 2⁵¹ mod 29 = 3.