The Deal with Quantum Computing and Cryptography

Written by

Cryptography provides the foundation for encryption, privacy and secure communication, and as such it has evolved heavily in the past and it will continue to deal with new threats in the future. You are never "done". It is a continuous process.
 
Looking back at some of the early days of modern cryptography: in the early 1970s, IBM developed an encryption algorithm called DES, which could encrypt any data with a 64bit key. The NSA successfully intervened and reduced the key-size to 56 bits, and in 1976 NIST officially approved it as a standard. 
 
20 years later, the DESCHALL project publicly broke a message encrypted with DES-56 for the first time in 1997. The next year a tool was released to break any DES-56 encryption in 56 hours, and in 1999 NIST permitted DES-56 only in legacy systems anymore.
 
This was a problem as all applications that used DES-56 needed to be changed. Web browsers, backend applications, backups, data storage, your financial record, but also less obvious things such as TV satellite systems - HBO used DES-56 in their TV satellite scrambling system called Videocipher-II.
 
The reason that it was possible to break the accepted protocol is because DES-56, and every encryption algorithm that is widely used today, is only "computational secure". They are all based on mathematical calculations that are very easy to do in one direction, but very hard to do in the opposite direction (You can easily calculate 165181*417953, but to get from 69037894493 to the original numbers turns out to be really hard). 
 
For the RSA algorithm with 2048 bits, the numbers used are incomprehensibly big (a number with 617 digits). In order to break just one key, a computer with one trillion operations per second would need around 317 trillion years. So even though RSA and ECC (Elliptic-Curve-Cryptography) are used for 99% of public key encryption and these are only computationally secure, we can still feel confident that public key encryption is secure, right? Well, not if someone really smart thinks of new ways to break them. This happened to DES, this happened to Wifi Security Standards WEP and WPA2 and to other encryption schemes.
 
It happened to RSA (and ECC) when Peter Shor came up with an awesome algorithm which can break every RSA and ECC encryption, 25 years ago (in 1994). When I say "break", what I really mean is that I can calculate the private key just with the knowledge of the public key. This should be impossible, as it will immediately allow me to decrypt everything that was protected with the (unknown) private key. RSA and ECC are the most widely used public key encryption schemes and they are used everywhere ranging from most blockchains, file encryption to all of our web traffic.

The only trouble with Shor’s algorithm is that it needs a quantum computer to do it, and in 1994, quantum computing was very much a theoretical research area. However quantum computing continues to heat up as one of the major battlefields for security. Fortunately for us, today's public quantum computers are still quite small, with fewer than 100 qubits, and very noisy.

What has changed since Shor’s proof in 1994 is that everybody now agrees that we will have a universal quantum computer at some stage. Quantum computers and Qubits are really strange and abstract objects, and research is focused on finding good algorithms that work much faster on Quantum Computers vs Classical Computers - just like Peter Shor did in 1994.

In order to break RSA, one needs to "factor" a really large number and the best algorithm on a classical computer is of exponential complexity (meaning if N is the number of bits of the key, it needs to execute e.g. 5N times). Peter Shor’s algorithm is only of polynomial complexity (meaning the N is not in the exponent, but in the base, e.g. N5).

For large numbers, the difference is so big, it’s hard to comprehend. As an illustration, let’s imagine we have a quantum computer with 4099 qubits that are completely stable and error-free, and this quantum computer can execute a modest one million operations per second. With this quantum computer, instead of it taking 317 trillion years to break RSA 2048 as on a classical computer, this could be executed in 10 seconds.

This is why the world is racing toward developing quantum computing, while other researchers are looking for replacements for RSA and ECC as well as for ways to harness that quantum power to deliver other security tools. I want to be clear though that such a computer doesn't exist yet, and will not exist for quite some time.
 
The ability to change and adapt our cryptographic solutions is called crypto-agility. As enterprises we need to have the ability and the agility to upgrade security protocols, methods and algorithms much quicker and easier that we have done in the past. I don't even want to check how many IoT devices still have DES-56 encryption enabled - over 20 years after it was compromised.

What’s hot on Infosecurity Magazine?