Computer Security :: Lessons :: Substitution
Caesar Cipher
A substitution cipher is one in which the plaintext characters are replaced by other characters to form the ciphertext. The Caesar Cipher, used by Julius Caesar to encrypt military messages, is an early example of a substitution cipher. The cipher involves replacing each letter of the alphabet with the letter three places after it. Examine the following example:
Plaintext: i came, i saw, i conquered.
Ciphertext: L FDPH, L VDZ, L FRQTXHUHG.
| i | c | a | m | e | , | i | s | a | w | , | i | c | o | n | q | u | e | r | e | d | . | |||||
| L | F | D | P | H | , | L | V | D | Z | , | L | F | R | Q | T | X | H | U | H | G | . |
Assuming each letter of the alphabet is assigned a number 0 through 25, the algorithm can be expressed using the following formula where the plaintext letter p is substituted with the ciphertext letter C:
C = f(3, p) = (p + 3) % 26
The formula can be generalized to use any shift from 0 to 25, which is represented by k below:
C = f(k, p) = (p + k) % 26
The decryption algorithm for the Caesar Cipher would be the following:
p = f(k, C) = (C - k) % 26
The Caesar Cipher is incredibly easy to break since there are only 25 possible keys. Below are the decryptions of all possible keys for our message above. The correct plaintext is trivial to spot.
| Transformation | Transformed text |
|---|---|
| ROT1 | G AYKC, G QYU, G AMLOSCPCB. |
| ROT2 | H BZLD, H RZV, H BNMPTDQDC. |
| ROT3 | I CAME, I SAW, I CONQUERED. |
| ROT4 | J DBNF, J TBX, J DPORVFSFE. |
| ROT5 | K ECOG, K UCY, K EQPSWGTGF. |
| ROT6 | L FDPH, L VDZ, L FRQTXHUHG. |
| ROT7 | M GEQI, M WEA, M GSRUYIVIH. |
| ROT8 | N HFRJ, N XFB, N HTSVZJWJI. |
| ROT9 | O IGSK, O YGC, O IUTWAKXKJ. |
| ROT10 | P JHTL, P ZHD, P JVUXBLYLK. |
| ROT11 | Q KIUM, Q AIE, Q KWVYCMZML. |
| ROT12 | R LJVN, R BJF, R LXWZDNANM. |
| ROT13 | S MKWO, S CKG, S MYXAEOBON. |
| ROT14 | T NLXP, T DLH, T NZYBFPCPO. |
| ROT15 | U OMYQ, U EMI, U OAZCGQDQP. |
| ROT16 | V PNZR, V FNJ, V PBADHRERQ. |
| ROT17 | W QOAS, W GOK, W QCBEISFSR. |
| ROT18 | X RPBT, X HPL, X RDCFJTGTS. |
| ROT19 | Y SQCU, Y IQM, Y SEDGKUHUT. |
| ROT20 | Z TRDV, Z JRN, Z TFEHLVIVU. |
| ROT21 | A USEW, A KSO, A UGFIMWJWV. |
| ROT22 | B VTFX, B LTP, B VHGJNXKXW. |
| ROT23 | C WUGY, C MUQ, C WIHKOYLYX. |
| ROT24 | D XVHZ, D NVR, D XJILPZMZY. |
| ROT25 | E YWIA, E OWS, E YKJMQANAZ. |
Monoalphabetic Ciphers
A permutation is a set of elements where each element from the set appears exactly once. As an example, there would be six permutations of {a, b, c}: abc, acb, bac, bca, cab, cba.
The Caesar Cipher worked by using a permutation of the alphabet, but that permutation was always in alphabetical order. What if you could use the letters of the alphabet in any order for the ciphertext? That would mean there would be 26! or 4 x 1026 possible keys. This is what is known as a monoalphabetic substitution cipher.
A monoalphabetic substitution cipher is harder to crack than a simple substitution cipher like Caesar, but it is not impossible. Consider the ciphertext below.
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
By examining the frequency of letters in the ciphertext, and knowing that the plaintext is in English, we can start to deduce the substitutions that were used. Below is a table of the frequencies of the letters in the ciphertext:
| P - 13.33% | H - 5.83% | F - 3.33% | B - 1.67% | C - 0% |
| Z - 11.67% | D - 5% | W - 3.33% | G 1.67% | K - 0% |
| S - 8.33% | E - 5% | Q - 2.5% | Y - 1.67% | L - 0% |
| U - 8.33% | V - 4.17% | T - 2.5% | I - 0.83% | N - 0% |
| O - 7.5% | X - 4.17% | A - 1.67% | J - 0.83% | R - 0% |
| M - 6.67% | ||||
Comparing the above results with the frequency of letters in English words it appears that p and z may map to e and t. From here, you can try filling in the remaining letters using guess-and-check like you are playing Wheel of Fortune. A more systematic method would be to look at two-letter combinations, or digrams. The most common digrams are th, he, in, en, nt, re, er, an, ti, and es. A combination of these approaches can lead you to the plaintext of the above cipher, which is "it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in moscow."
Playfair Cipher
The Playfair Cipher uses a five by five matrix of letters constructed using a keyword. The video below is a robust example of implementing Playfair.
Polyalphabetic Ciphers
A polyalphabetic substitution cipher uses different monoalphabetic substitutions as it proceeds through the plaintext message. An example of a polyalphabetic cipher is the Vigenère Cipher, which uses a key to determine how much each letter in the plaintext message is shifted to generate the ciphertext.
