Emily Eaton was nice enough to do some research in this field, and compiled the following  information for the OHDaMN.  She did a bang-up job.  Considering that a number of clues (I'm sure it seemed like half) made use of this information, we are all lucky that I wasn't the one stuck writing it.

Note:  Some portions of this article are formatted so that one line of text will line up with the next.  You should increase the width of your browser window or decrease the default size of text so that these tables are easier to read.  (If you can see all of the banner above, you'll be fine.)

A Brief History of Cryptography

The use of cryptographic methods to conceal communications dates back to ancient civilizations such as the Egyptians, the Hebrews, and the Assyrians.  History is full of military examples in which surprise was used as a deadly weapon, and transmission of secure messages between officers and intelligence agents is often a part of the ruse.  Following are summary descriptions of some of the cryptographic systems which have been used to achieve secret communication throughout history.

The Spartan Scytale

One of the earliest examples of encryption was by the Spartans around 400 B.C.  Spartan military commanders each had a baton called a "scytale".  When a message was to be sent, a strip of parchment was wrapped around the scytale so that the surface was completely covered but the parchment never overlapped.  The message was written on the strip of parchment down the length of the baton, and the strip was then removed from the baton and sent by messenger to the recipient.  The recipient would wrap the message around his identical scytale and then would be able to read the message.  While unwrapped, the letters on the parchment appeared to be random nonsense -- if an enemy were to capture the messenger, he would be able to make no sense of the message without the scytale.  However, if the enemy knew that this type of cipher was being used, he could try batons of different diameter until he found one which revealed the message.

Letter Substitution Ciphers

A substitution cipher is one in which each letter of the alphabet is substituted for another letter.  The most famous historical substitution cipher is the Caesar cipher, so called because it was first used by Julius Caesar.  In the Caesar cipher, messages were encrypted by "shifting" each letter by three based on its position in the alphabet.  Substitute D for A, E for B, etc.  For instance, the string GAC would be encrypted as JDF.  A slightly more general form of this cipher allows a shift of n letters.  The sender and the recipient agree on a value of n to be used for their communication.  A more complicated substitution cipher is the monoalphabetic cipher, which uses an arbitrary mapping of each letter to another letter.  the "Cryptogram" puzzles published in many newspapers are examples of this type of cipher.

These simple substitutions are fairly easy to break using letter frequencies.  We know that the most common letter in the English language is the letter E, and that A, N, S, and T are also common.  The letters Q, X, Z, and J are relatively rare.  If we count the frequencies of each of the letters in the encrypted message, we may find that L is the most common letter.  We can hypothesize that the letter L is substituted for the letter E.  If we are using one of the ciphers that depend on a shift of the alphabet, our work is probably done.  If L=E, then M=F, N=G, etc., and our message is decoded.  If a monoalphabetic cipher is being used, then we must continue to guess letters based on frequency until the message is revealed.

On easy way to confound bad guys trying to break your substitution cipher messages is to send only short messages.  For instance, the message "IRAQI AIRCRAFT FOUR OCLOCK" is more difficult to decrypt because the are no E's or S's (letters which we expect to be common) and there are two F's and two C's (letters which we expect to be less common).  The longer your message is, the more likely it is to fall in line with average statistics, so short messages are safer.  Of course, to maintain this safeguard, you must encrypt each of your messages using a different substitution mapping.  If an enemy intercepts 10 messages of 20 letters each that are all encrypted with the same mapping, he now effectively has a 200 letter sample to attack with statistics.

The Polybius Checkerboard

This is an ancient Greek form of encryption which substitutes number codes for letters.  The alphabet is written into a grid as follows:
 

Once the table is complete, the row and column numbers are used to signify letters.  For instance, the letter G would be encoded as "22" and the letter s as "43".  The letters I and J share the designation 24, but his should not be a complication to the recipient -- it will be clear from context whether the message reads "Georgja Tech" or "Georgia Tech".  This encryption method can be generalized by allowing an arbitrary assignment of letters into grid positions.

Notice that this method of encryption is vulnerable to the same attack as the letter substitution ciphers.  If the number 35 occurs most often, we can assume that 35=E, and so on.

The Vigenere Cipher

This Vigenere cipher dates to the nineteenth century and is much more difficult to break than the simple substitution ciphers.  Encrypting a message requires a secret key (a word or short phrase) shared between the sender and the recipient, and use of the table below:

To encrypt a message, use the message text and the key to identify a pair of letters, and then use that pair of letters as the row and column designation in the table to find the encoded text.  For example, let the message text be "Up with the white and gold", and let the key be "George".  We write the message text on one line (ignoring spaces) and the key on the line below, repeating the key as necessary:

Message:      UPWITHTHEWHITEANDGOLD
Key:          GEORGEGEORGEGEORGEGEO

The first letter of the message and the first letter of the key string form the pair U-G.  We use the letter from the message (U) to denote a row in the table, and the letter from the key (G) to denote a column.  The letter contained in both the row beginning with U and the column headed by G is "A", and this is the first letter of our encoded message.  Our second letter is determined by using the pair P-E, which gives the letter "T".  Using this pattern, our message is encoded as "ATKZZLZLSNNMZIOEJKUPR".

To decode the message, the recipient must use the same key and table.  Again, we use pairs of letters, this time from the encrypted text (the "ciphertext") and the key.

Ciphertext:   ATKZZLZLSNNMZIOEJKUPR
Key:          GEORGEGEORGEGEORGEGEO

Our first decoding pair is A-G.  To find the corresponding plaintext letter, simply reverse the encoding process.  We know that the letter A was found at the intersection of the column beginning with G and the row beginning with the first letter of the message.  So we find "column G" and trace down that column until the find the letter A, then trace across to find the of that row:  U.  Now we just need to repeat this process for each pair and the message will be revealed.

This encryption scheme is much more secure than any of the substitution systems discussed previously.  An enemy cannot decode the message text without knowledge of the key, even if he knows that Vigenere is being used.  However, this scheme is still vulnerable to cryptanalysis.  The method used to break this code is called the "Method of Coincidences".  The first step is to determine the length of the key.  We do this by shifting the encrypted text in relation to itself and comparing.  In the example below, the ciphertext has been shifted by 6:

Ciphertext:     ZLSNNM Z IOEJKUPR
Shifted by 6:   EJKUPR Z LSNNMZIO

(note: the spaces above are added only to emphasize the coincidence)

We compare the original with the shifted version and find there is one match -- the letter "Z" bolded in the example.  We try different shift amounts and count the matches for each.  We guess that the shift which gives the most matches is the length of the key.  Statistically, this will be true because some letters occur more often than others, and therefore some encryptions will be more common than others.

Once we have determined the length of the key, we break up the cipher text into groups that were encrypted using the same letter.  If the key length is 6, then we know that the 1st, 7th, and 13th letters were encrypted using the first letter of the key; the 2nd, 8th, and 14th letters were encrypted by the second letter of the key; and so on.  By studying the Vigenere table, we can see that encryption of a set of message letters with the same key letter produces a simple Caesar shift.  Now, we can use the letter frequency approach six times to decrypt the six groups.  With this done, we can reassemble the decrypted letters into their original order to reveal the message.

This code breaking strategy is complicated, but you can expect a moderately experienced cryptanalyst to be quite familiar with these methods.  One way to make your Vigenere messages more difficult to break is to send only short messages, as discussed in the section on substitution ciphers.  Again, you must change our key frequently or the enemy will be able to combine messages to get a larger sample.  Another way to make your messages harder to break is to use a long key, especially one made up of random letters rather than real English text  The Method of Coincidences relies on letter frequencies and repetition, so a long random key makes the necessary coincidences much more rare.

The Jefferson Wheel Cipher

This cryptographic system was originally invented by Thomas Jefferson, but was never put into use during his lifetime.  In 1922 a description of this system was rediscovered in his papers.  Coincidentally, at that time the US military was just beginning use of an almost identical system that had been invented independently.

The Jefferson Wheel cipher uses an encryption/decryption "machine" to translate between plaintext and ciphertext.  The wheels are constructed from a wooden cylinder with a hole bored lengthwise through the center so that the cylinder can turn on a spindle, similar to a rolling pin.  The cylinder is the n sliced into disks.  All 26 letters are written around the circumference of each disk, in a different (random) order for every disk.  Then the disks are threaded back onto the spindle.  The sender and the recipient of the encrypted message must have identical wheel systems.

To encode a message, the sender turns the wheels on the spindle so that one line of letters spells message.  Note that you can only encrypt as many letters as you have wheels, so longer messages may need to be done in multiple stages.  Once the wheels are aligned to spell the message across one of the lines, the remaining 25 letters around each disk give 25 lines of "random" letters.  The sender chooses any one of these lines and sends it as the ciphertext.

To decode the message, the recipient simply aligns the wheels to spell the ciphertext.  Because his wheel system is identical to the one the sender used, the plaintext message appears on one of the other 25 lines.  The recipient finds the line that reads as understandable English rather than random letters -- this is the message.

The security of the Jefferson Wheel cipher is comparable to that of the Vigenere cipher -- it is not trivial to break but can be broken by someone with an intermediate knowledge of cryptanalytic techniques.  Notice that the effect of Jefferson Wheel encryption is in fact very similar to Vigenere encryption except that the "key" is the position and labeling of the disks rather than a shared word or phrase.

The Enigma System

Probably the most famous historical cryptographic system is Enigma, which was devised by the Germans for use during World War II.  Although Enigma was a very strong encryption system, the Allies managed to break Enigma through the legendary efforts of cryptanalysts at Bletchley Park (based on earlier efforts in Poland) and through German overconfidence in the system.  The Germans abused Enigma because they thought it to be unbreakable, and the mathematicians took advantage of the abuse to break the system.  The breaking of the Enigma encryption system was one of the major deciding factors in the outcome of the war.

To encrypt messages, the Germans used Enigma machines, which resembled typewriters and were small enough to be carried by one person (or easily disposed of in case of capture).  A typewriter keyboard was used to enter the plaintext message, and an array of small lamps corresponding to letters then displayed the ciphertext.  For every plaintext letter entered, a lamp would light to display the encrypted letter.

Mechanically, the heart of the Enigma machine was a set of three rotors which changed the encryption key on a letter-by-letter basis.  pressing a single key on the keyboard would cause an electrical charge to pass through the rotor system.  At the end of the path, the charge lighted the lamp indicating the encrypted letter.  Between letters, the rotors would change position, which would completely change the circuit layout.  If the same plaintext letter were entered multiple times at the keyboard, it would produce a different ciphertext letter each time.

Although the rotor system was complicated in itself, several other factors made Enigma even more difficult to break.  Although the machine used only three rotors at a time, Enigma sets had a total of five rotors, and all were interchangeable.  The advance of the rotors between letters was similar to a car odometer.  If  the initial position of the rotors was AAA, it would then advance to AAB, AAC ... AAZ, ABA, ABB, etc.  The initial position of the rotors was another factor that could change the encryption scheme.

This was the real strength of Enigma -- there were so many ways to configure the machines that, with each change, a huge huge exhaustive search was required of cryptanalysts to find the new settings.  With five rotors to choose from for three positions in the machine, there were 5x4x3=60 ways to to place the rotors.  For a 26 letter alphabet, each rotor could be placed in one of 26 starting positions.  That means for any specific set of rotors, there are 26x26x26=17567 possible initial setting for three rotors.  With only these two factors, we now have 60x17567=1054560 (more than a million!) ways to set up the Enigma machine.  These settings changed on a daily basis, so every day the code breakers were starting over to find these settings.

The Germans were very confident in their system and so they were not as careful as they could have been in preventing the code from being broken.  The Germans sent enough messages using Enigma that the Allies had no lack of sample code to work with.  In addition, many field operatives neglected to change the rotor configurations as often as they should have, thereby negating one of the primary advantages of the system.  Finally, the Germans trusted the security of their system so much that they stopped trying to improve it.  By periodically increasing the complexity of the Enigma rotor scheme, the system would have been virtually unbreakable.

Computer-Based Cryptography

The invention of the modern computer changer the face of cryptography by increasing the speed of exhaustive searches by orders of magnitude.  Most of today's widely used cryptographic schemes are highly mathematical and depend on numeric keys that are large enough to be unsearchable by a computer.  An 8-bit key offers minimal protection because it allows only 256 (2 to the 8th power) possibilities -- a computer can search all 256 choices in a matter of moments.  A 128-bit key has 2 to the 128th power possibilities, or about 3.5x10ee38 possible values.  An exhaustive search over a field of that size is unreasonable by today's computing standards.
 

Back to Index