Security Sidebar: Did Quantum Computing Kill Encryption?

Google recently published results of its newest quantum computing capability with a chip called "Sycamore" and the results are pretty impressive. Classic computer operations rely on a binary 1 or 0 to execute operations. But, quantum computing can take advantage of numbers between 1 and 0 at the same time, thus greatly increasing its computing speed and power. Of course, this quantum computing thing is not easy. Giant companies like Google, IBM, and others have been working hard with large budgets for a long time to figure this thing out.
 

Google's Sycamore Chip

In its public release, Google showed that the Sycamore chip could execute calculations that are not possible with classical computers. The specific calculations that the Sycamore chip performed were related to complex random number generation. The Sycamore chip performed the calculations in about 200 seconds. In order to show the significance of how fast this was, the team also ran a simpler version of this same test on the world's fastest supercomputer (not quantum computer) at the Oak Ridge National Laboratory. After the supercomputer completed this simpler task, the team was able to extrapolate the amount of time the supercomputer would have taken to complete the more complex task that Sycamore completed. The team suggested it would have taken the supercomputer about 10,000 years to complete the same task that Sycamore completed in 200 seconds!

 

Google's Quantum Computer


To be fair, the task of verifying complex random number generation doesn't necessarily have wide application in today's world. But, that was never really the point of this experiment. The point was to show the potential that quantum computing can have in our world as the technology matures. Some experts have compared this breakthrough to Sputnik in space or the Wright Brothers first airplane flight...while these events arguably didn't have super-impressive results, they certainly paved the way for what would be very significant technology in the future. So, we will see where quantum computing takes us as an industry, but it's certainly proving to show that computing power is getting stronger and faster.
 

Encryption

So, how would this affect encryption? Encryption is fundamental to Internet privacy and security. At its core, encryption requires a secret key that the sender and receiver both have in order to encrypt and decrypt the information they send back and forth. Most encryption algorithms used today are widely known, and the developers show exactly how they work and how they were designed. While the security of the encryption is certainly based on its design and mathematical strength, it is also based on the fact that both the sender and receiver have a key that is kept secret. If an attacker steals the key, then game over.

The strength of the key is based on the mathematical likelihood that someone (or something) could (or could not) figure it out. If you have followed computer encryption for any length of time, you've no doubt noticed that certain encryption key strengths are no longer recommended. This doesn't automatically mean that the encryption algorithm is not good, it just means the key size needs to be larger so that a computer will take longer figuring out the key. As computer processing power has grown over the years, the need for larger key sizes has also grown.





For example, the RSA encryption algorithm (used for server authentication and key exchange) has been tested over the years to see how long it would take a computer to crack the secret key. As you may know, RSA is built on the foundation of prime number factoring where two large prime numbers are multiplied together to get a common value that is shared between the client and server. If a computer could take this large number and figure out the two prime numbers that were multiplied together, then it would know the secret key value. So, the whole foundation of security for RSA encryption is based on the idea that it is very difficult to figure out those two numbers that were multiplied together to get that big shared value. The idea with key size in RSA encryption is that the larger the two prime numbers are, the harder it is to figure them out.

Many people have tested RSA over the years, and one group of researchers discussed some results from one of their tests. Several years ago, this team tested a 155-digit number and worked to factor it down. It took them nine years to figure out the factors (and thus the secret key). More recently, they tested a 200-digit number with more modern computing power and it took them about 18 months to crack it. A while later (with still faster computers), they tried a 307-digit number and they factored it down even faster. The point is, as modern computing power gets faster, the time it takes to crack an encryption key gets shorter. A typical RSA implementation today uses 1024-bit key size. Some applications will use 2048-bit key sizes, but the larger the key size, the more load it puts on the client and server, and it slows the web application down. So, there's a tension between strong (large) key size and application speed.

Now that Google has shown the ability to use quantum computing to run calculations in 200 seconds that would take today's fastest supercomputers 10,000 years, it's not hard to imagine that an encryption key like the one used in RSA can be cracked in a matter of seconds. If you know a mathematician who designs computer encryption algorithms, tell them that the Internet might be looking for some new stuff pretty soon...