Caesar cipher

The transformation can be represented by aligning two alphabets; the cipher is the plain alphabet shifted left or right by a certain number of positions. For instance, here is a Caesar cipher using a left shift of three places, equivalent to a right shift of 23 (the shift parameter is used as the key): When encrypting, a person looks up each letter of the message in the "plain" line and writes down the corresponding letter in the "cipher" line. Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD Deciphering is done in reverse, with a right shift of 3. 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 x by a shift n can be described mathematically as: : E_n(x) = (x + n) \mod {26}. Decryption is performed similarly: : D_n(x) = (x - n) \mod {26}. (Here, "mod" refers to the modulo operation. The value x is in the range 0 to 25, but if or are not in this range then 26 should be added or subtracted.) The replacement remains the same throughout the message, so the cipher is classed as a type of monoalphabetic substitution, as opposed to polyalphabetic substitution. ==History and usage==

, who used an alphabet where decrypting would shift three letters to the right. The Caesar cipher is named for Julius Caesar, who, according to the Roman historian Suetonius, used it with a shift of three ( becoming when encrypting, and vice versa when decrypting) to protect messages of military significance. While Caesar's was the first recorded use of this scheme, other substitution ciphers are known to have existed earlier. Suetonius writes that his nephew, Augustus, used the cipher with a right shift of one, but it did not wrap around to the beginning of the Latin alphabet, instead replacing with . Evidence exists that Caesar also used more complicated systems. The grammarian Aulus Gellius refers to a (now lost) treatise on his ciphers: It is unknown how effective the Caesar cipher was at the time: there is no record of contemporary techniques for the solution of simple substitution ciphers. The earliest surviving records date to the 9th-century works of Al-Kindi in the Arab world with the discovery of frequency analysis. A piece of text encrypted in a Hebrew version of the Caesar cipher (not to be confused with Atbash) is sometimes found on the back of Jewish mezuzah scrolls. When each letter is replaced with the letter before it in the Hebrew alphabet, the text reads "YHWH, our God, YHWH", a quotation from the scroll. The Vigenère cipher uses a Caesar cipher with a different shift at each position in the text; the value of the shift is defined using a repeating keyword. Repeating keywords (e.g., "Complete Victory" used by the Confederacy during the American Civil War) introduce a cyclic pattern that might be detected with statistically advanced frequency analysis. (See e.g. Coincidence counting.) If the keyword is as long as the message, is chosen at random, never becomes known to anyone else, and is never reused, it is a one-time pad cipher, impossible to break cryptographically. However, the problems involved in distributing such a key make the one-time pad difficult to use in practice. In the 19th century, the personal advertisements section in newspapers would sometimes be used to exchange messages encrypted using simple cipher schemes. David Kahn (1967) describes instances of lovers engaging in secret communications enciphered using the Caesar cipher in The Times. As late as 1915 during World War I, the Caesar cipher was used by the Russian army as a replacement for more complicated ciphers which had proven difficult for their troops to master; German and Austrian cryptanalysts had little difficulty in decrypting their messages. In April 2006, fugitive Mafia boss Bernardo Provenzano was captured in Sicily partly because some of his messages, clumsily written in a variation of the Caesar cipher, were broken. Provenzano's cipher used numbers, so that "A" would be written as "4", "B" as "5", and so on. In 2011, British Airways employee Rajib Karim was convicted of "terrorism offences" after using a Caesar cipher to discuss with Bangladeshi jihadi activists plots to bomb the airline's planes or disrupt its IT systems. Although the parties had access to far better encryption techniques (Karim himself used PGP for data storage), they chose to use their own scheme implemented in Microsoft Excel, rejecting a more sophisticated code program called Mujahedeen Secrets "because 'kaffirs', or non-believers, know about it, so it must be less secure". Caesar ciphers can be found today in children's toys such as secret decoder rings. A Caesar shift of thirteen is also performed in the ROT13 cipher, a simple method of obfuscating text widely found on Usenet and used to obscure text (such as joke punchlines and story spoilers), but not seriously used as a method of encryption. ==Breaking the cipher==

The Caesar cipher can be easily broken even in a ciphertext-only scenario. Since there are only a limited number of possible shifts (25 in English), an attacker can mount a brute force attack by deciphering the message, or part of it, using each possible shift. The correct decryption will be the one which makes sense in the language of the plaintext. An example is shown on the right for the ciphertext ""; the candidate plaintext for shift four, "", is the only one which makes sense as English text. Another type of brute force attack is to write out the alphabet beneath each letter of the ciphertext, starting at that letter. Again the correct decryption is the one which makes sense as English text. This technique is sometimes known as "completing the plain component". Another approach is to match up the frequency distribution of the letters. By graphing the frequencies of letters in the ciphertext, and by knowing the expected distribution of those letters in the original language of the plaintext, a human can easily spot the value of the shift 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 , , (usually most frequent), and , (typically least frequent) are particularly distinctive. Computers can automate this process by assessing the similarity between the observed frequency distribution and the expected distribution. This can be achieved, for instance, through the utilization of the chi-squared statistic or by minimizing the sum of squared errors between the observed and known language distributions. The unicity distance for the Caesar cipher is about 2, meaning that on average at least two characters of ciphertext are required to determine the key. In rare cases more text may be needed. For example, the words "" and "" can be converted to each other with a Caesar shift, which means they can produce the same ciphertext with different shifts. However, in practice the key can almost certainly be found with at least 6 characters of ciphertext. With the Caesar cipher, encrypting a text multiple times provides no additional security. This is because two encryptions of, say, shift A and shift B will be equivalent to a single encryption with shift . In mathematical terms, the set of encryption operations under each possible key forms a group under composition. ==See also==