Computer Science homework help. **Background: Historical Ciphers**

**Substitution Cipher**

*c = E(m)=(m+ key) ***mod 26**

*m= D(c)=(c-key) ***mod 26**

The values of *m* and *c* are available in the table below:

Plaintext characters | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |

Their values | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

**Example:**

Plaintext(m) |
Key |
Chiphertext (c) |

B | O | (1+14)%26 = 15 = P |

A | X | X |

N | W | J |

A | X | X |

N | W | J |

A | X | X |

**Caesar Cipher** or **Shift Cipher**

If a substitution cipher uses same “*n*” for all input symbols, then it is called **Caesar Cipher** or **Shift Cipher**.

Example:

Plaintext characters | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |

Ciphertext characters | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | A | B | C | D | E | F | G | H | I | J | K |

Every plaintext character has shifted 11 positions (i.e., n=11) |

**Affine Cipher**

**Affine Cipher** is similar to a Shift cipher that, before shifting a character by “*b*” places, multiplies it with a fixed number “a.”

*c = E(m)=(a.m+ b) ***mod 26**

*m= D(c)=a*^{-1}*(c-b) ***mod 26**

In Affine cipher, (a, b) pair constitute the key. It can be mathematically shown that the decryption formula works, only if “*a*” and 26 do not have a common factor other than “1” (i.e., GCD(a,26)=1). So, only a limited number of *a*’s are usable that include: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 (total 12 values). The possible values of “*b*” (=number of shifts) include 1 through 26 (or 0 through 25). So the total number of possible (*a*,*b*) key pair is 12×26=312. A brute force attack (trying all key pairs one by one) can easily defeat it.

**Problem A** (7 points)

Implement a brute force attack in any programming language to break the following Affine Cipher (The plaintext includes only capital English letters):

KYQNDUHVIHMIVKIKQVGTUHKGNC

Note: To find the modulo of a negative number, use the following rule:

-x mod n = n – (x mod n)

**Problem B **(8 points)

The cipher in the attached file is generated using a substitution cipher. Corresponding plaintext includes 28 symbols: English capital letters, spaces between the words, and period at the end of the sentences. Break this cipher using frequency analysis, and linguistic and contextual observations. (**No code is required, but analysis process has to be explained systematically**)

Above we used 26 capital letters “A-Z”, “.” and “space”. It may be difficult to find a frequency distribution just for those symbols. One option could be to take a large English paragraph from somewhere, say from a news website, convert all letters to capital form (MS word can do that), and remove everything except “A-Z”, “.” and “space”. Then compute frequency distribution for those 28 symbols. Don’t expect the frequency distributions for different paragraphs to match exactly; but high frequency set of symbols usually maintain their high frequencies, although their rank may slightly vary. Cryptanalysts also look for the presence of most frequent digraphs (such as: th, he, in, er, an ), or words (such as: the, be, to , of , and). Hope this helps.