Information is power. Whether it is national secrets or the telling words of a wayward partner, exposure of messages and missives can change the course of people's lives and the success of nations. Hence why so much effort has been expended over the centuries on the encryption of messages and documents. But how did we get to today's encryption technologies, how do they work, and how safe are they?

Early Forms of Cipher

Most people's first interaction with hiding the content of messages is the Caeser cipher. This substitution cipher lays two copies of the alphabet next to each other, but with the second copy shifted by several positions. Thus, if A is set to E, B becomes F, and so on. To anyone intercepting the message, it looks like garbled words. Further confusion can be attained if the letters of the Latin alphabet are replaced by Cyrillic or Greek letters or symbols.
 
Ceaser Cipher - Encryption article
The Ceaser cipher replaces the letters in the original text with letters shifted by
a few places. Here E replaces A, F replaces B, and so on.
 
Mx'w e psx sj jyr avmxmrk evxmgpiw jsv Ipioxsv!
An example Caeser cipher that you can try to decode here.

Another critical aspect of a cipher is the ease with which both sender and receiver can prepare and decode the message. Both sides also need to agree on the setting of the code wheel. Once known, both sides can communicate securely but also with relative ease. 

Breaking the Cipher

Of course, deciphering the content of such communication is not especially difficult. However, some things must be known before attempting to break such a code. Firstly, you need to figure out the language of the encoded text. Without this information, it is impossible to know what words could be in the message. From here, patterns and frequency analysis can be used to break the code. For example, English uses many three-letter words (the, and, why, how). Furthermore, certain letter combinations occur regularly (qu, th, ck, ly, ing). Finally, some letters appear more often (e, t, a, o, i, etc.) and others less so (x, q, z).

Thus, with a bit of time, a pencil, and some paper, pattern matching can be used to figure out which letter was encoded with which letter in the cipher. If the text is long enough, frequency analysis can highlight likely candidates for enciphering e, t, a, and other frequently used letters and combinations.
 
Freq Analysis - sml. Encryption article
The histogram on the left shows the frequency of letters used in English texts.
The histogram on the right is the frequency analysis fora Caeser
cipher encoded text. It looks like the letters in the text have all been
shifted right by 5 places (A to F, B to G)
There are some key points to note here. Firstly, the person deciphering the message doesn't need to know how it was enciphered. If they do, it speeds up the journey to success, but the process will eventually deliver both the message and the enciphering method. The second is that the above approach does not even reference the use of a computer. With enough time and experience with languages, ciphers were eventually broken long before the development of mechanical calculating machines.

Obscurity Is Not Security

The fundamental learning here is that obscuring the method used to encipher a message doesn't necessarily make it stronger. As is often stated, obscurity is not security. And it is not just the encryption used; how the system’s implementation uses the encryption can be the weakness. You can have the best lock and key solution in the world, but if the door is made of cardboard and the room has a glass window, attackers have more straightforward ways of breaking in.

Many of the security systems that have been broken over the past decades are because failings were found in the implementation, even though their implementations were kept secret. Examples include KeeLoq for remote entry car keys and GSM encryption.

In the 1970s, as computers were growing in use, it became clear that they could be used to secure communications in a manner that was better than anything previously used and to a much higher level of security. Rather than encrypting each letter of a document, the document could be encrypted in binary using the 1s and 0s of the stored data. This would include the content of both upper and lower-case letters and punctuation. Next, the data could be worked on in any format and not just in the 7-bit format used for ASCII. Another challenge was standardization. In order for two people to share an encrypted message, both would need to use the same algorithm. If there were multiple algorithms in use, it would be difficult to transfer data between parties.

The National Bureau of Standards in the US set out to resolve this challenge. IBM had a commercial product called Lucifer that provided a high enough level of security that, at the time, was impossible to break with the computing power available for the near future. This became the Data Encryption Standard, or DES, offering protection with a 56-bit key. However, the challenges didn't end here. Although the algorithm was shared, both parties needed the key used to encrypt the data being shared. So the next challenge was, how do we securely share keys?

Resolving How To Distribute Keys

In his book, The Code Book: The Secret History of Codes and Codebreaking, Simon Singh notes that "The problem of key distribution has plagued cryptographers throughout history." Codebooks had to be distributed during World War II so that Enigma operators could communicate securely. Even with DES, the US government had to distribute keys on paper tapes and floppy disks to staff worldwide to guarantee the security of their communications. The myth was that the key distribution problem could not be solved. 

Luckily, two men, Whitfield Diffie and Martin Hellman, were not into myths. Working together and thinking through approaches to the problem, they come across a possible solution. Their idea revolved around sending a secret message in a box. The sender, typically referred to as Alice in descriptions of encryption methods, places her message in a box and places a padlock on it for which only she has the key. She sends this box to the recipient, typically named Bob. Of course, Bob cannot open the box as Alice has the key to her padlock.

This is where the clever part occurs. Bob places his padlock, for which only he has a key, on the box. He then returns the box to Alice. She now removes her padlock, leaving the message still secure thanks to Bob’s padlock. In a final step, the box is sent back to Bob who removes his padlock and retrieves Alice’s message.
 
Alice Bob Padlock. Encryption article
Diffie and Hellman figured out that a secret could be shared between two
people without first having to share a common encryption key.

From Padlocks to Math

While the process proves that a message can be securely passed from one party to another without first sharing a common key, one challenge remains: How do you implement the idea mathematically? The solution was found in one-way functions — mathematics that is easy to perform to get a result but challenging to reverse from the result back to the original values used in the calculation. It was modular arithmetic that came to the rescue. Using this approach, Alice and Bob could share keys with each other publicly, but only they could encode and decode a message sent between them using their private keys. The challenge remained, however, that a key had to be shared.

This all changed after the efforts of Rivest, Shamir, and Adleman who were working at the MIT Laboratory for Computer Science. They discovered that, by using prime numbers, it was possible to create a pair of keys. The public key of the pair could be used by people wishing to encrypt a message to be sent to, say, Alice. But, using her private key, only Alice could decode the message. The result of their work led to RSA public-key cryptography.

How Secure Are Our Encryption Algorithms?

Today’s news is not short of ‘hacking’ stories but, in most cases, access to encrypted data is broken by using social engineering to steal passwords and access details, not the encryption method. So, how long do we have until today’s encryption technology is cracked?

Cryptography relies on techniques that take too long to attack using today’s computing technology. When it was developed in the mid-1970s, Data Encryption Standard (DES) was considered very secure. However, by the mid-1990s, the custom hardware “Deep Crack” could typically determine DES keys in less than 4.5 days. It used a combination of massively parallel key testing combined with shortcuts that reduced the time needed to find the key used.

Today, Advanced Encryption Standard (AES) is the algorithm used for encryption and, despite much research, has yet to have been broken. However, with quantum computing on the horizon, there is a risk that this could be compromised too. Thanks to work by Peter Shor, a quantum computing algorithm exists that simplifies the calculation of prime factors. As a result, the race has already started to find post-quantum cryptography solutions to ensure that our secrets remain, well, secret.