mt.sagews

Midterm

%md

##### Instructions

1. Please answer the following questions as well as you can.  You are free to use any resources to help you answer the problems.  You are free to write code to help you answer problems.
1. Please do not collaborate.
1. Please put all answers in this document.
1. You can use Markdown (I will show how in class) or upload a legible image of work done on paper.
1. To make a cell a Markdown cell, put `%md` as the first line.
1. To enter a cell press `SHIFT-ENTER` while the cursor is in the cell.
1. This is due in one week, on Tuesday 10/31.
1. An updated schedule is on Piazza if you have concerns about scheduling.

Instructions

1. Please answer the following questions as well as you can. You are free to use any resources to help you answer the problems. You are free to write code to help you answer problems.

2. Please do not collaborate.

3. Please put all answers in this document.

4. You can use Markdown (I will show how in class) or upload a legible image of work done on paper.

5. To make a cell a Markdown cell, put %md as the first line.

6. To enter a cell press SHIFT-ENTER while the cursor is in the cell.

7. This is due in one week, on Tuesday 10/31.

8. An updated schedule is on Piazza if you have concerns about scheduling.

Question 1

Suppose we define an encryption scheme as follows. The key will be four elements $k_1,k_2,k_3,$ and $k_4$ in $\mathbb{Z}_{26}$. The message space will be sequences of elements of $\mathbb{Z}_{26}$ of length 6. The ciphertext space will be the same as the message space.

The encryption algorithm is the following. Given a key $k_1,k_2,k_3$ and $k_4$ and a message $\langle a_1,a_2,a_3,a_4,a_5,a_6 \rangle$, the corresponding ciphertext is $\langle b_1,b_2,b_3,b_4,b_5,b_6 \rangle$, where:

$$\begin{align} b_1 &= k_1a_1 + k_2a_2 \,(mod\, 26) \\ b_2 &= k_3a_1 + k_4a_2 \,(mod\, 26) \\ b_3 &= k_1a_3 + k_2a_4 \,(mod\, 26) \\ b_4 &= k_3a_3 + k_4a_4 \,(mod\, 26) \\ b_5 &= k_1a_5 + k_2a_6 \,(mod\, 26) \\ b_6 &= k_3a_5 + k_4a_6 \,(mod\, 26) \end{align}$$

Suppose you know that the message SIXWIG (thought of as a sequence of numbers in $\mathbb{Z}_{26}$) corresponds to the ciphertext IGPXUY.

Q1, Part $a$

Write down the system of equations in the unknowns $k_1,k_2,k_3$ and $k_4$ that you must solve to recover the key from the known plaintext-ciphertext pair.

Plaintext(a1a2a3a4a5a6) = (SIXWIG)

Ciphertext(b1b2b3b4b5b6)=(IGPXUY)

I = k1S + k2I (mod 26)
G = k3S + k4I (mod 26)
P = k1X + k2W (mod 26)
X = k3X + k4W (mod 26)
U = k1I + k2G (mod 26)
Y = k3I + k4G (mod 26)

Q1, Part $b$

What numbers in $\mathbb{Z}_{26}$ have multiplicative inverses mod 26?

Invertible elements of Z26: {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}

Q1, Part $c$

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

Q1, Part $d$ (BONUS)

Recover the key used to produce the known plaintext pair.

Answer here (with work!)

Question 2

You may know that the cipher described in Question 1 is the Hill Cipher and that the key elements $k_1,k_2,k_3$ and $k_4$. However let us ignore this fact and suppose that any four elements in $\mathbb{Z}_{26}$ can be a key.

Question 2, part $a$

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

26^4 = 456976 keys

Question 2, part $b$

Suppose we regard the Hill Cipher as described in Question 1 as a block cipher. The blocks are elements of $\mathbb{Z}_{26}^6$ (i.e. sequences of letters of length 6). How many distinct blocks are there?

we have a1, a2, a3, a4, a5 and a6 a total of 6 letters
So the total distinct blocks are: 26^6 = 308915776

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) = \frac{\# 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?

According to the formula above, E(F) = 456976/308915776 = 0.0015

Question 2, part $d$

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

2^k = 456976
log (2)456976 = k
k = 18.8

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?

b1 = k1a1 + k2a2 (mod 26)
b2 = k3a1 + k4a2 (mod 26)

If we changed one of the plaintext characters in plaintext SIXWIG, 2 ciphertext characters would be affected, such as b1 and b2..

Question 2, part $f$

Suppose you changed one of the key characters $k_1,k_2,k_3$ or $k_4$ used when encrypting SIXWIG. How many ciphertext characters would be affected?

b1 = k1a1 + k2a2 (mod 26)
b3 = k1a3 + k2a4 (mod 26)
b5 = k1a5 + k2a6 (mod 26)

If we changed one of the key characters used when encrypting SIXWIG, three ciphertext characters would be affected, such as b1,b3,b5..

Question 2, part $g$

A chosen plaintext attack is a threat model in which the attacker is allowed to use the encryption algorithm $E_k$ 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 $E_k$ as in a chosen plaintext attack.

b1 = k1a1+k2a2 (mod 26)
b1 = 1(a1)+0(a2) (mod 26)
b1 = a1

Question 3

Compute the 3rd power of the polynomial $x^4+x+1$ thought of as an element of GF($2^8$) with irreducible polynomial $P(x) = x^8+x^4+x^3+x+1$.

Answer here

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(2^8$) with irreducible $P(x)=x^8+x^4+x^3+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.

anyoung

%md

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

Answer here

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?