A Brief History of the Science of Secrecy

Written for the Open University ICT portal.

Ever since humans learnt to write, I suspect that they have been writing in codes. As soon as a sensitive message was inscribed on a clay tablet or written on a piece of papyrus, then it must have been foremost in the sender’s mind that it should not be intercepted and read by a rival. The message might have been a military plan, a political plot or a letter to secret lover, but in every case the necessity to encrypt was obvious.

Today, in the Information Age, the need to protect communications from prying eyes is greater than ever before. Cryptography, the science of encryption, plays a central role in mobile phone communications, pay-TV, e-commerce, sending private emails, transmitting financial information, and touches on many aspects of our daily lives.

Today’s technology can be traced back to the earliest ciphers, and have grown as a result of evolution. The first ciphers were cracked, so new, stronger ciphers emerged. Codebreakers set to work on these and eventually found flaws, forcing cryptographers to invent better ciphers and so on. For example, when the monoalphabetic substitution cipher was cracked, the polyalphabetic was invented.

The monoalphabetic cipher simply substitutes each letter of the alphabet with a symbol, so that A might always be replaced with +, and B with 8, and so on. The letter substitutions remain the same throughout a message. This cipher was secure for centuries, until codebreakers noticed that each letter has an average frequency and no matter how the letter is disguised the new symbol will take on the frequency of the letter it represents. The most common letter in English is E, so if a coded message contains lots of Ys, then Y probably represents E. The earliest known description of this codebreaking technique (frequency analysis) dates back to 9th century Baghdad.

In contrast, the polyalphabetic cipher works by using switching the rules of substitution – hence, the ‘poly’. For example, if E appears as the 1st, 3rd, 5th letter in a message then it is substituted for F, but in the even positions it is substituted K. In the other positions, F might represent Z, and K might represent Q. Although F and K represent E, they are not incredibly common in the encrypted message because they share the frequency of E and at other times they represent the rare letters Q and Z.

The Vigenère cipher is an early form of polyalphabetic cipher invented in the 16th century, but the most famous polyalphabetic cipher is the Enigma machine. Invented by Arthur Scherbius, this mechanical version of the Vigenère cipher was used by Germany prior to and throughout the Second World War. Looking rather like a typewriter, each letter on the keyboard was connected to a letter on the lampboard by 26 wires. However, the machine was not hardwired. The wiring passed through rotors, which turned after each key was pressed, so the circuits were continually changing.

A crucial feature of the Enigma cipher (and most crypto algorithms) is that the machine has billions of possible settings, such as the starting orientations of the rotors. Each complete setting is called a key. The Germans knew that a machine would eventually fall into that hands of the Allies, but such a machine could not be used to decipher a message unless the key used to encrypt the message was known. The significance of the key is an enduring principle of cryptography, and it was definitively stated in 1883 by the Dutch linguist Auguste Kerckhoffs von Nieuwenhof: “The security of a cryptosystem must not depend on keeping secret the crypto algorithm. The security depends only on keeping secret the key.”

There were different keys for the distinct communication networks (e.g., the Kriegsmarine or North Africa) and they were changed on a daily basis. Nevertheless, Britain’s codebreakers at Bletchley Park discovered shortcuts to finding the Enigma keys and the cipher was cracked routinely throughout long periods of the war, providing vital information for Churchill.

In the decades after the war, mechanical encryption was replaced with computer ciphers. They operated according to the same principle of substitution, combined with the other foundation of cryptography, namely transposition, whereby the order of the letters (or bits) is altered. Again, each cipher depended on choosing a key, known only by the sender and the receiver, which specified the exact rules of encryption for a particular message. This meant there was still the problem of getting the key to the receiver so that the message could be deciphered. This had to be delivered in advance by a courier, which was an expensive, slow and risky process.

For thousands of years, it had been assumed that there was no solution to the so-called key distribution problem – if you want to scramble a message according to a recipe, then surely the unscrambling recipe had to be given to the receiver in advance. But in the early 1970s, there was a revolution in cryptography known as public key cryptography, which destroyed the key distribution problem. This was a technology that was tailor-made for the Internet. Customers could encrypt their credit card details and send them to retailers on the other side of the world. Penpals who had never met could encrypt emails. Related technologies, based on similar mathematics, also enabled digital signatures, integrity checks and non-repudiation.

These are valuable technologies. For example, if I vote electronically, then I certainly want my vote to be secret, but the polling station needs to know it was me who voted, so that I cannot vote twice – a digital signature guarantees this. An integrity check stops my vote being changed, and non-repudiation guarantees that my vote has been registered.

Although today’s ciphers are effectively unbreakable, researchers continue to develop new security systems. For example, steganography does not hide the meaning of a message, but rather hides the very existence of the message. Previous techniques include invisible ink and microdots. Today, texts can be hidden within jpeg images, so that the image appears unchanged. One of the motivations for modern steganography is the fear that cryptography might be banned by a totalitarian regime that wants to spy on its subjects. But a dictator cannot ban a technology that by definition is hard to find.

In addition to research conducted by industry and in universities, there are still cryptographers working in government labs. The biggest employer of mathematicians in the world is the American National Security Agency. So, although there is plenty of cryptography in the open that can be studied, it is still true to say that to some extent the science of secrecy continues to be a secret science.

To find out more about codes and ciphers, visit the Crypto Corner