YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467: Cryptography and Computer SecurityHandout #6
Professor M. J. Fischer   September 29, 2020
 

Homework Assignment 5
Due on Tuesday, October 6, 2020

1 Goal

The goal of this assignment is to test your understanding of the concepts of block cipher, information leakage, and perfect security.

Twister is a block cipher on 3-letter blocks. It uses both substitution and transposition. The message space M and ciphertext space C are triples of letters, encoded by numbers in the range [0..25] as with the Caesar cipher. The key space K = {0,…,77}. Note that |K| = 78 = 26 × 3.

Twister encryption is the composition of two ciphers Ek1 and Ek2, so Ek = Ek2 ∘ Ek1. The first cipher,

1 Ek(m1, m2,m3 ) = ((m1 + k) mod 26,(m2 + k) mod 26,(m3 + k) mod 26),

is the shift substitution used by the Caesar cipher, applied separately to each letter of the message block (m1,m2,m3). The second cipher,

2 ′ ′ ′ E k(m1,m2, m3 ) = (m 1,m 2,m3),

is a transposition cipher. The letter mj in position j is moved to position tk(j), where tk(j) = ((j + k - 1) mod 3) + 1. Thus, m′tk(j) = mj,

Questions:

  1. How does one decrypt Twister?
  2. Is Twister information-theoretically secure on single blocks? Why or why not?
  3. How much does increasing the key space to {0,…,155} increase the difficulty of breaking Twister? Explain.
  4. What is the effect on security of increasing the key space to {0,…,78}? Explain.

Please answer questions 3 and 4 with respect to both information leakage and to the difficulty of carrying out a brute-force attack. As usual, we assume keys are chosen uniformly at random from the key space.