Hello, and welcome back, traveler!

This is the third part of our extraordinary journey through time, where we explore cryptography, the art of making a message secret, observe the underlying concepts, play with various mechanisms through historical anecdotes, and see their evolution until today.

In the first part of this series, we traveled all the way back to ancient Egypt and ancient Greece, we identified the origins of cryptography and, since then, we followed the evolutionary trail that led us to the creation of the Cipher disk in the 15th century, and the ingenious Enigma machine in the 19th century.

• Part I: The Art of Cryptography in Ancient and Medieval History
• Part II: The Evolution of Cryptography in Modern History

And now, the time has finally come to conclude this epic travel through time. Let’s explore what the post-modern world had to offer to the art of cryptography and how the configuration of an encryption key works today.

Jump into the time machine for one last time and prepare for time travel!

The evolution of encryption 1970 AD – today

Public key for private messages

We landed in the United States of America, sometime in the 1970s. The computing power of contemporary computers has been replacing rotors and encryption continues to progress rapidly. A prime example of this evolution is the Lucifer Cipher, designed by Horst Feistel, and is considered the precursor of Data Encryption Standard (DES). However, the problem of securely distributing the encryption key that we encountered in a few of our previous stops in time persists in the 1970s as well. Indeed, no matter how complex the method of encryption is, the interception of the key reduces the entire encryption effort to nothing.

Let's imagine for a moment that we initiate an exchange that would make it possible to set up encryption without any prior exchange. This is what the cryptographers Whitfield Diffie, Martin Hellman, and Ralph Merkle invented — the Diffie-Hellman key exchange method.

Fortunately for the average person, there is an analogy and terminology commonly used to understand this method without any special knowledge.

We have two protagonists, Alice and Bob, and the process is as follows:

• Alice and Bob agree on a common public color: yellow.
• Alice has a secret color: red. Alice combines her public and secret colors (yellow + red) and sends orange to Bob.
• Bob also has a secret color: cyan. Bob combines his public and secret colors (yellow + cyan)  and sends light blue to Alice.
• Both Alice and Bod mix the colors they received with their secret colors, So, light blue + red, for Alice, and orange + cyan for Bod. In both cases, the resulting color is yellow-brown.

Tadaaa! They have the same resulting color because they both used a mix of yellow + red + cyan (the order does not matter). The trick is the difficulty of retrieving the original colors from the mixes publicly exchanged. Now, imagine using large numbers instead of colors — it becomes extremely difficult to guess the secret parts.

This method is one of the first cases of public-key cryptography. It is also asymmetric cryptography, as the system uses different keys for encryption and decryption. This method is based on functions easy to apply but impossible, or extremely difficult to revert called one-way functions.

One must be careful not to confuse the key generation part with the encryption part of the communication itself. Indeed, we have just seen that the Diffie-Hellman method is asymmetric, but it is only the creation of a secret that can then be used in symmetric encryption.

The power of primes

We are in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman describe a new public-key cryptosystem algorithm (RSA). The algorithm is based on prime number properties — it is easy to make the product of two primes but very difficult to factorize.

Martin Gardner, an American popular mathematician, and popular science writer, publishes the article "A new kind of cipher that would take millions of years to break". In this article, he challenged his readers to find the secret sentence from the public key and the explanation of the principle. The phrase was "The Magic Words are Squeamish Ossifrage" and was uncovered in 1993 by a large team that used a considerable amount of means to achieve that. But even today, a lot of encryption algorithms are based on primes properties.

Attention! We are entering a zone of mathematical turbulence, please fasten your seatbelts!

For the sake of simplicity, I will just comment on the mathematical formulas without going into details. If your mathematical curiosity is not strong enough, feel free to skip the theoretical part and go directly to the practical application.

As we have seen, the RSA algorithm is based on certain properties of prime numbers, but what are they? We will use several theorems and something that we discover during our stay in ancient Rome: modular arithmetic.

First, the Euler Totient function:

If \( n = pq \), with \(p\) and \(q\) being prime numbers, then \(φ(n) = (p-1)(q-1)\).

Then, Fermat's little theorem:

If \(p\) is a prime number and \(a\) an integer such as \(gcd(a,p) = 1\), the equation \(a^{p-1} ≡ 1 (mod p)\) must be verified. More on the greatest common divisor (GCD) here.

And last but not least, from Euler’s theorem, if \(gcd(n,a) = 1\) then \(a^{φ(n)} ≡ 1 (mod 1)\).

I am delighted to announce that we have passed the zone of mathematical turbulence, we can untie our belts and resume the normal course of our adventures. Now, what do you think about exploring an example with the help of our old friends Bob and Alice?

Alice generates a number \(n\) which is a product of two prime numbers \(p\) and \(q\).

Let's say \(p = 2\) and \(q = 5\), so \(n = 2 x 5 = 10\). Then, she computes \(T=(p-1)(q-1) = (2-1)(5-1) = 4\). Now, to compute \(e\), such as \(gcd(φ(n),e) = 1\), that means a coprime with \(10\) and \(4\), and she chooses \(e = 3\). The public key is \((e,n)\), so \((3,10)\). Alice can share this publicly.

Then, she computes \(d\) such as \(e.d mod T = 1\), so \(3 d mod 4 = 1 Alice choose d = 7\). Now, the private key is \((d, n)\), so \((7,10)\). Bob obtains the public key from Alice \((3,10)\) and will use it to send a message, let’s take a simple number, for example, \(m=2\). Bob now has to solve the equation \(m^e mod n = 2^3mod 10 = 8\) .

Bob sends \(8\), which is the encrypted message, to Alice who will use the private key to decrypt it.

\(m^dmod n = 8^7mod 10 =2\)

Alice successfully decrypts Bob's encrypted message!

This example uses small numbers with tiny exponents. The larger the numbers, the more computing power they require.

RSA, good in every way?

Let’s make a quick stop in the early 1990s. Moore's law seems to apply wonderfully, and computers have more and more computing power. In this context, RSA Laboratory creates the RSA Factoring Challenge to encourage research and prove how robust RSA is depending on the key size.

As we saw in the previous step, the issue is to find the two prime numbers `p` and `q`, such as the RSA number `n = p.q`. The smallest (RSA-100) was found quite quickly by Arjen Lenstra, but as you can see in the challenge history, it was quite a hard task to find all the proposed RSA numbers.

What does this story tell us? First, it is very difficult to crack, and as we had guessed, this difficulty increases as the size of the key increases as well. To this day, and although the challenge is officially over since 2007, teams are still trying to find the prime factors, and guess what — nobody has managed to find beyond RSA-250!

The other thing is that computing RSA is expensive and the common user can’t use it easily to secure data. To solve this problem and to allow a greater number of people to protect their privacy, Philip Zimmermann publishes version 1.0 of Pretty Good Privacy (PGP) in June 1991.

Philip Zimmermann explains in "Why I Wrote PGP" the importance of cryptography to protect privacy and preserve individual liberties. This position provoked a lively debate on the usefulness of backdoors for states, and/or limitations of encryption capacity for ordinary citizens to limit criminal use. In part II, we saw the military applications of cryptography and, whatever our opinion is on that, it is undeniable that cryptography has an on politics and civil society.

But let's go back to the technical side. You may haven’t noticed, but our toolbox has grown considerably.

Just like PGP, we are now able to authenticate an interlocutor in addition to encrypting messages. Wait, didn't you realize that?

With a public key system, we can broadcast our public key to allow our interlocutors to encrypt data that only we can decrypt with our private key. But, if we encrypt a message with our private key, anyone can decrypt it with our public key. You may think this makes no sense, but by doing this, we prove that we are the owner.

A combination works best — we can use both our private key and the public key of the other person to encrypt the message. This way we make sure that we are the respective owners of the private keys and that only the owners of the private keys can read the message. In reality, as always, it is a bit more complex, but what is important is to understand the underlying concepts.

For example, with PGP, the signature is made from the hash of a message then encrypted with the private key and put in the header of the message in plain text. The receiver can then decrypt the hash with the public key and check if this hash corresponds to the one they have calculated by themselves.

It doesn't look like much, but the use of a hash function makes it possible to limit the size of the message to be encrypted and thus limit the computing power needed to encrypt the message used for authentication.

There is still a problem that we have not talked about, and it is to certify that the initial public key is indeed that of the desired interlocutor. Indeed, if a malicious person gives us his public key while pretending to be the right interlocutor, and if they intercept the messages, they will be able to use their private key to decrypt the message and even use the public key of the real recipient to simulate exchanges and perform a man-in-the-middle attack. This is why public and private organizations specialize in public key certification.

So, is that it? Did we find a way to secure all messages, to secure the internet?

Yes, and no. Let’s make a little jump to the mid-1990s.

Secure HTTP in a handshake

In 1994, Netscape Communications Corporation developed the original SSL protocol, and although it comes with a number of problems, it is the cryptographic protocol that will dress HTTP with an S (security) and give us HTTPS.

SSL, in time, will be replaced by its successor, TLS, which is still used to secure many resources on the internet. Extraordinary coincidence, you are currently reading an article on a secure website. How about taking a look at what our browser is telling us?

In my case, it's Firefox. We have to click on the padlock next to the address, then on Connection secure, then on More information.

We can see that the website uses a Certificate issued by Let’s Encrypt, which is a trusted third-party authority.

We will focus on the weird string that starts with TLS. Let’s figure out what that means.

This long string is the cipher suite and will define how TLS will secure the connection.

• TLS, defines the protocol that this cipher suite is for. Yes, we are doing TLS 😉
• ECDHE is the key exchange algorithm, in this case, a Diffie-Helman with an elliptic curve. It is the way we exchange keys between the server and the client.
• RSA is the public key authentication mechanism (during handshake).
• AES is the symmetric encryption used to encrypt the data after the authentication, and the connection is established.
• 128 is the key size.
• GCM is the type of encryption (cipher-block dependency and additional options).
• SHA256 is the hash function.

All these elements define which algorithms will be used during the exchanges respecting the TLS protocol. Now, let's have a look at the certificate by clicking on View certificate. There is a lot of information, but we will focus on the public key part.

The Algorithm is RSA, the Key Size is 2048, the Exponent is 65537, and the Modulus is a big number. We have all the knowledge to understand all those parameters — remember the RSA equation \(m^e mod n\)?

Here, the message to encrypt is \(m\), the exponent is \(e\), the modulus is \(n = pq\), and the key size is the size of the modulus. It's great, we are able to understand what this information contains!

We saw all the algorithms used during TLS connection but how does it work? To establish a connection between two parties, we will start with a handshake, and if everything goes well, all the following messages will be encrypted with a symmetric shared key.

First, the client will send a first message called Client Hello to tell the server what it is capable of doing. The client will share the max TLS version it can support, a random number to protect from different kinds of attacks, and a list of supported cipher suites. At this point, the server knows what the client supports. If the server does not support any of the proposed configurations from the client, the connection will end immediately with a TLS error.

The server responds with a Server Hello that contains something similar to Client Hello and expects that it will be the chosen TLS version and cipher suites that match both server and client capabilities.

Then the server sends a certificate with a public key attached and sends a server key exchange containing the parameters for the Diffie-Hellman exchange (remember Alice and Bob’s colors), and a digital signature containing a set of previous messages hashed and encrypted using a private key of the server (server authentication, as seen in PGP).

For the next step, the server sends a Server Hello Done, which means the server sent all needed information to establish a secured connection from the client. The client replies with a Client Key Exchange, which basically contains the client public key. At this point, both server and client have a pre-master secret that is combined with the random number from the beginning and becomes a master secret that will be used to encrypt communication after the handshake.

The client now sends the Change Cipher Spec message which means that the client is ready and all following messages will be encrypted using this configuration. The client sends the Finished message that contains a summary of all the messages so far encrypted with this configuration. The server responds with the same summary, a Change Cipher Spec and a Finished message that will be encrypted.

That last exchange of the Finished message wasn’t there in the first version of TLS and appears to protect from attack during the handshake exchanges. It will work only if both the client and the server have the same resume of the events. And so, if there is an issue during this step, it’s over — the connection fails.

Perfect! We found awesome technology that could last for millions of years... Right?

The quantum menace

Did encryption win? Isn't the computing power enough to counter any algorithm? Cryptography continues to evolve to counteract technical and mathematical advances, and new algorithms, like Elliptic-curve cryptography, are pushing the previous limits.

The era of quantum computing is coming, and with it, new physical principles, and new mathematical capabilities. One must be careful not to mix several concepts. First, quantum cryptography allows the use of quantum physics laws to exchange information. Then the Post-quantum cryptography is the evolution of the current algorithms to make them resistant to quantum processors.

In both cases, these are fascinating subjects that would require dedicated articles to thoroughly explore and explain.

In a nutshell, this potential threat is also a vector of renewal and evolution for cryptography.

Destination reached, you may disembark

And just like that, we reached our final destination for this journey through time. Cryptography is a fascinating subject that I have no doubt will continue to evolve to great lengths.

I sincerely hope you enjoyed this series, learned a bit more about the history and evolution of cryptography, and that you gained a new appreciation for the art of making a message secret.

Thank you for joining me on this journey, and see you next time!