Classical Ciphers & Cryptanalysis

Question 1

How do you crack a transposition cipher?

Answer 1

Run first-order statistics on it and you will find them to be identical to the frequency distributions of the language.

Question 2

How do you crack a simple substitution cipher?

Answer 2

Look at the letter frequency distribution. If the frequency distribution looks the same as that of regular English, except you just have to rename all the letters (i.e. it is isomorphic), then you know you have a simple substitution cipher.

Question 3

What is a Playfair cipher?

Answer 3

• A Playfair cipher puts each letter into a 5 x 5 grid (so you only get 25 letters). (For English, I and J are often considered to be the same thing for this cipher.)
• Adjacent plaintext characters are paired.
• Characters (p1,p2) are replaced by (c3,c4) according to a bunch of rules with the matrix.

Question 4

What is a homophonic substitution cipher?

Answer 4

• One plaintext character can map to multiple ciphertext characters.
• This is like simple substitution. You are still going to have the expansion problem, where the ciphertext is much bigger than the plaintext message. But also, this still turns out to be fairly weak, just like all the other simple, classical ciphers.

Question 5

What are cryptographic codes?

Answer 5

• Cryptographic codes operate on linguistic units, such as words, groups of words, or phrases, and substitutes these by designated words, letter groups, or number groups called codegroups.
• In order to translate one of these messages, you need a codebook, which tells you how to translate from one phrase to another.
• This makes cryptographic codes difficult to crack.
• The downside of this, though, is that once compromised, the entire code becomes useless. (You can’t just change your key to make it secure again, like other ciphers.)

Question 6

What is a polyalphabetic substitution cipher?

Answer 6

A **polyalphabetic substitution cipher** uses different
 substitution mappings (called multiple alphabets) on various portions of the plaintext.

Question 7

How does a simple Vigenere cipher work?

Answer 7

• The simple Vigenere cipher uses t shift ciphers, defined by t shift values k_i.

Question 8

What is a running-key Vigenere cipher?

Answer 8

The running-key Vigenere cipher uses a key that is the same length as the entire plaintext message, (making it invulnerable to the Kasiski Method, or other attacks that try to determine the block size).

Question 9

What is a rotor and how does it work?

Answer 9

• A rotor is a mechanical device consisting of a set of several code wheels, and is used for encryption and decryption.
• Each code wheel performs a monoalphabetic substitution cipher.
• After a character is fed through, the wheels rotate according to some pattern, effectively changing the monoalphabetic substitution cipher being used.
• When the wheel orientations repeat after t times, you have a block size of t.

Question 10

Define unicity distance.

Answer 10

The unicity distance of a cipher is the minimum amount of ciphertext (in number of characters) required to allow a
computationally unlimited adversary to recover the unique encryption key.

Question 11

What is the random cipher model?

Answer 11

• The random cipher model is a theoretical model. It says that when you try to decrypt something using a particular key, you will get a totally random plaintext.
• This cipher is not useful in practice, since it is random in nature. However, we can use it to derive interesting equations that help us understand the limitations of the block cipher.

Question 12

How do you crack a polyalphabetic substitution cipher?

Answer 12

Figure out the period t (i.e. the block size), and then just treat it like you’re cracking a monoalphabetic substitution cipher for each of the ciphers. That is, for each index of the block, compare the letters with language statistics to determine what the ciphertext letters map to.

Question 13

Describe how the Method of Kasiski works.

Answer 13

• Search for matching substrings within the ciphertext, and whenever you find one, record the distance between them.
• Increase the length of the substrings you are searching for until you find no matches, then stop.
• Finally, look at all the distances between matches that you recorded, and try to find the least common factor between all of them. This is probably a multiple of the block size t.

Question 14

Describe how the index of coincidences auto-correlation method works.

Answer 14

• Shift the ciphertext over, starting with t = 1 and going up to L - t.
• Compare the shifted ciphertext with the original, and count the number of letter matches at each index.
• Take note of when there is a big spike in the match count. This will likely happen at multiples of the real block size t.