Caesar cipher

From open-encyclopedia.com - the free encyclopedia.

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.

Contents

1 Example 2 History 3 Breaking the cipher 4 External links

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):

Plain:  abcdefghijklmnopqrstuvwxyz
Cipher: DEFGHIJKLMNOPQRSTUVWXYZABC

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.

 Plaintext: thequickbrownfoxjumpsoverthelazydog
Ciphertext: WKHTXLFNEURZQIRAMXPSVRYHUWKHODCBGRJ

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 described mathematically as,

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

Decryption is performed similarly,

<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 messages of military significance, including one to Marcus Cicero. It is unlikely that Caesar was the first to use the scheme, and other substitution ciphers are known to have been used earlier.

The cipher was effective at the time not least because few of Caesar's enemies would have been literate, let alone able to consider cryptanalysis. Assuming a literate attacker, it is not known whether any techniques were then known for the solution of simple subtitution ciphers. The earliest surviving records date to around 1000 AD in the Arab world with the discovery of frequency analysis.

Julius Caesar's nephew, Augustus also used the cipher, but with a shift of one.

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:

XQQXZH XQ AXTK

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:

th quik brwn fx jmps ovr da lzy dog

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.

External links

• An online Caesar cipher encoder (Javascript)
• The Caesar Shift as discussed on The Beginner's Guide to Cryptography

cs:Caesarova Å¡ifra de:Verschiebechiffre it:Cifrario di Cesare ja:シーザー暗号 pl:szyfr przesuwający pt:Cifra de César