Message Encoding from Ancient Rome to WW2 Germany

Message Encoding from Rome to WW2 Germany, by Ellen Hetland Fenwick

“What matter all these mysteries to me Whose life is full of indices and surds?”

X²+ 7X + 53 = 11/3

– Lewis Carroll

It started with my reading a wonderful book, “From Mary, Queen of Scots to Quantum Cryptography” by Simon Singh, 1999. It became clear to me that much of the process used by the Nazis in the workings of the Enigma, the encryption machine that encoded and decoded messages for the Nazis during World War II, originated in ancient Rome. Evolution of Enigma involved only two major advances in cryptography over the course of almost 2000 years. These steps will be described in the remainder of this essay.

Message Encoding: Caesar Shift

In Ancient Rome the Caesar Shift was the method of message encoding. It is said Julius Caesar employed it. This method (today) makes use of the alphabet shifted to the right from 1 to 25 times:

ABCDEFGHIJKLMNOPQRSTUVWXYZ: Alphabet
BCDEFGHIJKLMNOPQRSTUVWXYZA: Shift 1
CDEFGHIJKLMNOPQRSTUVWXYZAB: Shift 2
DEFGHIJKLMNOPQRSTUVWXYZABC: Shift 3

ZYXWVUTSRQPONMLKJIHGFEDABC: Shift 25

The easiest way to explain the encoding is by an example:

Encode the message, “ENGAGE”, by Shift 3.

E becomes H, N becomes O, G becomes J, A becomes D, G becomes J, E becomes H.

So “ENGAGE” encoded is “HOJDJH”.

These messages are easily deciphered. One suspects that either the ‘H‘ or the ‘J‘ is ‘E‘ in the un-encoded message. ‘E‘ is the most frequently found letter in words. For instance if ‘Z’ occurs frequently in the coded message then ‘E’ in a message must have been changed to ‘Z’ for the code. English words starting with ‘T’ are usually words starting with ‘TH’. Analysis of the frequency of letters in the alphabet used in a cipher has been a tool of the cipher people for a long time. It is said that Mary Queen of Scots used Caesar Shift code. The messages were intercepted and the code deciphered. There was enough evidence to convict her of treason, and Queen Elizabeth had her beheaded.

A Caesar Shift code is sometimes referred to as a simple substitution code. Some of you (mainly the guys, I suspect) may remember sending in an Ovaltine proof-of-purchase to obtain a Captain Midnight Code-O-Graph. This made use of a number/letter substitution code similar to a Caesar Shift.

Some effort was made to make cracking a Caesar Shift code more difficult, but an excellent solution had to wait until the 14th century.

First Advance: The Vigenère Cipher

In the 14th century Blaise de Vigenère came up with an ingenious scheme. Just take the Caesar Shift configuration and add a key word no larger than the message. I will show how the encoding is done is by the following example:

1) Let the original message be ‘FADE’.
2) Let the key word be ‘CEB’.
3) Enlarge the keyword to ‘CEBC’ making it as long as the message.
4) Choose the four Caesar Shifts that begin with ‘C‘, ‘E‘, ‘B‘ and ‘C‘ to echo the enlarge key word:

CDEFGHIJKLMNOPQRSTUVWXYZAB
EFGHIJKLMNOPQRSTUVWXYZABCD
BCDEFGHIJKLMNOPQRSTUVWXYZA
CDEFGHIJKLMNOPQRSTUVWXYZAB

5) Encode ‘FADE‘ in the following manner:

a) Replace first character (F) of the message with the first letter of the first of the four Caesar Shifts, ‘C.’
b) Replace 2nd character (A) of the message with the 2nd letter of the 2nd of the four Caesar Shifts, ‘F.’
c) Replace 3rd character (D) of the message with the 3rd letter of the 3rd of the four Caesar Shifts, ‘D.’
d) Replace 2nd character (A) of the message with the 4th letter of the 4th of the four Caesar Shifts, ‘F.’
e) FADE encoded is CFDF.

Vigenère message encoding is portrayed graphically in the following diagram:

F
↕
CDEFGHIJKLMNOPQRSTUVWXYZAB 1st letter of key word is ‘C.’

A
↕
EFGHIJKLMNOPQRSTUVWXYZABCD 2nd letter of key word is ‘E.’

D
↕
BCDEFGHIJKLMNOPQRSTUVWXYZA 3rd letter of key word is ‘B.’

E
↕
CDEFGHIJKLMNOPQRSTUVWXYZAB 4th letter of key word is ‘C.’

The Vigenère Cipher is much harder to decipher than what had come before. Charles Babbage succeeded in deciphering it in 1854. It is obvious that it took some sort of genius to accomplish this. Babbage did not make his finding public, and it was not until the 1970’s that the secrets of the cipher became widely known.

Second Advance: The Nazis’ Enigma

During World War II the Nazis used a machine, The Enigma, to encode messages. During the encoding of a message the Vigenère processes were used again and again to encode a message. Each time the key word was changed:

1) Encode message with keyword 1; produce encoded message 1
2) Re-encode encoded message 1 with keyword 2; produce encoded message 2
3) Re-encode encoded message 2 with keyword 3; produce encoded message 3
4) Re-encode encoded message n-1 with keyword n; produce encoded message n.

And message n is the delivered message, unless additional processes are employed to further decrease its decipherability.

General (later President) Dwight Eisenhower considered the breaking of the Enigma cipher to have been of critical importance to the allied victory in World War II. The earliest breakthroughs in cracking Enigma were made by the Polish Cipher Bureau, beginning in December 1932. The effort was continued during the war by the British and Americans, most notably at the British Government Code and Cypher School (GC&CS) at Bletchley Park, under the direction of the brilliant mathematician Alan Turing. This work is dramatically described in the movie “The Imitation Game.”

New Codes

These are quite different from their predecessors. The last one I became aware of used the product of two very large primes. This product is made public. The way to decipher the code is to find the two large primes. This is possible with the fast computers we have but still will take much time. The reasonable assumption those responsible for message encoding have adopted is that no code is “uncrackable.” But by the time seekers of the two very large primes have found them, the creators of the code will have chosen another set of primes.

¹ If the original message is 11 characters long, enlarge the key word to CEBCEBCEBCEBC.

² The successful cracking of Enigma resulted not so much from any weakness in the system, but rather from the German operators failure to follow prescribed procedures. For example, they often repeated phrases from one message to the next, thereby giving the Allied teams an entry point in decrypting the code.

³ My young friend Clara, the cryptographer, tells me that message encoding technology has changed many times since the methodology of large primes was used.

-Ellen Hetland Fenwick

Note: You might also enjoy Deciphering a Cryptic 1700s Philadelphia German Tombstone

← Back to Math-Language-Design
← Home