The Future of Encryption: How Quantum Computing May Impact Current Encryption Algorithms

Examining the current Encryption Algorithms and the potential consequences of advances in quantum computing on the security of RSA and AES encryption algorithms

Photo by Yuya Uzu on Unsplash

It may not come as a surprise to a regular internet user that generally all internet traffic can be intercepted. What may come as a surprise is that it is extremely easy to intercept internet traffic. For a number of years now, encryption has played a crucial role in securing data. These encryption algorithms rely on mathematically ‘hard’ problems which are computationally expensive to solve and in most cases not feasible for regular and even super computers to solve.

However, advances in quantum computing has the potential to significantly impact the security of current encryption algorithms. This is because quantum computers have the potential to solve these mathematical problems much faster than classical computers, which can be used to break encryption algorithms.

It is important to note that while quantum computing presents a potential threat to current encryption algorithms, it is still in its early stages of development and it is not yet clear when or if quantum computers will become powerful enough to effectively break these encryption algorithms. In the meantime, cryptographic experts are actively researching and developing new encryption algorithms and protocols that are designed to be secure against quantum computers.

Before, we delve into how the current encryption works and the challenges posed by quantum computers, let us look at how web traffic is currently secured.

How is web traffic secured?

When you establish a secure connection with a website, you would be navigating the website over HTTPS and you would be able to see a padlock icon in your browser. If you are accessing a website over HTTP, the website is likely not secure and information exchange is in cleartext which can be read by anyone intercepting traffic in the middle.

Web traffic is encrypted and secured using a protocol called TLS (Transport Layer Security). Its predecessor was called SSL (Secure Socket Layer). Although SSL was deprecated, both TLS and SSL are interchangeably used to refer to TLS.

How does TLS work?

There are 2 commonly used versions of TLS (TLS 1.2 and TLS 1.3). Although, there might still be websites using older versions of TLS and you should avoid providing any sensitive data to those websites. Generally, the following are essential for a TLS to work:

• The user/client and the website/server establish a TLS handshake, whereby a public key is exchanged and a secure connection is opened
• Both the parties then generate session keys using the information exchanged in the TLS handshake and these session keys are then used to encrypt and decrypt all traffic
• TLS also ensures that the website/server is actually who it claims to be
• TLS also ensures that the data exchanged is not altered, using a MAC (Message Authentication Code) that is included with data transmission

What is a TLS handshake?

The first step in securing the communication is to establish a TLS handshake. Both TLS 1.2 and TLS 1.3 follow a similar process with 2 key differences — 1) TLS 1.3 enables a faster handshake and 2) TLS 1.3 does not support parameters and cipher suites that are vulnerable to attack. The steps within a TLS handshake will vary depending on the key exchange algorithm and cipher suites used, however refer to the image below to see the typical steps in TLS 1.2 and TLS 1.3.

TLS 1.2 steps using RSA

The following are the steps under an RSA key exchange algorithm:

1. Client “Hello” message: The user/client initiates the handshake and sends a “Hello” message to the server. Either in the “Hello” message or separately, the client will also share TLS versions and cipher suites supported and a string of random bytes (client random).
2. Server “Hello” message: The server replies back with a “Hello” message and also shares the SSL certificate, the chosen cipher suite and a string of random bytes (server random).
3. Authentication, premaster secret: The client verifies the authenticity of the SSL certificate and shares a random string of bytes encrypted using the public key from the SSL certificate (premaster secret).
4. Decrypting premaster secret: The server decrypts the premaster secret using the private key.
5. Session keys generated: Both the client and the server generate session keys using the client random, server random and premaster secret.
6. Client “Finished” message: The client sends a “Finished” message encrypted with the session key.
7. Server “Finished” message: The server sends a “Finished” message encrypted with the session key.

Following these steps the handshake is complete and a secure symmetric encryption is achieved. We will discuss later on what is the difference between asymmetric encryption and symmetric encryption.

TLS 1.2 steps using Diffie-Hellman (DH)

As TLS handshakes using only RSA are now considered less secure, an alternative TLS handshake using DH is utilized. The steps under a DH handshake are similar with the following exceptions:

After initiating the handshake and sharing the SSL certificate, the server computes a digital signature of all the communication up to this point and the client verifies the digital signature. The server also shares a DH parameter. Following which, the client shares its DH parameter with the server. Instead of the client sharing a premaster secret, both the client and the server utilize the DH parameters to generate a matching premaster secret.

After the premaster secret is generated separately, both the client and the server utilize the premaster secret, client random and server random to generate the session keys.

The ephemeral DH handshake allows key establishment to happen independently of the server’s private key and thereby achieves forward secrecy, i.e. even if the server’s private key is compromised later, the communication cannot be decrypted using that, whereas under RSA, if the private key is compromised all the intercepted communication can be decrypted.

TLS 1.3 steps

TLS 1.3 has removed support for cipher suites vulnerable to attack and it also does not support RSA. Furthermore, the handshake has been shortened and therefore it takes less time to complete the handshake. Following are the steps typically undertaken under a TLS 1.3 handshake:

1. Client “Hello” message and share paramaters: The client sends a “Hello” message and with it the client makes an assumption of the server’s preferred key exchange method and also share the client random and parameter to generate the encryption keys.
2. Server “Hello” and “Finished message: The server uses the client random, client’s parameter and server random and generates the premaster key. The server sends the SSL certificate, chosen cipher suite, digital signature, server random with the “Finished” message.
3. Client “Finished” message: Client verifies server’s authenticity, generates the encryption keys and sends a “Finished” message.

As you can see that under TLS 1.3, a secure symmetric encryption is achieved in much less steps than TLS 1.2.

What is the difference between asymmetric and symmetric encryption?

As all traffic over internet can be easily intercepted, the idea of encryption is to mask the data so that any party not authorized to receive the message cannot decipher it. The computers do that by scrambling the information using an encryption key. If the same key is used to decrypt the information and the process is called symmetric encryption and if different keys are used for encryption and decryption then the process is called asymmetric encryption.

As the asymmetric encryption methodology uses 2 separate keys, it is computationally more expensive and much slower. Therefore, it is normally used to encrypt small amounts of data, while symmetric encryption is used to encrypt and decrypt large amounts of data.

The TLS handshakes describe above use asymmetric encryption in the process of generating keys. However, once a handshake is established all communication is done using a symmetric encryption using the session keys generated.

Two commonly used algorithms are RSA for asymmetric encryption and AES for symmetric encryption.

So what are the challenges posed by quantum computing?

Now that we understand how computers exchange communicate and exchange information, let us delve a bit deeper into how the RSA, AES and DH key exchange method work and what challenges are posed by advances in quantum computing.

How does the RSA algorithm work?

The RSA encryption algorithm relies on the mathematical property of large prime numbers. It relies on the premise that the algorithm is easy to compute in one direction but computationally very expensive to reverse (trap door function). For e.g. lets take 2 prime numbers 823 and 977. It is easy to compute 823 * 977 = 804,071 but it would be computationally expensive if you have 804,071 and you have to find 2 prime numbers that when multiplied provide that answer. This is a simple example and you would probably be able to solve it relatively quickly using a computer program, however, RSA using RSA-2048 bit implementation you would use two 1,024-bit prime numbers.

We will use a simple example and small prime numbers to show how an RSA algorithm works, using the following assumptions:

Two prime numbers: p = 17, q = 19

Public exponent: e = 65537 (it does not matter what this number is — it is usually a large odd number)

Private key: To generate the private key, we need to calculate the modular inverse of the public exponent with respect to the Euler Totient Function (ETF) of the modulus. Public exponent can be calculated using either Euler totient function or Carmichael totient function. For ease of calculation we will use ETF, however Carmichael totient function is simply the least common multiple (lcm).

Client = Alice, Server = Bob, Third-party/Eavesdropper = Eve.

Suppose Alice wants to send the letter “a” to Bob in a secure manner. To do this, Alice first generates two prime numbers, p and q. In this case, let’s assume p = 17 and q = 19. Alice then calculates modulus (n) = pq, which in this case is n = 17 * 19 = 323.

Next, Alice chooses a public exponent, e. In this case, let’s assume e = 65537. Alice then calculates the ETF of the modulus, i.e. (p-1)(q-1), which in this case is (17–1)(19–1) = 16 * 18 = 288. To ensure that the RSA encryption is secure, e must be coprime to (p-1)(q-1).

Alice then encrypts the letter “a” using the RSA algorithm. The encryption process is done by raising the letter “a” to the power of e modulo n, resulting in the encrypted message c = a^e (mod n). In this case, let’s assume that the letter “a” is represented by the number 97 in ASCII. So, c = 97⁶⁵⁵³⁷ (mod 323) = 193.

Bob receives the encrypted message c and decrypts it using his private key, which is a secret number d such that d is the modular inverse of e modulo (p-1)(q-1). Bob calculates d such that d * e = 1 (mod 288). d can be calculated using the Extended Euclidean Algorithm (ax + by = gcd(a,b), where gcd = greatest common divisor). Solving for the equation provides Bob with a value of d = 2753. An alternative calculation may also yield you the value of 161 but we are using 2753 for our example.

Bob then calculates c^d (mod n), which gives him the original letter “a”. In this case, 193²⁷⁵³ (mod 323) = 97, which represents the letter “a” in ASCII.

You can test the calculation using the calculator here.

How does the Diffie-Hellman (DH) key exchange work?

A downside of the RSA handshake is that if the private key is compromised then a third-party (Eve) can decrypt the entire communication. The ephemeral DH handshake resolves that problem by allowing Alice and Bob to securely agree on a shared secret key without the need for prior knowledge of each other’s private key.

The security of the DH algorithm is based on the difficulty of computing the discrete logarithm of a large prime number. Let us illustrate using a very simple example.

In the Diffie-Hellman key exchange, two parties, Alice and Bob, agree on two values: a prime number p and a primitive root g. These values are public and can be easily shared between Alice and Bob. Alice then chooses a secret number a and Bob chooses a secret number b. Alice then calculates A = g^a (mod p) and sends it to Bob. Bob calculates B = g^b (mod p) and sends it to Alice.

Both Alice and Bob can now use the values they received from each other to calculate the shared secret key K. Alice calculates K = B^a (mod p) and Bob calculates K = A^b (mod p). The shared secret key K is the same for both Alice and Bob and can be used to encrypt and decrypt messages between them.

Here is an example of the Diffie-Hellman key exchange with p = 17 and g = 5:

• p = 17
• g = 5
• Alice chooses a secret number a = 7
• Bob chooses a secret number b = 11
• Alice calculates A = g^a (mod p) = 5⁷ (mod 17) = 9
• Bob calculates B = g^b (mod p) = 5¹¹ (mod 17) = 8
• Alice calculates K = B^a (mod p) = 8⁷ (mod 17) = 13
• Bob calculates K = A^b (mod p) = 9¹¹ (mod 17) = 13

So the shared secret key K is 13.

After the key is exchange either using DH or RSA handshake, typically the subsequent traffic is then encrypted and decrypted using a symmetric encryption algorithm, such as AES.

How does the AES algorithm work?

Suppose Alice wants to send the letter “a” to Bob in a secure manner. To do this, Alice first generates a secret key, which is a string of binary digits. In this case, let’s assume the secret key is the binary number 10011001. The key is used to encrypt and decrypt the letter “a”.

Next, Alice encrypts the letter “a” using the AES algorithm. The AES algorithm works by dividing the letter “a” into blocks of data and then applying a series of mathematical operations to each block using the secret key. The operations performed by AES are designed to be fast and secure, making it difficult for an attacker to recover the original message without having access to the secret key.

For the purpose of this illustration, let’s assume that the encrypted message is the binary number 01100110.

Bob receives the encrypted message and decrypts it using the same secret key that was used to encrypt the letter “a”. The decryption process is done by applying the reverse of the operations performed by AES to the encrypted message.

In this case, the decrypted message is the binary number 01100001, which represents the letter “a”.

The AES algorithm is deemed secure as typically back-solving the encryption key in AES is equivalent to brute-forcing the key, which involves trying all possible keys until the correct one is found. Assuming a key length of 128 bits would imply 2¹²⁸ possible keys. Solving that would be computationally very expensive for classical computers.

What challenges are posed by quantum computing?

Challenges to RSA

As we discussed above that the security of the RSA algorithm depends on the assumption that factoring large integers into its prime factors is a computationally difficult problem. In 1994 Peter Shor proposed a polynomial-time quantum algorithm.

Shor’s algorithm can find the prime factors of n in polynomial time, which means that a quantum computer could use Shor’s algorithm to find p and q in a much shorter amount of time than is currently possible with classical computers. Once p and q are known, it’s possible to calculate φ(n)(ETF) and d, and therefore to break the RSA encryption.

We will not go into details of how the Shor’s algorithm works. For the purpose of this article, we will leave with an understanding that Shor’s algorithm uses quantum computing to perform fast modular exponentiation and find the prime factors of a composite number much faster than classical computers. This makes it a powerful tool for breaking RSA algorithm.

Challenges to AES

As discussed above that cracking the AES algorithm requires brute-forcing the encryption key which is computationally very expensive for classical computers.

Grover’s algorithm is a quantum algorithm that can be used to crack AES encryption. To crack the encryption using Grover’s algorithm, the quantum computer would utilize the ‘amplitude amplification trick’. This operation allows the quantum computer to search through a large set of possible keys in a single operation, making the process much faster than traditional brute force methods. Following from our previous example, a quantum computer will be able to search through all possible 128-bit keys in just O(2⁶⁴) operations, which is significantly faster than the O(2¹²⁸) operations required by classical computers.

Conclusion

While advances in quantum computing pose challenges to the current mainstream encryption methodologies, it’s worth mentioning that the actual capabilities of quantum computers are still very limited and there is not an immediate threat. However, the impact could be very disruptive when and if practical quantum computing solutions are available. The good news is that a number of researchers are working on developing ‘quantum-safe’ cryptography capabilities and hopefully encryption standards will be migrated to a quantum-safe solution before the digital economy is disrupted.