Origins and the history of Encryption

If the entire span of human evolution is compressed into the pages of one book, most of the bookmarks and chapter changes would be found around the evolution of communication. From the exchange of ideas to establishing relations, communication is perhaps the conceptual equivalent of the wheel. But unlike the wheel, not all communication has always been meant for everyone out there. Privacy and secrecy have been interlaced into human communication for almost as long as we can think of. Don’t you think even the stone age man carefully guarded the designs of his latest tools and only shared them once he was completely sure it wouldn’t go into the wrong hands? We might not have any concrete evidence of the same, but it is quite natural that he adopted some form of modified communication, as in, encryption, to achieve this secrecy. For confirmation, we may have to wait till we find the first stone age love letter.

Based on the evidence that we do have, the first instance of encryption and the science of cryptography dates back to ancient Egypt. Modifications of their hieroglyphic alphabet was found in several tombs and ancient remains dating back to 1900 BCE, with their objectives ranging from secrecy to dignified epitaphs to even plain amusement for the literate population. In fact, most intelligent civilisations did use some form of encryption and ciphers in their literature and military communication. “Arthashastra”, an ancient treatise on statecraft written and modified by Chanakya between 2nd Century BCE and 3rd Century CE, mentions the usage of secret writing in Indian espionage.

One of the most commonly cited historical examples of cryptography and ciphers is the Caesar cipher, which is also reportedly the first popular military cipher. This simple substitution cipher, where each letter was replaced by the letter which was 3 places after it on the alphabet, was used by Julius Caesar around 100 BCE to communicate with his generals on the warfront. It is easy to see that this type of cipher is highly susceptible to breaking. In fact, even if you consider that the letters could be substituted by another letter which could be any distance further from 1 to 26, all it would take is 26 people trying the possibilities till at least a single word makes sense. But this was still quite secure at that time because most of Caesar’s enemies were illiterate or assumed it to be some strange foreign language.

Scytale, a battlefield tool used by ancient Romans with transposition ciphers 

There are a number of historical examples where a stronger or perhaps even a weaker encryption method would change the course of history. Take the example of Mary, the Queen of Scots. Accused by the British Crown of plotting the assassination of Queen Elizabeth, she was under trial for treason and all her co-conspirators were arrested and their assets seized. Among those assets were the letters that contained her agreement to the plot. Unfortunately, Queen Elizabeth’s Principal Secretary to the throne was also the British Spymaster. The letters, which used a nomenclator encryption scheme that replaced letters and words with symbol, ultimately went on to become the damning evidence required for Mary’s execution. If only her co-conspirators had found a treatise published in 1586, the very same year in which she was executed.

In 1460, Florentine polymath Leon Alberti proposed two cipher-alphabets and a switch between them during encryption. This method was further refined by Blaise de Vigenere almost a century later in 1586. Due to the novelty of the method, the entire process was misattributed to Vigenere and the cipher was deemed unbreakable. Interestingly, in a battle of ego between Charles Babbage and John Thwaites to prove that Thwaites’ ‘new cipher’ was essentially a modified Vigenere, Babbage eventually broke the cipher by a method which would later be published in 1863 by Friedrich Kasiski as the Kasiski Test. A four century old cipher stronghold was almost publicly broken in an ego-clash.

Not too long before that, when Edgar Allan Poe wrote “The Gold Bug”, a treasure hunt story with cryptography as one of the crucial plot devices, he definitely had no clue that less than four decades later, a series of three ciphertexts would be published as a pamphlet, allegedly containing the location of a treasure buried by a man named Thomas J. Beale in the 1820s. The pamphlet contained other information as well, such as the actual deciphered plaintext of the second paper, and the information that the key used was the “Declaration of Independence”. Sounds familiar? Nicolas Cage‘s “National Treasure”, anyone? The treasure’s existence is yet to be confirmed since the other ciphertexts still lie undeciphered.

Towards the end of the 19th century, the field of cryptography was very chaotic. Babbage and Kasiski’s destruction of the Vigenere cipher sent cryptographers running after schemes that could once again make business and military communication secure. Moreover, Marconi had invented the magical radio that could seemingly transmit information wirelessly across vast distances, but with the weakness of being received and intercepted by anyone. Reliable encryption became a necessity.

Even with this necessity, the need wasn’t actually fulfilled during most of the first world war, and the period of 1914-1918 was marked by a series of catastrophic cryptography failures. Perhaps one of the most significant ones was Germany’s infamous Zimmerman telegram. Before a planned naval attack on the British navy which would affect American ships as well, German foreign minister Arthur Zimmerman sent a telegram to the Mexican president, detailing a proposal for a planned invasion of America by Mexico if America chooses to join the Allied forces post the naval attack. The decryption and subsequent revelation of the telegram by the British eventually led to America joining the Allied forces which was a very decisive event during the first world war.

Enigma is a name that has been the source of bafflement for almost an entire generation of cryptanalysts. In 1918, German inventor Arthur Scherbius, bothered by the consistent failures of his country’s encryption systems, designed a mechanised version of Alberti’s cipher disc, which in turn was a mechanization of the Vigenere Cipher. Called Enigma, this would go on to become the most feared encryption system in history. The original construction consisted of mainly three components:

• A keyboard for entering plaintext letters
• A scrambling unit for encrypting each plaintext letter
• A display board to indicate corresponding ciphertext letter
   

A labelled Enigma with the parts highlighted

Further modification were done to the device to make it more secure, such as multiple scrambler units, rotation of scramblers, using reflectors, rearrangement of scramblers, using a plugboard. To state it simply, a key press on the Enigma keyboard lit up a corresponding alphabet on the display which was the ciphertext equivalent, and the intermediate scramblers kept rotating with each key-press to ensure that each press followed a different electrical pathway. And the deciphering process was simply the opposite of the same, as in, keying in the ciphertext revealed the plaintext, as long as both the encoder and the decoder machines were started with the same initial settings. These settings were communicated via codebooks, which, needless to say, became highly decisive and desirable objects for the military, especially with the world falling head first into the Second World War.

In the light of their success from the First World War, the focus of the Allies on cryptanalysis was reduced greatly, as they had started considering themselves unbeatable. Poland, on the other hand, was sandwiched between its two enemies, Russia and Germany, was desperate for cryptographic breakthroughs, especially when they encountered the Enigma around 1926. And finally, when they did get this breakthrough, it was one with its roots in espionage. Hans-Thilo Schmidt was just another disaffected German who had lost both his military rank as well as the business he tried to establish post the first world war and the Treaty of Versailles. Unfortunately for the Germans, Hans’ elder brother Rudolph was not only a high ranking official in the German army, he was responsible for securing communication and it was he who officially sanctioned the German army’s use of the Enigma. It was this very brother who got him a job in the office through which all the secure communication was sent. Needless to say, a disgruntled Hans, impoverished and needy in Berlin, pushed by his envy for his brother, didn’t take long to turn on his brother, as well as his country, and sold the basic instructions for using the Enigma machine to a French secret agent for 10,000 marks ($30,000 in today’s value). This information in turn was passed on to Poland, due to an agreement between the two countries.

Even though the Polish could effectively reconstruct an Enigma now, the true secrecy of the machine lay not in the machine itself, but the initial setting of the machine. On top of that, Germans were incorporating newer methods to complicate the encryption even further. Undaunted, the Polish invited 20 mathematicians for a course on cryptography. Among them was 23 year old Marian Rejewski. Rejewski’s strategy to break the Enigma focussed on analysing repetitions of any and every kind, and almost after a year of chasing a particular trend regarding letter chains, the Enigma machine finally gave way to Rejewski’s determination and German communications were transparent. Even with their modified schemes, Rejewski went ahead and designed a mechanised way of finding a decryption using a number of Enigma machines in parallel. This arrangement was named as a bombe.

A 4 rotor US Navy Bombe in operation.

It was finally in 1939 that Rejewski’s efforts had to be in vain when the Germans added two new scrambler units and four plugboard cables. In a desperation to maintain their cryptographic superiority against Germany, Poland shared the Enigma decryption process and other intelligence with the British and the French. The British, now with this fresh intel as well as an Enigma machine spared by the Polish, set up a think tank of their own in Bletchley Park, bringing together the best mathematicians, chess players, scientists of the country to deal with Enigma at a much larger scale than ever before. Bletchley proved to be invaluable during the Second World War as it helped the Allied forces predict and counter several invasions and attacks by Germany. Part of the reason behind this success was the interesting mix of people filling the rooms in Bletchley Park. A puzzle passed around that crowd was bound to find someone who had the mental acuity required to solve it. One of the most significant person to do so was Alan Turing.

Turing utilized the vast repository of decrypted messages in Bletchley park to predict parts of encrypted messages. Once this prediction was made, it placed several constraints on the allowed initial conditions on the machine. Turing himself designed a machine to try out the possible combinations until the message made sense. With this breakthrough and the continued efforts of the residents of Bletchley Park, the war was shortened by many years. Unfortunately, Alan Turing did not live long enough to bask in the glory of their accomplishments, as he committed suicide after he was persecuted and humiliated for being homosexual and forced to undergo medical treatment. The world had again lost a genius to its own narrow mindedness.

After the war, the role of the computer in the battle between cryptographers and cryptanalysts gradually became more significant. A series of technological breakthroughs brought computers, and computer encryption, a lot closer to wide usage. But despite a widespread standardisation of Business data encryption with Data Encryption Standard (DES), one of the major problems that plagued the scale of communications was the exchange of keys. The next breakthrough needed was a safe way to exchange encryption keys. Whitfield Diffie, an independent security expert in the 70s, was no stranger to the significance of the discovery of such a method. Together with Martin Hellman and inspired by Ralph Merkle’s work on public key cryptography, he devised a method which did not require the sender and the receiver to meet. In half an hour of frantic scribbling, thousands of years of cryptography was forced to rewrite its rules.

Theoretically, Diffie had a brilliant model – an asymmetric key model where anyone can encrypt a message using the receiver’s public key which can then be decrypted by the receiver using his or her private key. But this method still awaited the appropriate mathematical function required to make it reality. By the end of 1976, they shared their work with the world, and less than a year later, the team of Ron Rivest, Adi Shamir and Leonard Adleman at the MIT Laboratory for Computer Science wrote the outline of a paper that detailed a method titled RSA, which would go on to become the most influential cipher in modern cryptography. Without going into the technical details, we can tell you that with a very simple choice of two sufficiently large numbers during the encryption, it can take all the computers in the world working together even a 1000 years to break a standard bank encoding. It is not a surprise that this process has become standard practice, and the keys used now would take longer than the span of the universe’s existence to be broken.

Initially, computers powerful enough to run such encryption algorithms were only in the hands of the government, the military or big businesses. With the advent of the Information age, and the technological breakthroughs that made powerful computing a lot more accessible than it ever was, privacy and security became public concerns. Phil Zimmerman was one advocate of widespread usage of strong encryption, which also resulted in him being branded as an arms dealer (well, that sounds like it escalated quickly!). The real concern was with a software developed by him, Pretty Good Privacy (PGP) which was the first solution to put all the theories and algorithms together in one comprehensive easy to use product, which ran on most moderate computers. The government programs to scan emails, digital communications, faxes would have been rendered useless in the face of such a program, had it not been labelled illegal “banditware”.

A quantum encrypted future

If you have made it a point to avoid physics post school life, we don’t blame you. Although, if you haven’t, then you might have heard all the buzz created by the progress being made in quantum computing. We’ve come a long way from feebly trying to understand the concept to actually making quantum computing available to everyone (If you think we are joking, Check out this). With these developments, doors to quantum cryptography are opened. A computer that can simultaneously perform calculations on, say 128 bits, will effectively bring down the decryption time of algorithms like RSA to a comprehensible, and actually executable time. If a viable quantum computer is built, which might have been already done by government agencies in secrecy, it would render all such algorithms useless and there would be a need for a quantum cryptography method. And once that is done, decrypting that would mean disproving quantum theory, shaking the very understanding we have of the universe. Sounds pretty unlikely. So, if this encryption comes to reality, you can finally declare that the battle between cryptographers and cryptanalysts is over, and the cryptographers have won. A perfectly secure lock would be at the disposal of governments, military, business and public, which includes known and potential criminals. All we can say at this stage is, we have to decide what we are more scared by – an all seeing government, or perfectly immune criminals. 

The Kryptos sculpture at CIA, Langley, Virginia

This article was first published in the June 2016 issue of Digit magazine. To read Digit's articles first, subscribe here or download the Digit e-magazine app.

Follow Us

Arnab Mukherjee