The Caesar and Vigenère Ciphers

The Caesar cipher dates to ancient times and Vigenère cipher to the sixteenth century. The Caesar cipher was never secure despite its alleged use by powerful emperors. In the mid nineteenth century the Vigenère cipher was broken.

The Caesar cipher

The Caesar cipher was reputedly used by the Emperor Julius Caesar to communicate with his generals. Given a plain text message like ATTACKATDAWN we encrypt by shifting each letter forward a certain distance in the alphabet. For example, if we shift back three letters we get the ciphertext XQQXZHXQAXTK. Think of the letters of the alphabet as being arranged in a circle, so that shifting A back by 1 unit gives Z, shifting back by 2 gives Y, etc. To decode, we just shift forward by 3. The key for this code is the number 3.

The Caesar code is easy to break even without the key. One way is to use frequency analysis. The letter X occurs three out of twelve times, just as the letter Q is. These are therefore likely to be among the most frequent letters of the English alphabet: E, T, A, O, I in order. With statistical clues like this, one can easily break the code. But since there are only twenty-six keys, brute force also works: we shift forward by one unit, by two, by three, and so on, until we see something that makes sense:

1: YRRYAIYRBYUL
2: ZSSZBJZSCZVM
3: ATTACKATDAWN

Because computers speed up brute force searches, one requirement of a good cryptographic system is a large enough "key space."

Vigenère cipher

The Vigenère cipher is more difficult to crack. We explain this encryption scheme in the case where the plain text is ATTACKATDAWN and the key is OATMEAL. First, to the letters A, B, C, ..., X, Y, Z, associate the numbers 0, 1, 2, ..., 23, 24, 25. Define an addition operation on letters by adding the corresponding numbers, then looking up the corresponding number. To this we add just one rule: if the result is bigger than 25, subtract 26. Thus, to compute B + Q, note that 1 + 16 = 17, which corresponds to R:

B + Q = R

Likewise, for T + U, we form 19 + 20 = 39 and subtract 26 to get 13, which corresponds to N. Thus

T + U = N

For subtraction, do the same, except that if the result is less than zero, add 26 to the numerical result. Thus

K - J = B and J - K = Z.

We can add words as well as letters. For example, ONE + TWO = HJS. We obtained this result by adding corresponding letters: O + T = H, N + W = J, E + O = S. This is a simple example of Vigenè encryption: we encrypted ONE using the keyword TWO. To decrypt, subtract: HJS - TWO = ONE. The only thing left to say is that if the key is shorter than the message, just repeat the key as needed. Thus the ATTACKATDAAWN message was encrypted as

ATTACKATDAWN + OATMEALOATME = OTMMGKLHDTIR

Secrecy is perfect if the key and the plain text have the same length, the key is only used once, and (of course) kept secret.

Here is a little problem — to find the plain text of the message below:

HEUJPIHFDHQLJAKBWGOZWFBVVEEHEJWLVPLAF
LKGRMXHSIXWTWRKHKWSKQLMXSLKIJRRFUPWPW

The message was encoded using the Vigenère method. Your job is to break the code without knowing the key.

Some history

The Vigenère cipher was invented in the mid sixteenth century by Blaise de Vigenère, who worked in the court of King Henry III of France. Long thought to be unbreakable, a method for its solution was published in 1861 by the German army officer Friederich W. Kasiski.