The Story of Cryptography

In the first post of this series, we described the early history of cryptography. This included the development and use of the Caesar Box and the Vigenère Cipher, encryption algorithms that pioneered the use of encryption as well as the advent of the encryption key.

It wasn’t until the 20th century that cryptography came into widespread use. Notable encryption milestones from the 20th century include the development and use of the Enigma machine, the creation of the US Data Encryption Standard (DES), and the development of asymmetric encryption.

The Enigma Machine

The Enigma machine is arguably the most famous encryption device to date. It was developed by Arthur Scherbius in 1918 at the end of WWI. The Enigma uses a rotor mechanism and special wiring to scramble the alphabet to easily and quickly create ciphertext from plaintext or vice versa.

When in use, one person types the message on the keyboard, while a second person writes down which letters light up on the light board directly above the keyboard. For example, you may type an "O" on the keyboard, but the "E" may light up on the light board. However, if you type "O" a second time, perhaps a "T" might light up. If you are typing the plaintext message on the keyboard, the letters from the light board would be the ciphertext or vice versa.

But how does it work? The rotor mechanism changes the electrical connections between the keys and the lights with each keypress. To remain secure, the settings on the machine were changed daily based on secret key lists distributed in advance. The receiving station had to know and use the exact settings employed by the transmitting station to successfully decrypt a message. Decryption was accomplished via the same process.

The Enigma machines were infamously used by the Germans in WWII to encrypt radio communications, but versions were also employed by the Japanese and Italians as well.

Cryptanalysis: Cracking the German Code

Breaking the encryption of the Enigma machine was a multistage process. The model in use by the Germans had cryptographic vulnerabilities which ultimately allowed a Polish cryptanalyst, Marian Rejewski, to crack the encryption keys in use. However, he did not have knowledge of the internal wiring of the machines, so he was not able to use this knowledge to break the codes. This information was actually obtained by a French spy, Hans-Thilo Schmidt, along with all of the codes used for encryption during September and October of 1932.

Using the newly obtained ciphertexts from this period, the Polish were able to build a working Enigma machine and decrypt German communications in three short months. This began a "cat and mouse game" between the Germans and the Polish until 1938, when German improvements made decryption too resource-intensive for the Polish to maintain.

In July of the following year, the Polish disclosed their Enigma decryption efforts to French and British military intelligence. This partnership allowed the British to develop their Enigma decryption efforts at Bletchley Park and continue decryption of German communications for the rest of the war.

Lucifer: The Data Encryption Standard

Before the early 1970’s, the use of cryptography was primarily restricted to military use. However, in 1971, the first encryption algorithms for private-use were published. By this time, companies had seen the effectiveness of encryption and were interested in applying it to the protection of their own intellectual property.

The first set of civilian encryption algorithms were developed by IBM under the name "Lucifer." Several different versions were created by IBM, one of which they submitted to the US National Bureau of Standards in hopes of getting it accepted as the national Data Encryption Standard (DES). The version they submitted was initially vulnerable to "differential cryptanalysis," but after some modifications done by the National Security Agency (NSA), IBM’s Lucifer was indeed accepted as the Data Encryption Standard

The accepted version was a "Feistel network," which is a multi-round encryption algorithm whose structure is shown in the images below. The image on the right shows the operations that would be performed in each of the left image’s boxes labeled “F" (for Feistel function).

So, the message undergoes a permutation at the beginning of the encryption process and at the end of the encryption process (boxes "IP" and "FP"), as well as during each round of the Feistel function (the green box labeled "P"). Getting technical, the "E" box in the right image represents an expansion of the half-block from 32- to 48-bits, while each of the numbered "S" boxes represents a substitution table that reduces 6 input bits to 4 output bits. The cipher also has a key schedule, which generates 16 48-bit round keys from the original 56-bit secret key.

Brute-Force Attack on the Data Encryption Standard

As mentioned, the NSA made several different modifications to the Lucifer cipher before it was accepted as the DES. Some modifications, like changing the S-Boxes to protect against differential cryptanalysis, were designed to improve the security of the cipher. Others, like changing the key length from 128-bits to 56-bits, may have been designed to ensure that the NSA still had the ability to break the cipher if needed.

Ultimately, Lucifer, or the DES, was not broken due to cryptographic vulnerabilities, but instead by a brute force attack that took advantage of the limited key space. DES was first broken in 1997, acting as the catalyst for the advent of the Advanced Encryption Standard.

Asymmetric Encryption

The original encryption algorithms used are called "symmetric encryption algorithms." These types of systems require both the sender and the recipient of a message to both have access to the same encryption key. The users are required to set up a secure channel in order to transmit this key before encryption can begin. However, in the 1970’s, the invention of "asymmetric cryptography" changed this.

Asymmetric cryptography, or public key cryptography, uses both a public and a private key in order to encrypt or decrypt data. The keys are typically two large strings of numbers paired together. One key is public, and can be shared with anyone, the other is the private key which is kept secret. If the private key is used to encrypt a message, you would use the public key for decryption and vice versa.

The one-way functions used in most asymmetric cryptography are called "factorization" and "discrete logarithm problem." Technically speaking, the security of these schemes relies on the fact that operations like multiplication and exponentiation are "easy" (with polynomial difficulty), and the inverse operations, factoring and logarithms, are "hard" (with exponential difficulty). Asymmetric encryption algorithms are designed to allow legitimate users to perform "easy" operations while forcing attackers to solve "hard" problems.

The UK’s Government Communication Headquarters’ (GCHQ) cryptographers originally developed asymmetric cryptography in the early 1970’s, though, their results and algorithms remained classified until 1997. The algorithms were independently discovered by private researchers and are named after these parties.

The original key exchange protocol, called D-H, was invented by Malcolm J. Williamson of GCHQ in 1974, but is named after Whitfield Diffie and Martin Hellman, who discovered it in 1976. The RSA algorithm for asymmetric encryption and decryption was discovered by Clifford Cocks in 1973. A more general version was invented by Ron Rivest, Adi Shamir, and Leonard Adleman in 1976. Since then, several different asymmetric encryption algorithms have been invented.

Coming Up: 20th Century Ciphers

The encryption algorithms presented in this article are largely broken, with the exception of the asymmetric algorithms D-H and RSA. However, even the security of these algorithms are threatened by advances in computers. The final post in this series describes some of the modern encryption algorithms currently in use or development that are designed to replace these algorithms as they are broken.