The ciphertext YIFZMA was encrypted by a Hill cipher with matrix . Find the plaintext.
The matrix 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 matrix. The plaintext is solved. Find the encryption matrix .
Consider the following combination of Hill and Vigenère ciphers: The key consists of three matrices, , , . The plaintext letters are represented as integers mod 26. The first two are encrypted by , the next two by , the 5th and 6th by . 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 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 mod 26. She tries a chosen plaintext attack. She finds that the plaintext encrypts to and the plaintext encrypts to . What is the matrix .
Alice uses a Hill cipher with a matrix that is invertible mod 26. Describe a chosen plaintext attack that will yield the entries of the matrix . Explicitly say what plaintexts you will use.
The ciphertext text ELNI was encrypted by a Hill cipher with a matrix. The plaintext is dont. Find the encryption matrix.
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 is used for an encryption matrix in a Hill cipher. Find two plaintexts that encrypt to the same ciphertext.
Let be integers mod 26. Consider the following combination of the Hill and affine ciphers: Represent a block of plaintext as a pair mod 26. The corresponding ciphertext is
Describe how to carry out a chosen plaintext attack on this system (with the goal of finding the key ). 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 matrix. In fact, Alice is bored and her plaintext consists of the letter 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 , rather than .)
Let denote encryption (for some cryptosystem) with key . Suppose that there are possible keys . Alice decides to encrypt a message as follows:
She chooses two keys and and double encrypts by computing
to get the ciphertext . Suppose Eve knows Alice’s method of encryption (but not and ) and has at least two plaintext–ciphertext pairs. Describe a method that is guaranteed to yield the correct and (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 computations.
Alice and Bob are arguing about which method of multiple encryption they should use. Alice wants to choose keys and and triple encrypt a message as . Bob wants to encrypt as . 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 denote DES encryption with key and let denote decryption.
Alice chooses two keys, and , and encrypts using the formula . Bob chooses two keys, and , and encrypts using the formula . 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.
What is the advantage of using instead of in Alice’s version?
Suppose and are two encryption methods. Let and be keys and consider the double encryption
Suppose you know a plaintext–ciphertext pair. Show how to perform a meet-in-the-middle attack on this double encryption.
An affine encryption given by can be regarded as a double encryption, where one encryption is multiplying the plaintext by and the other is a shift by . Assume that you have a plaintext and ciphertext that are long enough that and 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 denote DES encryption with key . Suppose there is a public database consisting of DES keys and there is another public database of binary strings of length 64. Alice has five messages . She chooses a key from and a string from . She encrypts each message by computing . She uses the same and for each of the messages. She shows the five plaintext–ciphertext pairs to Eve and challenges Eve to find and . Alice knows that Eve’s computer can do only calculations, and there are pairs , so Alice thinks that Eve cannot find the correct pair. However, Eve has taken a crypto course. Show how she can find the and 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 and encrypts four times:
Eve finds several plaintext–ciphertext pairs encrypted with this set of keys. Describe how she can find (with high probability) the keys . (For this problem, assume that Eve can do at most computations, so she cannot try all 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: , where each has 32 bits, rather than the eight bits used in CFB. Encryption proceeds as follows. An initial 64-bit is chosen. Then for , the following is performed:
where denotes the 32 leftmost bits of , denotes the rightmost 32 bits of , and denotes the string obtained by writing followed by .
Find the decryption algorithm.
The ciphertext consists of 32-bit blocks . Suppose that a transmission error causes to be received as , but that are received correctly. This corrupted ciphertext is then decrypted to yield plaintext blocks . Show that , but that for all . 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 , 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 has 64 bits and is sent unencrypted to the receiver. (a) If 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 ? (b) What could go wrong if the same is used for two different messages? (Assume that the key is not changed.)
Suppose that in CBC mode, the final plaintext block is incomplete; that is, its length 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:
Compute .
Compute , where means we take the leftmost bits.
Compute , where denotes with enough 0s appended to give it the length of a full 64-bit block.
The ciphertext is . 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 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 keys, Bob has one with keys, and Carla has one with 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.)