The ciphertext YIFZMA was encrypted by a Hill cipher with matrix $\left(\begin{array}{cc}9& 13\\ 2& 3\end{array}\right)$. Find the plaintext.

The matrix $\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ mod 26 is not suitable for the matrix in a Hill cipher. Why?

The ciphertext text GEZXDS was encrypted by a Hill cipher with a $2\times 2$ matrix. The plaintext is solved. Find the encryption matrix $M$.

Consider the following combination of Hill and Vigenère ciphers: The key consists of three $2\times 2$ matrices, $M_1$, $M_2$, $M_3$. The plaintext letters are represented as integers mod 26. The first two are encrypted by $M_1$, the next two by $M_2$, the 5th and 6th by $M_3$. This is repeated cyclically, as in the Vigenère cipher. Explain how to do a chosen plaintext attack on this system. Assume that you know that three $2\times 2$ matrices are being used. State explicitly what plaintexts you would use and how you would use the outputs.

Eve captures Bob’s Hill cipher machine, which uses a 2-by-2 matrix $M$ mod 26. She tries a chosen plaintext attack. She finds that the plaintext $ba$ encrypts to $HC$ and the plaintext $zz$ encrypts to $GT$. What is the matrix $M$.

Alice uses a Hill cipher with a $3\times 3$ matrix $M$ that is invertible mod 26. Describe a chosen plaintext attack that will yield the entries of the matrix $M$. Explicitly say what plaintexts you will use.

1. The ciphertext text ELNI was encrypted by a Hill cipher with a $2\times 2$ matrix. The plaintext is dont. Find the encryption matrix.

2. Suppose the ciphertext is ELNK and the plaintext is still dont. Find the encryption matrix. Note that the second column of the matrix is changed. This shows that the entire second column of the encryption matrix is involved in obtaining the last character of the ciphertext.

Suppose the matrix $\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right)$ is used for an encryption matrix in a Hill cipher. Find two plaintexts that encrypt to the same ciphertext.

Let $a\text{,}b\text{,}c\text{,}d\text{,}e\text{,}f$ be integers mod 26. Consider the following combination of the Hill and affine ciphers: Represent a block of plaintext as a pair $(x\text{,}y)$ mod 26. The corresponding ciphertext $(u\text{,}v)$ is

Describe how to carry out a chosen plaintext attack on this system (with the goal of finding the key $a\text{,}b\text{,}c\text{,}d\text{,}e\text{,}f$). You should state explicitly what plaintexts you choose and how to recover the key.

Alice is sending a message to Bob using a Hill cipher with a $2\times 2$ matrix. In fact, Alice is bored and her plaintext consists of the letter $a$ repeated a few hundred times. Eve knows what system is being used, but not the key, and intercepts the ciphertext. State how Eve will recognize that the plaintext is one repeated letter and decide whether or not Eve can deduce the letter and/or the key. (Note: The solution very much depends on the fact that the repeated letter is $a$, rather than $b\text{,}c\text{,}\dots$.)

Let $E_K$ denote encryption (for some cryptosystem) with key $K$. Suppose that there are $2^{35}$ possible keys $K$. Alice decides to encrypt a message $m$ as follows:

She chooses two keys $K$ and $L$ and double encrypts by computing

to get the ciphertext $c$. Suppose Eve knows Alice’s method of encryption (but not $K$ and $L$) and has at least two plaintext–ciphertext pairs. Describe a method that is guaranteed to yield the correct $K$ and $L$ (and maybe a very small additional set of incorrect pairs). Be explicit enough to say why you are using at least two plaintext–ciphertext pairs. Eve may do up to $2^{50}$ computations.

Alice and Bob are arguing about which method of multiple encryption they should use. Alice wants to choose keys $K_1$ and $K_2$ and triple encrypt a message $m$ as $c=E_{K_1}(E_{K_2}(E_{K_1}(m)))$. Bob wants to encrypt $m$ as $c=E_{K_1}(E_{K_1}(E_{K_2}(E_{K_2}(m))))$. Which method is more secure? Describe in detail an attack on the weaker encryption method.

Alice and Bob are trying to implement triple encryption. Let $E_K$ denote DES encryption with key $K$ and let $D_K$ denote decryption.

1. Alice chooses two keys, $K_1$ and $K_2$, and encrypts using the formula $c=E_{K_1}(D_{K_2}(E_{K_1}(m)))$. Bob chooses two keys, $K_1$ and $K_2$, and encrypts using the formula $c=E_{K_1}(E_{K_2}(E_{K_2}(m)))$. One of these methods is more secure than the other. Say which one is weaker and explicitly give the steps that can be used to attack the weaker system. You may assume that you know ten plaintext–ciphertext pairs.

2. What is the advantage of using $D_{K_2}$ instead of $E_{K_2}$ in Alice’s version?

Suppose $E^1$ and $E^2$ are two encryption methods. Let $K_1$ and $K_2$ be keys and consider the double encryption

1. Suppose you know a plaintext–ciphertext pair. Show how to perform a meet-in-the-middle attack on this double encryption.

2. An affine encryption given by $x\mapsto \alpha x+\beta (\text{mod}26)$ can be regarded as a double encryption, where one encryption is multiplying the plaintext by $\alpha$ and the other is a shift by $\beta$. Assume that you have a plaintext and ciphertext that are long enough that $\alpha$ and $\beta$ are unique. Show that the meet-in-the-middle attack from part (a) takes at most 38 steps (not including the comparisons between the lists). Note that this is much faster than a brute force search through all 312 keys.

Let $E_K$ denote DES encryption with key $K$. Suppose there is a public database $Y$ consisting of ${10}^{10}$ DES keys and there is another public database $Z$ of ${10}^{10}$ binary strings of length 64. Alice has five messages $m_1\text{,}{m}_2\text{,}\dots \text{,}{m}_5$. She chooses a key $K$ from $Y$ and a string $B$ from $Z$. She encrypts each message $m$ by computing $c=E_K(m)\oplus B$. She uses the same $K$ and $B$ for each of the messages. She shows the five plaintext–ciphertext pairs $(m_i\text{,}{c}_i)$ to Eve and challenges Eve to find $K$ and $B$. Alice knows that Eve’s computer can do only ${10}^{15}$ calculations, and there are ${10}^{20}$ pairs $(K\text{,}B)$, so Alice thinks that Eve cannot find the correct pair. However, Eve has taken a crypto course. Show how she can find the $K$ and $B$ that Alice used. You must state explicitly what Eve does. Statements such as “Eve makes a list” are not sufficient; you must include what is on the lists and how long they are.

Alice wants to encrypt her messages securely, but she can afford only an encryption machine that uses a 25-bit key. To increase security, she chooses 4 keys $K_1\text{,}{K}_2\text{,}{K}_3\text{,}{K}_4$ and encrypts four times:

Eve finds several plaintext–ciphertext pairs $(m\text{,}c)$ encrypted with this set of keys. Describe how she can find (with high probability) the keys $K_1\text{,}{K}_2\text{,}{K}_3\text{,}{K}_4$. (For this problem, assume that Eve can do at most $2^{60}$ computations, so she cannot try all $2^{100}$ combinations of keys.) (Note: If you use only one of the plaintext–ciphertext pairs in your solution, you probably have not done enough to determine the keys.)

Show that the decryption procedures given for the CBC and CFB modes actually perform the desired decryptions.

Consider the following simplified version of the CFB mode. The plaintext is broken into 32-bit pieces: $P=[P_1\text{,}{P}_2\text{,}\dots ]$, where each $P_j$ has 32 bits, rather than the eight bits used in CFB. Encryption proceeds as follows. An initial 64-bit $X_1$ is chosen. Then for $j=1\text{,}2\text{,}3\text{,}\dots$, the following is performed:

where $L_{32}(X)$ denotes the 32 leftmost bits of $X$, $R_{32}(X)$ denotes the rightmost 32 bits of $X$, and $X\parallel Y$ denotes the string obtained by writing $X$ followed by $Y$.

1. Find the decryption algorithm.

2. The ciphertext consists of 32-bit blocks $C_1\text{,}{C}_2\text{,}{C}_3\text{,}{C}_4\text{,}\dots$. Suppose that a transmission error causes $C_1$ to be received as ${\tilde{C}}_1\ne C_1$, but that $C_2\text{,}{C}_3\text{,}{C}_4\text{,}\dots$ are received correctly. This corrupted ciphertext is then decrypted to yield plaintext blocks ${\tilde{P}}_1\text{,}{\tilde{P}}_2\text{,}\dots$. Show that ${\tilde{P}}_1\ne P_1$, but that ${\tilde{P}}_i=P_i$ for all $i\ge 4$. Therefore, the error affects only three blocks of the decryption.

The cipher block chaining (CBC) mode has the property that it recovers from errors in ciphertext blocks. Show that if an error occurs in the transmission of a block $C_j$, but all the other blocks are transmitted correctly, then this affects only two blocks of the decryption. Which two blocks?

In CTR mode, the initial $X_1$ has 64 bits and is sent unencrypted to the receiver. (a) If $X_1$ is chosen randomly every time a message is encrypted, approximately how many messages must be sent in order for there to be a good chance that two messages use the same $X_1$ ? (b) What could go wrong if the same $X_1$ is used for two different messages? (Assume that the key $K$ is not changed.)

Suppose that in CBC mode, the final plaintext block $P_n$ is incomplete; that is, its length $M$ is less than the usual block size of, say, 64 bits. Often, this last block is padded with a binary string to make it have full length. Another method that can be used is called ciphertext stealing, as follows:

1. Compute $Y_{n-1}=E_K(C_{n-2}\oplus P_{n-1})$.

2. Compute $C_n=L_M(Y_{n-1})$, where $L_M$ means we take the leftmost $M$ bits.

3. Compute $C_{n-1}=E_K\left((P_n||0^{64-M})\oplus Y_{n-1}\right)$, where $P_n||0^{64-M}$ denotes $P_n$ with enough 0s appended to give it the length of a full 64-bit block.

4. The ciphertext is $C_1{C}_2\cdots C_{n-1}{C}_n$. Therefore, the ciphertext has the same length as the plaintext.

Suppose you receive a message that used this ciphertext stealing for the final blocks (the ciphertext blocks $C_1\text{,}\dots C_{n-2}$ were computed in the usual way for CBC). Show how to decrypt the ciphertext (you have the same key as the sender).

Suppose Alice has a block cipher with $2^{50}$ keys, Bob has one with $2^{40}$ keys, and Carla has one with $2^{30}$ keys. The only known way to break single encryption with each system is by brute force, namely trying all keys. Alice uses her system with single encryption. But Bob uses his with double encryption, and Carla uses hers with triple encryption. Who has the most secure system? Who has the weakest? (Assume that double and triple encryption do not reduce to using single or double encryption, respectively. Also, assume that some plaintext-ciphertext pairs are available for Alice’s single encryption, Bob’s double encryption, and Carla’s triple encryption.)