Caesar Cipher

One of my favorite undergraduate courses was an optional elective on the topic of ciphers, starting with handwritten approaches and eventually moving on into mechanical and then digital cryptography. A few classes in the handwritten section started with the professor writing ciphertext on the board and inviting us to spend some time attempting to break it without knowledge of what the cipher actually was.

A while back I pledged to write a paper on a topic unrelated to my academic major for my Estonian fraternity. I never actually got around to doing this, but at the time of the pledge I had the ciphers course fresh in my head and thought it would more research would be interesting. So in the interest of actually making some progress on this, I thought writing a bit about handwritten ciphers here may be a good way to motivate myself. To ease into it, I’m starting with the most basic cipher I know of: the Caesar Cipher.

The Caesar cipher itself is a substitution cipher: to convert a piece of plaintext into ciphertext, every letter in the plaintext is consistently replaced with another letter according to some mapping. In the Caesar cipher, the mapping is simply defined by shifting letters forward a set number of steps, wrapping from the end to the start as needed. I’ll refer to the number of steps at the ROT value: a mapping of ROT1 means that all ‘A’s are replaced with ‘B’s, ‘B’s with ‘C’s, and ‘Z’s with ‘A’s. ROT20 shifts the letters by 20 spaces, and so on.

I’ve written up a small utility to generate the mapping. Dragging the slider below shows the mapping from plaintext letters on the top, to ciphertext letters on the bottom:

Substitution ciphers must define the alphabet they operate on. I’ve decided to use the 26 letters in the English alphabet and not to convert any other characters including whitespace and punctuation, but it’s possible to define the working alphabet to accommodate any characters. I’ll use ALPHA to represent the size of the working alphabet, with ALPHA26 representing the 26 English characters I’m using.

To convert plaintext to ciphertext, substitute every letter in the plaintext with the mapped value for that letter. To convert ciphertext back into plaintext, undo the mapping by applying a ciphertext of ROT - ALPHA. This means that text encrypted with ALPHA26 and ROT3 can be decrypted by applying ROT23 (26 - 3) to the encrypted text.

Below, I’ve taken some sample text from the top box and applied the configured ROT mapping to it to produce the Caesar Cipher-encrypted ciphertext in the bottom box. The text in the top is editable in case you want to experiment with other input.

While any value can be used for ROT, there are a couple values with special properties. A ROT of 0 or of ALPHA is an identity mapping - the plaintext and ciphertext will be identical. For alphabets where the length of the alphabet is even, a ROT of ALPHA / 2 will act as both an encryption and decryption mapping - in the case of ALPHA26, applying ROT13 to plaintext will produce ciphertext, while applying ROT13 to ciphertext produces plaintext. This property makes for nice usability, to the point where such encoding is used on some websites as obfuscation for spoilers. There’s even a rot13 command line utility which ships on linux distributions. In the demo above, try setting the slider to 13 and pasting the ciphertext into the box on the top - you’ll see the original passage in the lower box.

The cipher itself is named after Julius Caesar, who reportedly used a form of ROT3 in his sensitive letters:

There are extant likewise some letters from him to Cicero, and others to his friends, concerning his domestic affairs; in which, if there was occasion for secrecy, he wrote in cyphers; that is, he used the alphabet in such a manner, that not a single word could be made out. The way to decipher those epistles was to substitute the fourth for the first letter, as d for a, and so for the other letters respectively.

(Suetonius & Thomson)

In terms of difficulty in breaking this code, the Caesar Cipher is very insecure. Simply possessing the knowledge of the decryption algorithm, as simple as “to substitute the fourth for the first letter, as d for a, and so for the other letters respectively” is sufficient to read any of Caesar’s historical correspondence.

In general, substitution ciphers are very susceptible to statistical analysis, first described by al-Kindī around 800AD (Al-Kadit, 1992, p. 101). His approach was:

One way to solve an encrypted message, if we know its [original] language, is to find a [different clear] text of the same language long enough to fill one sheet or so and then we count [the occurrences of] each letter of it. We call the most frequently occurring letter the "first", the next most occurring the "second", the following most occurring the "third" and so on, until we finish all different letters in the cleartext [sample]. Then we look at the cryptogram we want to solve and we also classify its symbols. We find the most occurring symbol and change it to the form of the "first" letter [of the cleartext sample], the next most common symbol is changed to the form of the "second" letter, and the following most common symbol is changed to the form of the "third" letter and so on, until we account for all symbols of the cryptogram we want to solve.

It could happen sometimes that the cryptogram is too short to have all different letters. The high and low [frequency] counts will not be correct, for high and low counts are only correct in long enough messages to correspond to all places of frequent and rare occurrences so that if some letters are [too] few in one segment of the message, they will be [too] many in others. But if the cryptogram is too short, equivalence does not apply, letter ranks are not correct and [consequently] a second trick should be used to recover letters. Such a trick is qualitative which is ... [here al-Kindī' wrote in detail on possible letter combinations in a language like 'al' in Arabic... etc.]

(Al-Kadit, 1992, pp. 107-108)

As a reference for the frequencies of English text, here’s a histogram of standard frequencies for each letter which I found online:

The unmodified sample text I included in this post also has a frequency distribution very visually similar to the distribution of English letters. It’s also really obvious that the frequencies for the ciphertext are merely shifted horizontally from that of the plaintext.

In terms of applying a statistical analysis technique to break a Caesar Cipher, it’s not necessary to use al-Kindī’s approach of going letter by letter if you know that a ROTN technique is being used. It’s sufficient to compute the frequency distribution for the ciphertext and then shift it over one step at a time, comparing the similarity of the shifted histogram against English at each step. The offset which produces the closest similarity is the likeliest candidate to decipher the ciphertext. Below is a table generated from each possible offset from the ciphertext, where the value is its difference from English according to the selected comparison method:

This post has a description of a bunch of comparison operations to use which have been implemented in the dropdown. There’s not a lot of difference in the methods with the unmodified sample text - they all accurately compute the right offset given a long enough message. But because the approach is focused on finding the right offset for all letters (contrasted to al-Kindī’s approach of matching letter-by-letter) much smaller messages can be broken. In fact, many of the approaches including a standard Euclidean distance measure will break a message as small as “Very short message” which intuitively doesn’t feel like it contains enough data to be able to decipher using frequency analysis (but it does!).

References

Comments? In the interest of limiting third-party Javascript running on this site, I've disabled all commenting plugins. If you have feedback, please share it with me on Twitter.

Elsewhere

Twitter (@kurrik) Github (kurrik) Google+ (+kurrik) Linkedin (kurrik)

Tags

arne (11) reviews (11) work (8) twitter (7) chrome (7) extensions (6) cinemaclub (6) games (6) books (4) html (4) google (3) ludumdare (3) algorithms (3) javascript (3) go (3) presentations (3) readinglist (2) appengine (2) internet (2) estonia (2) space (1) art (1) recipes (1) management (1) ciphers (1) http (1) product (1)