The Caesar cipher shifts every letter by the same number of places. With a key of 3, A becomes D, B becomes E, and “Hello World” becomes “Khoor Zruog”.

There are only 26 possible keys. Trying all of them is easy. Deciding which of the 26 results is the message is the actual work.

My first version printed all 26 lines and left that decision to a human. The new version makes that decision itself.

Why I built it

Caesar is usually called insecure because it only has 26 keys. A million keys would not help either, as long as a program can try every one and recognise the right result.

I wanted to see which part of the language survives the encryption, and how much statistics it takes to use it.

How it works

A command-line tool with three modes:

python main.py encrypt "Hello World" --key 3
python main.py decrypt "Khoor Zruog" --key 3
python main.py brute "Khoor Zruog"

Without arguments, python main.py asks for the cipher, the mode, the text and, for encrypt and decrypt, the key. If an answer is invalid, for example a key that is not a number, it asks again.

When encrypting, the tool keeps only the letters A to Z and puts them in capitals, so “Hello World” with key 3 comes out as KHOORZRUOG. Spaces would show how long each word is. Decrypting gives the letters back without spaces. The tool uses only Python and its standard library.

brute decrypts the text with every key from 0 to 25, gives each result a score for how much it looks like English, and prints the best one. With --all it prints all 26, best first.

Attempt 1: single letters

Letters are not equally common. In English, E makes up about 12.7% of all letters, T about 9.1%, and Z less than 0.1%.

A Caesar shift moves every letter, but it moves them all by the same amount. The frequencies survive. They move to other letters. The right decryption is the one whose letter counts look most like English again.

To measure “looks like”, I used a chi-squared test. For each letter:

1. count how often it appears in the candidate (observed),
2. work out how often it should appear in English text of that length (expected),
3. add up (observed - expected)² / expected over all 26 letters.

The lower the sum, the closer the candidate’s letter counts are to English. Squaring makes large deviations count much more than small ones.

On a full sentence this works. “The quick brown fox jumps over the lazy dog”, encrypted with key 11, came back correctly.

On “Khoor Zruog” it failed. The winner was key 6:

6  Ebiil Tloia
14 Wtaad Ldgas
3  Hello World

“Hello World” came third. Most of its score comes from the three L’s: 16.9 of 28.4. L is about 4% of English text, so in ten letters you would expect 0.4 of them. Three is a large deviation, and the test punishes it. “Ebiil Tloia” happens to consist of common letters, so the test rates it higher.

Ten letters are not enough for single-letter statistics to settle down.

Attempt 2: letter pairs

Counting single letters ignores which letters stand next to each other.

“hello” contains the pairs he, el, ll, lo. he is one of the most common pairs in English, and ll occurs in many words, such as “all” and “will”. “Ebiil” contains eb, bi, ii, il. A double I is rare.

These pairs are called bigrams. Scoring by letter pairs, or by longer groups such as four letters, is a common way to break classical ciphers automatically.

Where the numbers come from

A table of bigram frequencies has to come from real text. I did not want to copy one from somewhere without knowing how it was made, so I counted my own.

build_bigrams.py takes Pride and Prejudice from Project Gutenberg, cuts off Gutenberg’s header and footer, lowercases everything and drops every character that is not a letter, spaces included. Then it counts every pair of neighbouring letters.

The book gives 563,924 letters. The most common pairs are th, he and er, which are also at the top of published lists for English, so the counting works. ll appears 3,456 times, ii only 90 times. Deleting bigrams.json and running the script again produces a byte-identical file.

123 of the 676 possible pairs never appear in the whole book, bq or cx for example.

Dropping the spaces is deliberate. Real ciphertexts are often written without them, so that word lengths do not give anything away. A score that needs spaces would not work on those.

Scoring

For each candidate, the program looks up the probability of every letter pair. Two things are needed to turn these into one score.

Logarithms. The probability of a whole text is the product of the probabilities of its pairs. Multiplying hundreds of small numbers produces a number too small for the computer to store. Taking the logarithm turns the multiplication into an addition, and the sum stays in a normal range.

Smoothing. A pair that never appeared in the book has probability zero, and the logarithm of zero is minus infinity. A single cx would make a candidate impossible, no matter how good the rest of it is. So every count gets +1 before the probabilities are calculated. Unseen pairs become very unlikely instead of impossible.

The result is a negative number per candidate, because the logarithm of a probability below 1 is negative. The closer it is to zero, the more common the candidate’s letter pairs are in English.

Results

“Khoor Zruog” again, now with bigrams:

3  Hello World   -48.6
14 Wtaad Ldgas   -59.5
6  Ebiil Tloia   -59.6

“Hello World” is now first, 10.9 points ahead of the next candidate. “Ebiil Tloia” is third.

Input	Ciphertext	Result
Short text	Khoor Zruog	key 3: Hello World
No spaces	HAAHJRHAKHDU	key 7: ATTACKATDAWN
One word	mywlyn	key 20: secret
No letters	123 !?	key 0: 123 !? (no crash)

A full sentence, encrypted with key 11:

Esp bftnv mczhy qzi ufxad zgpc esp wlkj ozr
key 11: The quick brown fox jumps over the lazy dog

The cases above are also unit tests. python -m unittest runs them together with checks for the shift itself, such as x wrapping around to a.

Known limits

English only. The table comes from an English book. German text would need its own table, and the same script could count it from a German book.

Very short texts. “secret” (six letters) came back correctly. Of seven words with two or three letters I tried, only “cat” did. --all is there for those cases.

One book from 1813. The frequencies come from a single novel written two hundred years ago. Modern text, and especially technical text, has somewhat different pairs. For Caesar with its 26 candidates this does not matter much.

No spaces after decrypting. Encrypting removes the spaces, so decrypting gives HELLOWORLD, and the reader has to find the word boundaries. They cannot be restored, because the ciphertext no longer contains them.

What I learned

Scoring without knowing words

I assumed a score would have to recognise real words. The bigram score does not. “hehehehehe” scores -40.6, better than “helloworld” at -48.6. It only has to pick the one candidate out of 26 that is not shifted nonsense, and common letter pairs are enough for that.

Short texts

The chi-squared test worked as intended on “Hello World”. The numbers in attempt 1 show that ten letters are too few for single-letter counts. Letter pairs did better with the same ten letters, because they also use the order of the letters.

Spaces in the ciphertext

The first version kept the spaces. A word of one letter is almost always A or I in English, and for Caesar one known letter is enough to work out the key. Removing the spaces avoids that. The cost is that decrypted text has no word boundaries.

Writing the tests afterwards

I wrote the tests after the code, from cases I had already checked by hand. The interactive mode was harder to test, because it waits for input. The tests replace input() with a list of prepared answers and capture what the program prints.

What comes next

The Vigenère cipher. Instead of one shift for the whole text, it uses a keyword, and each letter of the keyword gives its own shift. The keyword repeats along the text. With the keyword LEMON, ATTACKATDAWN becomes LXFOPVEFRNHR.

The tool can already encrypt and decrypt with it. I describe that, and the plan for breaking it, in the Vigenère cipher post.

The code is at github.com/DilaraKoc1/cipher-breaker.