An Introduction and Brief History of Cryptography and Codebreaking

We take a look at the history of cryptography and how works, how it is used, and misuesd, to secure communications, and the future.

Cryptography was made famous by the German Enigma cypher, used in World War II for encryption of very high-level general staff messages and the subsequent decryption at Bletchley Park, UK. Cryptography is now widely used in everyday life from credit cards to browsing the internet.

Cryptography dates back to ancient Mesopotamia where clay tablets show encrypted recipes, while around 5-600BC Hebrew scholars made use of simple monoalphabetic substitution cyphers. A cypher is an algorithm for performing encryption and decryption.

What Does Privacy Mean To Us?

Everyone has something to hide and thanks to the most recent developments in codes and encryption, the art of concealment has never been easier.

A US study of companies with over 1,000 workers has found that 63% either make use of or plan to employ staff to read or otherwise analyse outbound emails. It also found that 93.6% of companies monitor their employee's email via an automatic system.

Your employer isn't the only one interested in what you have to say.

Echelon, an international computer network run collectively by the governments of the United Kingdom and the United States since the 1970s which intercepts massive numbers of personal communications, scanning them for key phrases about activities that "they" would rather you didn't engage in.

So where does our fundamental right to privacy fit into this? US computer scientist Philip Zimmermann once asked himself that same question and very nearly went to prison for his answer. Zimmerman's speciality was cryptography or code construction. He devised a computer program known as Pretty Good Privacy  (PGP) that enabled the typical desktop computer to scramble email messages with military-grade encryption, strong enough that even governments could not crack. When he started distributing this software in 1991 free to anyone who wanted it, the National Security Agency (NSA) was, to put it mildly, not best pleased.

The agency accused Zimmermann of violating the US International Traffic in Arms Regulations, legal machinery generally reserved for dealing with arms traders. The charge was however dropped, and PGP continues to be available today, however, the message was loud and clear: cryptography is a big deal.

History of Cryptography

The ancient Egyptians are believed to have been the first to make use of cryptography, over 4,000 years ago using hieroglyphs. In the 16th century, the British had gained a reputation for intercepting the communications of overseas diplomats; so much, so that many foreign governments began encrypting their important messages using simple codes. In response, Britain founded its first intelligence department, devoted to decoding those encoded messages.

Among the successes of these Elizabethan codebreakers was the foiling of the plot to replace Queen Elizabeth I with Mary, Queen of Scots, culminating with Mary's execution.

The most notable, and well-known, triumph of Britain's codebreakers took place 350 years later, during World War II. In 1938, with war looming on the German-Polish border, the so-called Government Code and Cipher School (GC&CS) set up a codebreaking centre to decipher enemy transmissions at Bletchley Park, in Buckinghamshire. The centre had the codename, Station X. Britain's codebreakers had been some of the greatest mathematical minds of the century and by the end of the war, they'd broken the Nazi's most sophisticated encryption system: the Enigma.

Enigma was the brainchild of German genius Arthur Scherbius. The notorious encryption machine was available for civilian use in 1922 as a way of securing communications for banks and other sensitive businesses. Four years later the German government adopted it for military use. Weighing 13kg, the Enigma machines were the first portable mechanical encryption equipment of their kind. Three 26-toothed cogs formed the core of its encoding engine, producing a complex mapping to encrypt each letter of the text.

Enigma was a highly sophisticated system for its time. Aided by the work of Polish codebreakers who cracked the first version of the code in the mid-1920s, mathematician Alan Turing, one of Bletchley Park's chief codebreakers, set about unravelling it. His first stroke of genius was the creation of the Bombe machine: a complex system mimicking the guts of the Enigma. The Bombe generated thousands of possible encryption keys.

A checking machine then established which of those were logical probabilities and which were not. Whittling down the Enigma's 150 million million million conceivable combinations to around 7,000. These were then laboriously analysed by hand until the proper one was found.

View my Bletchley Park Codebreakers photo gallery!

The chief use of the Enigma used to be in encrypting Germany's naval communications, in particular coordinating the efforts of its U-boat fleet, which by 1943 had a stranglehold on North Atlantic shipping. Churchill is quoted as saying. "The only thing that ever frightened me during the war was the U-boat peril."

The continued breaking of Enigma allowed Allied naval strategists to vector aircraft and destroyers onto known U-boat locations while steering convoys around them. It is estimated that the Enigma's downfall shortened the war by an estimated 3 years.

History of Cryptography Hitlers Security

But the Enigma wasn't the only German code. The Lorenz cypher was the encryption machine used to safeguard Hitler's private communications with his Generals. Invented by American Gilbert Vernam in 1918, the device was ingeniously simple, using a distinct mathematics operation to add obscuring characters to a message. Providing the obscuring characters were random, the cypher would be unbreakable.

Nevertheless, in 1943 Station X broke the Lorenz cypher. A handful of lazy slip-ups by German operators proved enough for Bletchley's code breakers to spot the cypher's structure. The mechanics of it were nonetheless too complex to implement efficiently by hand, and Tommy Flowers, a Post Office engineer, was commissioned to design and construct a device to decipher the Lorenz system.

The result was Colossus, the world's first computer. The machine was constructed using 1,500 valves, a bank of relays, an outdated IBM teleprinter and a ticker tape drive. It spun the tapes at around 30kph, reading 5,000 characters per second.

Colossus hacked down the time taken 10 decipher a message in Lorenz cypher from a month, by hand, to just a few hours. Colossus was well ahead of its time; its parallel design meant the algorithm that ran on it would not perform much faster on a modern Pentium PC.

Ten Colossus machines were built by the end of 1944. Altogether, they deciphered 63 million characters of high-grade German messages. After the war, the Government was anxious to keep its advanced code-breaking technology as secret as possible, and by 1960 all ten of the machines were destroyed and their design plans burnt.

History of Cryptography - Post WWII

It may have been the end of Colossus, however, it was by no means the end of the British Government's codes and cyphers programme. In 1952, GC&CS moved from Bletchley Park to a brand new base in Cheltenham, Gloucestershire, and changed its name to Government Communications Headquarters (GCHQ). It was there that British researchers discovered one of, if not the most secure encryption techniques to be implemented so far.

The weak link in a traditional encryption system is in distributing the system's key secretly to all recipients. However, in the early 70s, GCHQ researchers James Ellis, Clifford Cocks and Malcolm Williamson devised an encryption system that was free from this problem. In their system, you'll be able to tell the key to whoever you like, in confidence that only a message's intended recipient will be capable to read it.

The system works using some smart yet simple maths. The intended recipient of the message picks two very large prime numbers, that is numbers which can only be divided by themselves and the number one. These form the secret key needed to read the message, which is not revealed to anybody. Multiplying these two numbers together, however, produces what is called the public key, which the recipient broadcasts to all and sundry.

Encrypting a message using the code only calls for knowledge of the public key, so anyone can do it. To decode that message requires factors, which are only known to the recipient. The clever part of the code rests in the fact that whilst it is easy to multiply two large numbers together, splitting one large number into its factors is exceptionally hard. Therefore, the secret key is extremely hard to obtain.

The discovery of this system is often credited to a team of US researchers at MIT, however, that is only a result of GCHQ's dedication to absolute secrecy in the interests of national security preventing the British team from telling a soul about it.

The GCHQ team referred to as the system non-secret encryption. It was later known as public key encryption, and RSA, after the initials of the MIT team who, unlike Ellis, Cocks and Williamson, were allowed to go public with their findings.

The Communications and Electronics Security Group (CESG), the division of GCHQ now dealing with cryptography, only released Ellis' account of his team's discovery in 1997, a few weeks after his death.

So what encryption systems are GCHQ using? "RSA continues to be in use although they do have other forms of encryption and are looking at even more sophisticated techniques," said one independent researcher, preferring to be identified only as The Gardener. While unable to comment on specific technologies, a GCHQ spokesperson admitted, "We make it our business not only to keep up with emerging technologies but to be ahead of them."

Future of Cryptography

Investigative journalist Duncan Campbell, the author of the recent European Parliament report on surveillance technologies , believes that for their most secure communications, GCHQ has reverted to secret key cyphers with very long keys, as opposed to RSA.

A secret key system may seem like a step backwards, but it is probably the future. The current problem with secret key crypto is in keeping the key secret while it is being distributed. But this could soon change thanks to the emerging field of quantum computing, which many universities and almost certainly GCHQ are currently investigating.

It promises secure encryption by transmitting information locked away in the quantum states of fundamental particles of matter. Quantum theory relies on the idea that matter can exist in more than one state at the same time, a principle known as a superposition. In the popular 'many worlds' view of quantum theory, this is interpreted as an overlap of matter from parallel universes. In addition, this superposition is the secret to quantum cryptography.

"Information is hidden in the superposition, or other universes if you like," says David Deutsch, an expert on quantum information theory at the University of Oxford.

Security derives from a dictum of quantum theory called Heisenberg's uncertainty principle, which says that you cannot measure a quantum state without changing it irreversibly. This ensures that every time an eavesdropper tries to listen in on a quantum message, he or she is guaranteed to leave a signature that can be detected. "Let's say you might need a key of 128 bits," says Deutsch. "You send a burst of, say, 1,000 bits. The system uses most of those to do a statistical check to see whether anybody has measured those bits. The remaining, ones you use as the key."

Initially, the system would be implemented by encoding information into photons of light and transmitting these down fibre optic cables. But experimenters at Los Alamos National Laboratory, New Mexico, are trying to incorporate the system into open-space lasers, that is fibre optics without the fibres. They have so far achieved an effective range of around 500m in broad daylight, but the team confidently speculates that one day the system's effective range could be hundreds of kilometres, enough to beam secure signals to satellites.

Recent events have highlighted the importance of satellite security. Several years ago a hacker calling himself Captain Midnight seized control of a US TV satellite. And earlier this year a British group was reported to have commandeered one of the Ministry of Defence's Skynet satellites. When the Skynet story broke, Geoff Bains, editor of What Satellite? told the Daily Telegraph that current satellite security was so flimsy he was surprised that more spacecraft hadn't been hijacked. The MOD still deny the incident, however.

"There was no breach of Skynet," a spokesperson told news agencies. "It's rubbish."

Deutsch believes that quantum cryptography could be a workable reality for protecting satellites, and other applications, soon. "I would guess that the actual technology is going to be useable within the next ten years," he says. "Though when it'll be used I don't know. Probably after the next embarrassing incident."

Simple Cryptography Examples

Monoalphabetic Substitution

A very simple monoalphabetic substitution cypher would involve one step performed on the original text where letters are substituted. For example, ROT13 is a Caesar cypher where the alphabet is rotated 13 steps.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

becomes

N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

Using this lookup the string "Hello World" will become "Urxxa Jadxq". Quite meaningless to anybody who happens to find the encrypted text, but it is still very easy to crack.

A more secure cypher uses a passphrase to generate the substitution alphabet, where a secret password is chosen, duplicate letters removed and the rest of the alphabet filled in.

For example, a password of novembers becomes novembrs and our new substitution alphabet is:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

becomes

N O V E M B R S A C D F G H I J K L P Q T U W X Y Z

Using this new cypher "Hello World" becomes "Smddi Wilde", which can only be decrypted once the password has been cracked.

Other substitution cyphers can involve substituting numbers or symbols or even pictures (pigpen cypher) to encode text.

Polyalphabetic Substitution Cryptography

As the name suggests polyalphabetic substitution involves more than one substitution alphabet and is substantially more difficult to crack. Multiple alphabets are created and stored in a tableau, usually 26 alphabets of 26 letters. Then, a password or passphrase is chosen and a string is encrypted using the alphabet corresponding to the letters of the password. For example, a password of TODAY would involve using the T alphabet to find the first letter of the cypher text, the O alphabet for the seconds, D for the third and so on. After the Y alphabet has been used revert back to T and start again.

Mechanical Substitution Ciphers

The most important and famous mechanical cypher machine was the Enigma device used by the Germans but also includes devices used by the allies called SIGABA and Typex. These were rotor cyphers where the substituted letter was chosen electrically from a huge number of possible combinations resulting from the rotation of several letter disks. Since one or more of the disks rotated mechanically with each plaintext letter enciphered, the number of alphabets used was substantially more than astronomical.