Substitution ciphers - homophonic, playfair, polyalphabetic

Question 1

What is a homophonic substitution cipher?

Answer 1

For mono-alphabetic you can detect by frequency analysis on how often the letter appears in the plaintext SO countermeasure is to provide multiple substitutes (i.e., homophones) for a single letter to make frequency analysis more difficult.

Question 2

Mathematical formalisation of a homophonic substitution cipher?

Answer 2

1. To each a ∈ A associate a set H(a) of strings of t symbols, where H(a), a ∈ A are pairwise disjoint.
2. Replace each a with a randomly chosen string from H(a).
3. To decrypt a string c of t symbols, one must determine an a ∈ A such that c ∈ H(a).
4. The key for the cipher is the sets H(a).

Question 3

Why is cryptanalysis still possible with homophonic ciphers?

Answer 3

1. There are still multiple letter patterns in the ciphertext.
2. Homophonic is better than mono-alphabetic but it is not enough.

Question 4

What are the two principal methods used in substitution ciphers that lessen the extent to which the structure of plaintext survives in ciphertext?

Answer 4

1. encrypt multiple letters of the plaintext - PLAYFAIR

2. use multiple cipher alphabets (polyalphabetic substitution) - VIGENERE

Question 5

What is the playfair cipher?

Answer 5

1. Uses a 5 x 5 matrix of letters constructed using a keyword ( do not include duplicates)
2. Fill in the remaining of the matrix with the rest of the letters in alphabetical order (I/J in one cell)
3. Plaintext is encrypted two letters at a time - if there is a repeated letter in the pair - use a filler X (“BALLOON” ; “BA LX LO ON”) - process the plaintext as you go along. You can use the filler even at the end to make sure the entire plaintext is separated in pairs.
4. Both letters in the pair are in the saw row -> replace with the letter to the right/ wrap around the same row.
5. Both letters in the pair are in the same column -> replace it with the letter below it/ wrap around the same column.
6. If both the letters in the pair are not in the same row and same column -> replace each letter by the letter in the same row and in the column of the other letter of the pair.

Question 6

How to decrypt the playfair cipher?

Answer 6

1. Both letters in the pair are in the saw row -> replace with the letter to the left/ wrap around the same row.
2. Both letters in the pair are in the same column -> replace it with the letter above it/ wrap around the same column.
3. Drop the fillers X so that the plaintext makes sense.

Question 7

What is the security of the playfair cipher?

Answer 7

Security MUCH IMPROVED than mono-alphabetic

1. 26 (plaintext) x 26(ciphertext) = 676 diagrams vs. 26 letters.
2. Would need a 676 entry frequency table to analyse, and correspondingly more ciphertext.
3. Breaking it is still relatively easy
   a. a lot of the structure is still preserved/ intact.
   b. a few 100 letters of ciphertext are generally sufficient

Question 8

What is a polyalphabetic substitution cipher?

Answer 8

1. DIFFERENT MONO-ALPHABETIC SUBSTITUTIONS AS ONE PROCEEDS THROUGH THE PLAINTEXT MESSAGE.

Question 9

What are the two features of polyalphabetic substitution ciphers?

Answer 9

1. a set of related mono-alphabetic substitution rules is used.
2. a key determines which particular rule is chosen for a given transformation.

Question 10

Explain the Vigenere cipher?

Answer 10

1. Set of related monoalphabetic substitution rules consists of the 26 Caesar ciphers with shifts of 0 through 25.
2. Each cipher is denoted by a key letter, which is the ciphertext letter that substitutes for the plaintext letter A.
3. Therefore, a Caesar cipher with a shift of 3 is denoted by key value D

Question 11

What are the main details of the Vigenere cipher?

Answer 11

1. Assume:
   a. a sequence of plaintext letters P = p0, p1, p2, . . . , pn−1,
   b. a key consisting of the sequence of letters K = k0, k1, k2, . . . , km−1.
   Typically m < n.
2. Sequence of ciphertext letters C = C0, C1, C2, . . . , Cn−1:
   C = C0, C1, C2, . . . , Cn−1
   = E(K, P)
   = E((k0, k1, k2, . . . , km−1),(p0, p1, p2, . . . , pn−1)) = (p0 + k0) mod 26, (p1 + k1) mod 26, . . . ,(pm−1 + km−1) mod 26, (pm + k0) mod 26, (pm+1 + k1) mod 26,. . .(p2m−1 + km−1) mod 26, . . .

For each letter in the plaintext and the key:
ENCRYPTION: Ci = (pi + ki) mod 26
DECRYPTION: pi = (Ci − ki) mod 26

3. First letter of key (k0) is added to the first letter of plaintext P (p0) -> (k0 + p0) mod 26
   This carries on until the entire plaintext is encrypted as shown above in step 2.
4. The KEY HAS TO BE AS LONG AS THE MESSAGE. If not, repeat the key until it is as long as the message.

Question 12

What are the strengths of the Vigenere cipher?

Answer 12

1. There are multiple ciphertext letters for each plaintext characters, one for each unique letter in the keyword/ key.
2. Due to this, letter frequency info is hidden.
3. HOWEVER, not all knowledge of the plaintext structure is lost BUT better than playfair cipher.