Question 1 

Suppose we define 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(mod26)

b2=k3a1+k4a2(mod26)

b3=k1a3+k2a4(mod26)

b4=k3a3+k4a4(mod26)

b5=k1a5+k2a6(mod26)

b6=k3a5+k4a6(mod26)

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

Q1, Part a

Write down the system of equations in the unknowns k1,k2,k3 and k4 that you must solve to recover the key from the known plaintext-ciphertext pair?

Q1, Part b

What numbers in Z26 have multiplicative inverses mod 26?

Q1, Part c

Use your answer to Part b to solve for one of the key variables.

Q1, Part d

Recover the key used to produce the known plaintext pair.

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 Z26 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 Z626 (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 2=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 k1,k2,k3 or k4 used when encrypting SIXWIG. How many ciphertext characters would be affected?

uestion 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.

uestion 3

Compute the 3rd power of the polynomial x4+x+1 thought of as an element of GF(28) with irreducible polynomial P(x)=x8+x4+x3+x+1.

Question 4

The following describes a toy block cipher. The block size is 8 bits and the key size is 16 bits. A round will consist of the following.

1.The input is XORed with the first 8 bits of the round subkey

2. The input, considered as an element of GF(28) with irreducible P(x)=x8+x4+x3+x+1, is squared.

3.The left 4 bits of the block are swapped with the right 4 bits of the block. For example 0x4A becomes 0xA4.

There are two rounds. The key schedule is the following:

1.During the first round, the subkey is the first 8 bits of the key.

2.During the second round, the subkey is the second 8 bits of the key.

Question 4 part a

Use the above cipher with key k= 0x1111 to encrypt the block B= 0x88.

Question 5 part b

Use this block cipher to encrypt the plaintext x= 0x4A01 in OFB mode with IV=0x22 and key k=0x4444. Please show all intermediate steps.

Question 6

Suppose a plaintext message is exactly one block long and consists of all 0's. You produce a MAC tag using CBC-MAC with DES and an all-zero IV, and the key consisting of all zeros. A padding block will be appended to the plaintext which is 0x8 followed by enough 0's to fill out a second block, as per the CBC algorithm. What is the CBC-MAC tag?