Aiden A. Bruen - Cryptography, Information Theory, and Error-Correction

Lyon Playfair, Baron of St. Andrews, recommended a cipher invented in 1854 by his friend Charles Wheastone, to the British government and military. The cipher was based in a digraphic 3 substitution table and was known as the Playfair Cipher . The main difference when compared with a simple substitution cipher is that characters are substituted two at a time. Substitution characters depend on the positions of the two plain text characters on a secret square table (the key) whose entries are the characters of the alphabet less the letter “J.”

In 1894, Captain Alfred Dreyfus of the French military was accused of treason and sent to Devil's Island, because his hand writing resembled that of an encrypted document that offered military information to Germany. To prove his innocence, the note had to be cryptanalyzed. To be certain that the decipherers' work was correct, an army liaison officer with the Foreign Ministry managed to elicit another similarly encrypted note in which the contents were known to him. The plain text then showed that Dreyfus had not written the encrypted document, but it took several more years before he was to “receive justice, re‐instatement and the Legion of Honour” [Kah67, p. 262].

Early in the twentieth century, Maugborne and Vernam put forth the basis for the cipher known as the one‐time pad. Although – as was proven later by Shannon – this cipher is effectively unbreakable, its use is somewhat restricted because, in practice, a random key that is as long as the message must be generated and transmitted securely from Ato B. Soviet spies used this cipher, and it is said that the phone line between Washington and Moscow was protected with a one‐time pad during the Cold War era.

Edward Hugh Hebern [Bri97] of the United States invented the first electric contact rotor machine. In 1915, he experimented with mechanized encryption by linking two electric typewriters together using 26 wires to randomly pair the letters. In turn, this led to the idea of rotors which could not only mechanize substitution, but also alphabet shifts as well. The function of the rotor was to change the pairing of letters by physically changing the distribution of electric contacts between the two typewriters. By 1918, he had built an actual rotor‐based encryption machine.

At about the same time (1918–1919) three other inventors, the German Arthur Scherbius, the Dutchman Hugo Koch and the Swede Arvid Damm were filing patents of rotor‐based encryption machines. The Scherbius idea, which included multiple rotors, materialized in the first commercial models having four rotors, ENIGMA A and ENIGMA B in 1923. Ironically, Hebern only filed for patent protection in 1921, received one in 1924 and lost a patent interference case against International Business Machines in 1941. Later modifications to the Scherbius machine including a reflector rotor, and three interchangeable rotors were implemented by the Axis Forces during World War II.

Rotor‐based machines give the possibility to implement poly‐alphabetic substitution ciphers 4 with very long keys or cycles in a practical way. With the advantage of mechanization, the ability of widespread deployment of cryptographic stations and widespread use became a reality. This translated into a larger volume of messages (potentially all messages) being encrypted. However, the increase in traffic gave more cipher text for cryptanalysts to analyze and the probability of operators making a deadly mistake in the management of keys was multiplied.

The timely breaking of the ENIGMA cipher by the Allies was due in part to inherent weaknesses in the encryption machine, mismanagement of keys by the operators and lots of mechanized, analytical work. The cipher was first broken, using only captured cipher text and a list of daily keys obtained through a spy, by the Polish mathematician Marian Rejewski. One of the important players in the mechanization of ensuing breaks was the English mathematician Alan Turing, who also contributed to the establishment of the basis for what is today called Computation Theory.

As a side note, after World War II, many of the ENIGMA machines captured by the Allies were sold to companies and governments in several countries.

Another very interesting cryptographic technique of a different kind was used by the US military in the Pacific campaign in World War II. Secret military messages were encrypted by translating them from English to the Navajo language. For decryption at the other end, of course, the Navajo was translated back into English. Some words describing military equipment did not exist in the original Navajo language, but substitutes were found. For example “tanks and planes” were described using the Navajo words for “turtles and birds.” To avoid the possibility of the enemy getting a handle of the code, the whole system was committed – by means of an intensive training program – to the memory of the translators or “Code Talkers.” This code was never broken.

Immediately after World War II, Shannon was publishing his seminal works on information theory. Almost simultaneously, thanks to the efforts of Ulam, von Neumann, Eckert, and Mauchly another key technological development was starting to make strident progress, the introduction of the newly invented digital computer as a mathematical tool [Coo87].

Figure 1.1(a) Claude E. Shannon, Theseus, and the maze (see Section 1.4). (b) Claude E. Shannon.

Source: Reused with permission of Nokia Corporation and AT&T Archives.

Because of the importance of his contributions to the issues in this book, we present here a brief biography of Shannon, before finishing the chapter with a review of modern developments ( Figure 1.1).

Claude Shannon has been described as the “father of the information age.” His discoveries are everywhere. Waldrop [Wal01] gives an excellent example from the days, not so long ago, where most people listened to music on CDs, before streaming services became so popular.

Pick up a favorite CD. Now drop it on the floor. Smear it with your fingerprints. Then slide it into the slot on the player‐and listen as the music comes out just as crystal clear as the day you first opened the plastic case. Before moving on with the rest of your day, give a moment of thought to the man whose revolutionary ideas made this miracle possible: Claude Elwood Shannon.

Computers give us the power to process information. But Shannon gave us the capacity to understand and analyze information. Shannon demonstrated the unity of text, pictures, film, radio‐waves, and other types of electronic communication, and showed how to use these media to revolutionize technology and our way of thinking.

Shannon was born in Petoskey, Michigan in 1916. His father was a business man who later became a judge, and his mother was a high schoolteacher. As a youngster he was interested in, and became adept at, handling all kinds of contraptions such as model airplanes and boats as well as learning the workings of the telegraph system. At the age of 20, he graduated with degrees in Mathematics and Electrical Engineering from the University of Michigan.

In the summer of 1936, Claude joined the MIT Electric Engineering department as a research assistant to work on an analog computer (as opposed to our modern digital computers) under the supervision of Vannevar Bush. Bush's analog computer, called a differential analyzer, was the most advanced calculator of the era and was used mainly for solving differential equations. A relay circuit associated with the analyzer used hundreds of relays and was a source of serious study by Shannon, then, and later.