Question 1

Suppose we de ne an encryption scheme as follows. The key will be four elements k1,k2,k3, and k4 in Z26. The message space will be sequences of elements of Z26 of length 6. The ciphertext space will be the same as the message space.

The encryption algorithm is the following. Given a key k1, k2, k3 and k4 and a message a1, a2, a3, a4, a5, a6, the corresponding ciphertext is b1,b2,b3,b4,b5,b6, where:

b1 = k1a1 + k2a2 (mod 26)

b2 = k3a1 + k4a2 (mod 26)

b3 = k1a3 + k2a4 (mod 26)

b4 = k3a3 + k4a4 (mod 26)

b5 = k1a5 + k2a6 (mod 26)

b6 = k3a5 + k4a6 (mod 26)

Suppose you know that the message SIXWIG (thought of as a sequence of numbers in Z26) corresponds to the ciphertext IGPXUY.

Question 2

You may know that the cipher described in Question 1 is the Hill Cipher and that the key elements k1,k2,k3 and k4. However let us ignore this fact and suppose that any four elements in can be a key.

Question 2, part a

How many keys are there in the Hill Cipher described above?

Question 2, part b

Suppose we regard the Hill Cipher as described in Question 1 as a block cipher. The blocks are elements of (_i.e._ sequences of letters of length 6). How many distinct blocks are there?

Question 2, part c

The expected number E(F) of false keys that exist for a brute force attack on a block cipher with

a single known plaintext pair is given by the formula

E(F)= #keys / #blocks

What is the expected number of false keys for a brute force attack on the Hill Cipher as described

in Question 1 with a single known plaintext pair?

Question 2, part d

Suppose your answer to Question 2, part a was p. If = p, then what is ? (Hint: use log base 2)

Question 2, part e

Suppose you changed one of the plaintext characters in the plaintext SIXWIG from Question 1.

How many ciphertext characters would be affected?

Question 2, part f

Suppose you changed one of the key characters used when encrypting SIXWIG.

How many ciphertext characters would be affected?

Question 2, part g

A _chosen plaintext_ attack is a threat model in which the attacker is allowed to use the encryption algorithm Ek with key k to encrypt plaintext of his or her choice. The attacker does not learn k, she is only allowed to use the encryption algorithm as a black box. Give an example of a plaintext that would

reveal the key to the Hill Cipher from Question 1, if you had access to Ek as in a chosen plaintext attack.