When checking your email over a secure connection, or making a purchase from an online retailer, have you ever wondered how your private information or credit card data is kept secure?
Our information is kept away from prying eyes thanks to cryptographic algorithms, which scramble the message so no-one else can read it but its intended recipient. But what are these algorithms, how did they come to be widely used, and how secure really are they?
Coded messages
The first cryptographic methods actually go back thousands of years to the time of ancient Greece. Indeed, the word “cryptography” is a combination of the Greek words for “secret” and “writing”.
For example, the Spartans famously used a system where they wrapped a piece of papyrus around a staff of a certain girth, and wrote their message down the length of the staff. When the papyrus was unravelled, the message was jumbled until it reached its destination and was wrapped around another staff of the correct circumference.
Early encryption algorithms like these had to be applied manually by the sender and receiver. They typically consisted of simple letter rearrangement, such a transposition or substitution.
The most famous one is the “Caesar cipher”, which was used by the military commanders of the Roman emperor Julius Ceaser. Each letter in the message was replaced in the encrypted text – the ciphertext – by another letter, which was shifted several places forward in the alphabet.
But over time such simple methods have proved to be insecure, since eavesdroppers – called cryptanalysts – could exploit simple statistical features of the ciphertext to easily recover the plaintext and even the decryption key, allowing them to easily decypher any future messages using that system.
Modern computing technology has made it practical to use far more complex encryption algorithms that are harder to “break” by cryptanalysts. In parallel, cryptanalysts have adopted and developed this technology to improve their ability to break cryptosystems.
This is illustrated by the story of the Enigma cryptosystem used by the German military during the Second World War, as dramatised most recently in the movie The Imitation Game.
Enigma’s relatively complex encryption algorithm was implemented using electromechanical computing technology to make it practical for German military communications. An extension of the same technology was used by the “bombe” machines of the British cryptanalysts to make it practical to break the cipher.
Current cryptosystems
The cryptosystems in wide use today have their origins in the 1970s, as modern electronic computers started to come into use. The Data Encryption Standard (DES), was designed and standardised by the American government in the mid 1970s for industry and government use. It was intended for implementation on digital computers, and used a relatively long sequence transposition and substitution operations on binary strings.
But DES suffered a major problem: it had a relatively short secret key length (56 bits). From the 1970s to the 1990s, the speed of computers increased by orders of magnitudes making “brute force” cryptanalysis –- which is a simple search for all possible keys until the correct decryption key is found –- increasingly practical as a threat to this system.
Its successor, the Advanced Encryption Standard (AES), uses minimum 128-bit keys by contrast, and is currently the most popular cryptosystem used to protect internet communications today.
Key problem
The AES also has limitations. Like all earlier cryptosystems, it is known as a symmetric-key cryptosystem, where the secret key is known to both the sender who encrypts the message (lets call her Alice), and the receiver who decrypts the message (lets call him Bob).
The secret key, being secret, cannot simply be exchanged over a public communication channel like the internet. If that was intercepted, that would compromise all future encrypted messages. And if you want to encrypt the key, well that produces another problem of how to secure that encryption method.
So, Alice and Bob must first use a private communication channel, such as a private meeting in-person, to exchange the secret key before they can use the cryptosystem to communicate privately. This is a significant practical hurdle for internet communications, where Alice and Bob often have no such private communication means.
To overcome this hurdle – known as the key distribution problem – an ingenious different type of cryptosystem, called an asymmetric-key, or public-key, cryptosystem was devised in the 1970s.
In a public-key cryptosystem, the receiver Bob generates two keys: one is a secret key that Bob keeps to himself for decryption; while the second is a public encryption key that Bob sends to Alice over a public channel. Alice can use the public encryption key to encrypt her messages to Bob. But only Bob can decrypt it with his private key. It thus provides a solution to the key distribution problem of symmetric-key cryptosystems.
In practical applications, due to the higher computational demands of public-key systems compared to symmetric-key systems, both types of cryptosystems are used. A public-key cryptosystem is used only to distribute a key for a symmetric key system like AES, and then the symmetric key system is used to encrypt all susbequent messages.
Consequently, the resulting privacy depends on the security of both symmetric and public key cryptosysems in use. The most commonly used public-key cryptosystems in use today were devised in the 1970s by researchers from Stanford and MIT. They are known as the RSA cryptosystem (from the initials of the designers, Ron Rivest, Adi Shamir, and Len Adleman) and the Diffie-Hellman system, and make use of techniques from an area of mathematics known as number theory.