The Caesar Cipher

History of the Caesar Cipher

The Caesar cipher is one of the earliest known ciphers. It is named for Julius Caesar, who used it to encrypt messages of military importance that he did not wish to fall into enemy hands. His nephew, Augustus, used a modified version of the cipher for similar purposes and it is the basis for later ciphers such as the Vigenère cipher.

Implementation of the Caesar Cipher

Unlike many modern ciphers, the Caesar cipher does not have a secret key that’s needed to decode the message. Instead, the “secret” in the Caesar cipher is how the cipher works. This violates Kerckhoff’s Principle which states that “A cryptosystem should be secure even if everything about the system, except the key, is public knowledge”.

In the Caesar cipher, each letter of a message is replaced by the letter three steps to the right of it in the alphabet. For example, A is replaced by D, B by E, etc. The shift “wraps” around the alphabet so that X is replaced by A, Y is replaced by B, and Z is replaced by C.

To decode a message encrypted with a Caesar cipher, it is necessary to shift each letter in the ciphertext left by three steps to reach the original plaintext letter, so A becomes X, D becomes A, etc.

As an example, let’s consider the encryption of the message CAESARMESSAGE using the Caesar cipher as follows.

plaintext: CAESARMESSAGE
C → F
A → D
E → G
S → V
A → D
R → U
M → P
E → H
S → V
S → V
A → D
G → J
E → H
ciphertext: FDGVDUPHVVDJH

Shift Ciphers: A More General Caesar Cipher

Shift ciphers are a more general form of the Caesar cipher. The Caesar cipher is traditionally meant to be a right shift by three for encoding and a left shift by three for decoding. In a general shift cipher, any shift amount can be used, which increases the number of possible plaintexts for a given ciphertext from one in the Caesar cipher to twenty-six in a shift cipher (since a shift of twenty-six is the same as a shift of zero in the English alphabet).

To decode a ciphertext encrypted with a shift cipher, it is necessary to shift each letter of the ciphertext left by the same amount as it was shifted right in encryption. To simplify implementation, it is also possible to shift right by twenty-six minus the original shift amount. For example, the Caesar cipher can be decoded by a right shift of twenty-three since shifting a letter twenty-six steps to the right reaches the original letter.

Another special case of the shift cipher (besides the Caesar cipher) is the ROT13 cipher. In this cipher, each letter is rotated thirteen places to the right (or left), resulting in each letter being replaced by the letter halfway around the English alphabet from it. This cipher is commonly used in malware to provide a low level of obfuscation of sensitive information without using traditional, secure encryption algorithms.

As an example, let’s encrypt the message SHIFTMESSAGE using the ROT13 shift cipher as follows.

plaintext: SHIFTMESSAGE
S → F
H → U
I → V
F → S
T → G
M → Z
E → R
S → F
S → F
A → N
G → T
E → R
ciphertext: FUVSGZRFFNTR

Substitution Ciphers

Just as Caesar ciphers are a subset of shift ciphers, shift ciphers are a subset of substitution ciphers. In a substitution cipher, each letter of the alphabet is mapped to another letter of the alphabet for encryption. For example, the encrypted value of A might be M, while B might be Q.

It is not necessary in a substitution cipher for the mapping to be consistent (though it is in shift ciphers where the mapping is determined by the shift amount) or for letters to be paired so that each is the encryption of the other i.e. R encrypts to A and A encrypts to R (the Caesar Cipher doesn’t have this property but ROT13 does). The only requirement is that each plaintext letter maps to a single ciphertext letter and vice versa. For example, it’s not possible for both A and R to map to F in encryption since it would be impossible in decryption to determine if an F in the ciphertext is supposed to be an A or an R.

In order to decrypt a substitution cipher, it is necessary to know the mapping of plaintext letters to ciphertext letters. By performing the inverse of the encryption operation (i.e. if A is encrypted as R, replacing all of the R’s in the ciphertext with A’s), the original message can be determined.

For an example, let’s use the following map of letters in the plaintext to letters in the ciphertext.

alphabets:    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
encrypted-to: O Y U E N K Q Z J L X S G I R B V F H T D C A P M W

Using this mapping, let’s encrypt the message SUBSTITUTIONMESSAGE.

plaintext: SUBSTITUTIONMESSAGE
S → H
U → D
B → Y
S → H
T → T
I → J
T → T
U → U
T → T
I → J
O → R
N → I
M → G
E → N
S → H
S → H
A → O
G → Q
E → N
ciphertext: HDYHTJTUTJRIGNHHOQN

Frequency Attacks

One of the major security issues of substitution ciphers is that they retain the character distributions of the underlying text. In English, E is the most commonly used letter; therefore, in a sufficiently large sample of English text, it is likely that the letter that appears the most frequently in the text will be the letter E. Since substitution ciphers create a one-to-one mapping between plaintext letters and ciphertext letters, identifying the most common letter in a ciphertext (known to be in English) likely will reveal the letter that E maps to in encryption.

Breaking Shift Ciphers

For shift ciphers, performing this simple step will be sufficient to crack the cipher. Using the following steps, the plaintext can be retrieved:

1. Identify the most common letter in the ciphertext
2. Determine the shift used to make this letter decrypt to an E. For example, E is the fifth letter in the alphabet and, if J is the most common letter and is the tenth letter in the alphabet, the shift used is five
3. Decrypt the plaintext using the calculated shift value
4. If the result makes sense, terminate. Otherwise, repeat with the next most common letter in the ciphertext

This process is the most efficient method for cracking shift ciphers. However, due to the small number of possible shifts (twenty-six in English), it is also possible to try every possibility and look for a result that makes sense (maybe by checking to see if a reasonable majority of the message consists of words in the English dictionary).

Breaking Substitution Ciphers

Cracking a general substitution cipher using frequency analysis requires more work than a shift cipher since the mapping from plaintext to ciphertext must be discovered for each letter used in the message. For this, a table of the frequencies of use of various English letters (as shown below) is helpful.

Cracking a substitution cipher using frequency analysis is similar to cracking a shift cipher. First, the most common letter is identified in the ciphertext and tentatively labeled as an E. Next, the next most common letter is labeled as an T and so on. It is important to keep in mind that each plaintext letter can only be assigned to a single ciphertext letter and vice versa. A decryption resulting in nonsensical words or cases where the only logical choice for a letter has already been assigned indicates that one or more assignments is incorrect.

At each stage, the plaintext should be analyzed to determine if some letters can be learned from context or if some labelings may be incorrect. For example, in English there are only two one-letter words: a and I. By analyzing a message, it should be possible to quickly identify and label such words, gaining additional letters. Also, since E and T are the most common letters, words like “the” should be readily apparent. By using a combination of contextual clues and frequency information, substitution ciphers can easily be broken through frequency analysis.