Recent Articles

Caesar cipher

In cryptography, a Caesar cipher, also known as a Caesar shift cipher or shift cipher, is one of the simplest methods of encryption, although it can be easily broken. It is a substitution cipher in which each letter in the plaintext is replaced by the letter some fixed number of positions further down the alphabet. For example, with a shift of 3, a would be replaced by D<tt>, <tt>b would become E, and so on. The method is named for Julius Caesar, who was recorded to have used it to communicate with his generals.

The encryption step performed by a Caesar cipher is often incorporated as part of more complex schemes, such as the Vigenère cipher, and still has modern application in the ROT13 system.

Example

The transformation can be represented by aligning two alphabets; the cipher alphabet is the plain alphabet rotated left or right by some number of positions. For instance, here is a Caesar cipher using a right rotation of three places ("3" being the cryptographic key):

To encipher a message, simply look up each letter of the message in the "plain" line and write down the corresponding letter in the "cipher" line. To decipher, do the reverse.

The encryption can also be represented using modular arithmetic by first transforming the letters into numbers, according to the scheme, A=0, B=1,...,Z=25. Encryption of a letter <math>x<math> by a shift n can be represented mathematically as:

<math>E_n(x) = x + n \mod 26<math>

Similarly, decryption is represented as:

<math>D_n(x) = x - n \mod 26<math>

History

The Caesar cipher is named after Julius Caesar, who, according to Suetonius, used it with a shift of 3 to protect a messages of military significance, including one to Marcus Cicero. It is unlikely that Caesar was the first to use the scheme, and substitution ciphers had certainly been suggested in earlier writings. The method was secure at the time because few of Caesar's enemies would even be literate, let alone able to perform cryptanalysis; furthermore, there is no record that any method was then known which would reliably break such a cipher. Since the discovery of frequency analysis in the Arab world around 1000CE, every such cipher has been easily, even trivially, breakable. None are suitable for secure communication now, and indeed haven't been for the past 1000 years or so. An ancient Roman book on cryptography, now lost, is said to have discussed the use of such ciphers at considerable length.

Even as late as 1915, the Caesar cipher was in use: the Russian army employed it as a replacement for more complicated ciphers which had proved to be too difficult for their troops to master; German and Austrian cryptanalysts had little difficulty in decrypting their messages.

The most commonplace Caesar ciphers found today are in children's toys such as secret decoder rings and in the ROT13 algorithm (which, of course, serving only to obscure, is meant to be trivial to decrypt).

Breaking the cipher

The Caesar cipher is much weaker than the substitution ciphers used in newspaper cryptogram puzzles, which typically scramble the alphabet in more complex ways. By graphing the frequencies of letters in the ciphertext and those in the original language of the plaintext, a human can easily spot the value of the key by looking at the displacement of particular features of the graph. This is known as frequency analysis. For example in the English language the plaintext frequencies of the letters E, T, (most frequent), and Q, Z (least frequent) are particularly distinctive. Computers can also do this trivially by means of an auto-correlation function.

Another approach to breaking the cipher involves recognition of short, commonly-used words; in English, "the", "and", and "of" appear regularly. A two- or three-letter sequence that is repeated in the ciphertext is likely to stand out, particularly if spaces are included in the ciphertext, and these can often give clues to the cryptanalyst. Repeated, consecutive letters can also also be obvious clues, as there are relatively few letters that commonly repeat consecutively: "ss", "ee", and "tt" are common in English. For instance, the ciphertext:

contains a short word, enciphered as "XQ", and a double-letter "QQ"; surmising that "QQ" is really "ss" or "tt" would soon lead to a correct deciphering, "attack at dawn." This is another form of frequency analysis, taking into account more than one letter at a time. Since the Caesar cipher uses a uniform shift, once a single letter has been identified with confidence, decrypting the message is a simple matter of shifting the remaining ciphertext by the appropriate amount.

As such a cipher system only has 26 possible keys (or more precisely, as many characters as there are in the alphabet used; e.g. Polish has more than 26 letters) it is trivial even for a cryptanalyst equipped only with pen and paper to cycle through the keys trying each until they find one which allows the ciphertext to be converted into plaintext. This is known as a brute force attack.

A minor improvement in security can be made by garbling the plaintext through omission of vowels, removing excess usage of common words like "the," or otherwise distorting the text within the limits of readability. For example, the message "the quick brown fox jumps over the lazy dog" could be rendered as:

Frequency analysis is less likely to yield useful results in such a message, since the usual English characteristics are distorted; the common letter "e" is not used at all. Some common two-letter combinations are not as likely to be recognized correctly, but on the other hand others, including 'th', aren't changed. Even so, breaking this variant of a Caesar cipher is unlikely to require a brute force attack as too much information about the plaintext is preserved.

Multiple encryptions and decryptions provide no additional security. This is because two encryptions of, say, shift A and shift B, will be equivalent to an encryption with shift A + B. In mathematical terms, the encryption under various keys forms a group.