Historical Cryptography Ciphers

Like most technologies, encryption has evolved throughout the years from simple origins. While modern encryption relies on complex computational operations, older encryption ciphers were rudimentary and easy to break. Regardless of each cipher’s strength, all encryption methods share a common goal, to encode a readable “plaintext” message in a way that prevents unauthorized individuals from reading it. Let’s explore the history of encryption and some historical ciphers that were used to hide messages from prying eyes.

Substitution Ciphers

Caesar Cipher

The Caesar cipher, also called a Caesar shift, gets its name from Julius Caesar, who occasionally used this encoding method in his own private messages. As one of the most basic encryption techniques, the Caesar cipher works by replacing each letter in the original plaintext message with a different letter based off a fixed shift of the alphabet. For example, let’s say we want to encode a secret message using a Caesar shift of 7 to the right. First, we create our substitution table by printing the alphabet followed by the alphabet shifted 7 places to the right.Original: ABCDEFGHIJKLMNOPQRSTUVWXYZ Shifted:  TUVWXYZABCDEFGHIJKLMNOPQRSNext, we take each letter of our plaintext message and replace it with its corresponding letter in the shifted alphabet.Plaintext:  THISISASECRETMESSAGEBURNAFTERREADING Ciphertext: MABLBLTLXVKXMFXLLTZXUNKGTYMXKKXTWBGZTo revert the encoded message back into its readable plaintext form, the recipient must re-create the substitution table using the appropriate shift and then substitute each encoded character with its original character, according to the shift. One take on the Caesar cipher that has reached internet stardom is ROT13, which equates to a rotation (or shift) of 13 places. Because the basic English alphabet is 26 characters long, ROT13 is its own inverse, allowing the same algorithm to both encode and decode messages.

Vigenère Cipher

A Vigenère cipher uses a table consisting of different Caesar shifts in sequence and a key to encode a message across several rows of the table. By using different Caesar shifts for different characters in the message, the Vigenère cipher makes decoding the ciphertext using frequency analysis much more difficult. For example, to encode a message, we must first choose a word or phrase to use as a key, and then repeat it until it matches the length of the plaintext message. In this example, our key is “FIREWALL”.Plaintext:  THISISASECRETMESSAGEBURNAFTERREADING KEY:        FIREWALLFIREWALLFIREWALLFIREWALLFIRETo generate the encoded ciphertext, we match the plaintext character to a column and the corresponding key letter to a row in the Vigenère table. For example, the first letter in our plaintext is “T” and its corresponding key is “F”. Row “F”, column “T” would give us the ciphertext character “Y”. This process is repeated sequentially for the entirety of the plaintext.Plaintext:  THISISASECRETMESSAGEBURNAFTERREADING KEY:        FIREWALLFIREWALLFIREWALLFIREWALLFIRE Ciphertext: YPZWESLDJKIIPMPDXIXIXUCYFNKINRPLIQEKTo decode each character in the message, the recipient again selects the row indicated by the key character, locates the ciphertext character within the row, and notes the column. For example, to decode the last character in the message above, you would go to row “E” of the table and locate character “K” which maps to column “G”, the plaintext character.

Playfair Cipher

The Playfair cipher is a diagraph substitution cipher. Instead of encoding a message by replacing individual characters, it replaces them in pairs. To encode a message, the Playfair cipher uses a keyword to generate a 5 by 5 encoding table and then follows 4 rules to encode digrams (pairs of characters) using the table. To create a Playfair cipher table, you use a keyword to fill spaces in a 5 by 5 table top to bottom, left to right. Any duplicate letters from the keyword are omitted when filling out the table. Furthermore, the letters I and J are placed in the same space to shrink the 26-character alphabet into a 25-character table. The remaining spaces in the table are filled with the rest of the letters of the alphabet in order. For example, let’s assume our keyword is “Picture Frame”. To create a Playfair cipher table, we would begin by writing “Picture Frame” in a 5 by 5 table, omitting repeated characters. Note in the example table below, the “R” and “E” from “Frame” are skipped because they were already placed in the table. After writing out the keyword, the rest of the spaces in the table are filled out with the remaining letters of the alphabet. In our example, “J” is skipped when filling in the rest of the table because it shares a space with “I” from the keyword. After generating the table, we then prepare our plaintext message for encoding by splitting it into digrams (groups of 2 letters). For example, the secret message “Kill the spy” becomes “KI LL TH ES PY”. Next, we encode the message by mapping the digrams to the table and following 4 simple rules.

1. If both letters in the digram are the same, add an X after the first letter to split them into a new digram and continue encoding the message.
2. If they appear in the same row of the table, shift the characters one position to the right, wrapping around the table if needed.
3. If they appear in the same column, shift the characters down one position, wrapping around the table if needed.
4. If they form the corners of a rectangle, replace them with the characters forming the opposing corners of the rectangle, left to right.

These rules are much easier to understand with an example. To encode the message “KI LL TH ES PY” using the table we created earlier, we begin by look at the first digram, “KI”, and map it to the table. The letters “K” and “I” form opposing corners of a rectangle, which means rule 4 applies. We replace “K” with the opposite corner in its same row, in this case “D”. “I” meanwhile is replaced with “U”. The next digram contains repeated letters, “LL”. We use rule 1 to split this digram by adding “X” to the first letter, giving us a new digram to encode, “LX”. The letters “L” and “X” also form the corners of a rectangle, which means we replace them with the opposing corners to form the encoded digram “OV.” Because we split the previous digram, our third digram is now “LT.” “L” and “T” form opposing corners of another rectangle, which means our encoded digram is “QP.” Continuing through the message, “HE” forms yet another rectangle in our table and gives us “DA” for the encoded digram. The next digram “SP” forms a rectangle giving us “LU” as the encoded digram. Finally, because our secret message only has one character left, “Y”, we add “X” to form the digram “YX”. The characters “Y” and “X” appear in the same row of our table which means rule 2 applies. To form our final encoded digram, we shift “Y” and “X” each one character to the right, giving us “ZY”. Completed, our encoded message should look like this.Plaintext:  KILL THE SPY Digrams:    KI LX LT HE SP YX Ciphertext: DU OV QP DA LU ZYTo decrypt the message, the recipient would build out the same table using the given keyword and then use the inverse of the last 3 rules (shift left instead of right, up instead of down, etc.) to decode the ciphertext. They would then remove any “X”s that don’t make sense once all digrams are decoded.

Transposition Ciphers

Rail Fence Cipher

The rail fence cipher is a simple transposition cipher where plaintext characters are re-arranged instead of replaced to encode a message. The rail fence cipher encodes a message by writing it down and up diagonally over successive “rails”, or rows, in an imaginary fence. For example, the secret message “THIS IS A SECRET MESSAGE” encoded over 4 rails would look like this.T . . . . . A . . . . . T . . . . . G . . H . . . S . S . . . E . M . . . A . E . . I . I . . . E . R . . . E . S . . . . . . S . . . . . C . . . . . S . . . .We then create the ciphertext by reading off characters left to right, top to bottom. For our example message, the cipher text becomes:TATGHSSEMAEIIERESSCSDecoding a message only requires knowing the number of “rails” used to encode the message and solving a simple math equation to determine the spacing between letters. To decode the ciphertext, you first determine the size of the “cycle”, that is the number of characters in one full movement down and up the “fence”. For a ciphertext created using 4 “rails”, the cycle is 6 characters long. The size of the cycle for any other number of rails can be calculated using the equations [Size] = ([rails] x 2) – 2. After calculating the size of the cycle, divide the number of characters in the ciphertext by the size of the cycle to find the number of cycles used to encode the message. Our ciphertext for example is 20 characters long, which gives us 3 full cycles and a partial cycle of 2 characters when divided by a cycle size of 6. Finally, we use this information to write the ciphertext back out on the “fence” for decoding. In our example, we calculated 3 full cycles and one partial cycle of 2 characters, which means the top row of the fence should consist of the first 4 characters of our ciphertext (3 cycles + the start of the partial cycle.)T . . . . . A . . . . . T . . . . . G .The second row uses the next 7 characters of our ciphertext (2x the number of cycles + the second extra character from the partial cycle.)\T . . . . . A . . . . . T . . . . . G . . H . . . S . S . . . E . M . . . A . EThe third row uses the next 6 characters, that is 2x the number of cycles.T . . . . . A . . . . . T . . . . . G . . H . . . S . S . . . E . M . . . A . E . . I . I. . . . E  R . . . E . S . . .And the final row uses the last three characters, one for each full cycle.T . . . . . A . . . . . T . . . . . G . . H . . . S . S . . . E . M . . . A . E . . I . I . . . E . R . . . E . S . . . . . . S . . . . . C . . . . . S . . . .Finally you can read the decoded message by following the text pattern down and up the “fence”.

Route Cipher

The route cipher is another very simple transposition cipher. To use the route cipher, you write out your plaintext message into a grid of arbitrary dimensions. For example, “THIS IS A SECRET MESSAGE BURN AFTER READING” might be written out:TIETSBARD HSCMAUFRI IAREGRTEN SSESENEAGYou then encode the message by following a specific pattern as the key. For example, the key may be “spiral clockwise, starting in the bottom-right”, which would give us the ciphertext:GAENESESSIHTIETSBARDINETRGERASCMAUFRTo decode the ciphertext, the recipient must know the pattern used and the size of the grid. They would then simply follow the pattern in reverse to form a grid of the given size.

Book Cipher

The book cipher is an encryption method often used in popular culture. With a book cipher, both the sender and recipient of a secret message must have the same copy of a book, usually down to the same edition. The sender then encodes the secret message word-by-word by replacing the plaintext word with coordinates mapping to the location of the same word within the chosen book. For example, if the word “Kill” appeared in the book on page 39, paragraph 7, word 12, the ciphertext coordinates would be {39:7:12}. To decode the word, the recipient would find the word within their copy of the book in the notated position. To solve the problem of encoding a message that includes words not contained in the book, the sender could instead encode it character-by-character. The ciphertext coordinates could either point to individual letters in the book or to words where the resulting plaintext character is the first character of the word.

One-Time Pad

A one-time pad is an encryption technique that cannot be solved by brute-force (trying every possible combination of key in hopes of outputting the original plaintext message). Encrypting a message using a one-time pad requires a single-use pre-shared key of the same size or larger than the plaintext message being encoded. Both the sender and the recipient of the message must know the key but it must also be kept secret from everyone else. So long as the same “pad” is never used twice, the ciphertext remains secure. Messages encrypted using a one-time pad are resistant to cryptanalysis because it is possible to decode the ciphertext into any plaintext message with the same number of characters as the original plaintext message by using different keys. Specifically, there is no information in the ciphertext that allows differentiating between multiple potential plaintext decodings of the same ciphertext. Encoding a message with a one-time pad requires using modular addition, which is best explained with an example. Let’s say we want to encode the plaintext message “KILL THE SPY.” We must first select a one-time pad to use. Historically, one-time pads were generated as a stack of pages. Both parties then agreed on which specific page to use in advanced. For this example, we assume our agreed-upon one-time pad is:HQWORJIHKSGSICOSFSSB PCWCHGXYOUMWEOYYWUKY LKVZVHSMRJPLGHXULJBTNext, each character in the plaintext message is paired up with a character from the pad, starting with the first character. To make the modular addition calculation easier, we can convert each character into its numeric value (e.g. “A” is 0, “B” is 1, etc.) Next we add the numeric values of the corresponding message and key characters together, mod 26. While modular addition sounds complicated, it is actually very simple. First, add the two numbers together like normal. Then, if the resulting number is equal to or larger than 26 (our mod value), subtract 26 from it. The resulting number is the numeric value of the ciphertext character.     K     I     L     L     T     H     E     S     P     Y   message   10(K)  8(I) 11(L) 11(L) 19(T)  7(H)  4(E) 18(S) 15(P) 24(Y)  message +  7(H) 16(Q) 22(W) 14(O) 17(R)  9(J)  8(I)  7(H) 10(K) 18(S)  key = 17    24    33    25    36    16    12    25    25    42     message + key = 17(R) 24(Y)  7(H) 25(Z) 10(K) 16(Q) 12(M) 25(Z) 25(Z) 16(Q) (message + key) mod 26      R     Y     H     Z     K     Q     M     Z     Z     Q   ciphertextIn the above example, our plaintext message “KILL THE SPY” becomes “RYHZKQMZZQ” using the one-time pad. To decode the message, the same process is used, just in reverse. We subtract the key from the ciphertext and if the result is negative we add 26.     R     Y     H     Z     K     Q     M     Z     Z     Q   ciphertext   17(R) 24(Y)  7(H) 25(Z) 10(K) 16(Q) 12(M) 25(Z) 25(Z) 16(Q)  ciphertext -  7(H) 16(Q) 22(W) 14(O) 17(R)  9(J)  8(I)  7(H) 10(K) 18(S)  key = 10     8   -15    11    -7     7     4    18    15    -2     ciphertext - key = 10(K)  8(I) 11(L) 11(L) 19(T)  7(H)  4(E) 18(S) 15(P) 24(Y)  ciphertext - key (mod 26)      K     I     L     L     T     H     E     S     P     Y   message DVXVJLEEOTPEMKGGWVHSOTAJLEXGOZWUAKJQLZRGWQUHOYEKXSMVVRGDUCSJJELKPS