Technology blog::Life hacks::Linux::Hardware::Gaming

History of Cryptography

Just what is this Cryptography?

By , 7th January 2014 in Privacy & Security

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

Want to know a secret? A US study of companies with over 1,000 employees has found that 63% either employ or plan to employ staff to read or otherwise analyse outbound e-mail. It also found that 93.6% of companies monitor their worker's e-mail through an automated system. Your employer is not the only one interested in what you have to say.

Echelon, a global computer network run jointly by the governments of the UK and the US since the 1970's which intercepts large numbers of private communications, scanning them for keywords pertaining to activities that "they" would rather you didn't engage in.

So where does our basic right to privacy fit into this? US computer scientist Philip Zimmermann once asked himself that same question and very nearly went to jail for his answer. Zimmerman's speciality was cryptography or code building. He devises a computer program called Pretty Good Privacy (PGP) that enabled the average 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.

Radomes at Menwith Hill, Yorkshire. Photo taken November 2005.
Image Credit: Credit: Matt Crypto via Wikipedia
Radomes at Menwith Hill, Yorkshire. Photo taken November 2005.

The agency accused Zimmermann of violating the US International Traffic in Arms Regulations, legal machinery normally reserved for dealing with arms traders. The charge was however dropped, and PGP is still available today, but 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 use cryptography, over 4,000 years ago using hieroglyphs. In the 16th century, the British had gained a reputation for intercepting the communications of foreign diplomats; so much, so that many foreign governments began encrypting their important messages using simple codes. In response, Britain founded its first intelligence department, dedicated to deciphering these 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 famous, triumph of Britain's codebreakers occurred 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 were some of the greatest mathematical minds of the century and by the end of the war, they had broken the Nazis most sophisticated encryption system: the Enigma.

Enigma was the brainchild of German genius Arthur Scherbius. The infamous encryption machine was available for civilian use 1922 as a means of secure 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 tools of their kind. Three 26-toothed cogs formed the core of its encoding engine, producing a complex mapping to encrypt each letter of text.

Enigma in use in Russia
Image Credit: Wikipedia
Enigma in use in Russia

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 these were logical possibilities and which were not. Whittling down the Enigma's 150 million million million possible combinations to around 7,000. These were then laboriously analysed by hand until the right one found.

The chief use of the Enigma was in encrypting Germany's naval communications, in particular coordinating the efforts of it's 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 three years.

Hitlers Security

But the Enigma wasn't the only German code. The Lorenz cypher was the encryption system used to safeguard Hitler's personal communications with his Generals. Invented by American Gilbert Vernam in 1918, the system was ingeniously simple, using a special arithmetic 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 identify the cypher's structure. The mechanics of it were still too complex to implement efficiently by hand, and Tommy Flowers, a Post Office engineer, was commissioned to design and build a machine to decipher the Lorenz system.

The result was Colossus, the world's first computer. The machine was built using 1,500 valves, a bank of relays, an old 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.

Aerial photograph of GCHQ main building
Image Credit: Wikipedia
Aerial photograph of GCHQ main building

It may have been the end of Colossus, but it was by no means the end of the British Governments codes and cyphers programme. In 1952, GC&CS moved from Bletchley Park to a 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 systems 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 can tell the key to whoever you like, in confidence that only a messages intended recipient will be able 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 requires knowledge of the public key, and so anyone can do it. To decode that message requires the factors, which are only known to the recipient. The clever part of the code rests in the fact that while it is easy to multiply two big numbers together, splitting one large number into its factors is phenomenally 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, but this is only because GCHQ's commitment to absolute secrecy in the interests of national security prevented the British team from telling a soul about it.

The GCHQ team called the system non-secret encryption. It was later referred to 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 is still 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 in 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 systems 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 actually be used I don't know. Probably after the next embarrassing incident."

Further Reading
Comments

There are no comments for this post. Be the first!

Leave a Reply

Your email address will not be published.