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.
