I remember reading not long ago a news snippet about NSA deprecating some aspects of Elliptic Curve Cryptography due to quantum computing. Quantum computing has been futuristic for quite some time but it appears that it is starting to mature quickly. I decided to ask two of my crypto friends for the story behind this news snippet, what does “quantum resistant” really mean, and what is the impact of the advances of quantum computing on security. Both of my friends readily agreed. First up is a guest blog by Randy Breeden. I have known Randy for many years and highly respect his knowledge when it comes to many things IT but cryptosystems are his bread and butter. Read his guest blog and bio below. I believe you will find it quite “superpositioning.”
Guest blogger – Randy Breeden
April 19, 2016
When I was back in High School, my physics class was abuzz with an emerging field called Quantum Physics. The stories were all about how quantum computing was going to create computers that were faster than could be imagined, and science fiction type transportation. While there have been a large number of breakthroughs over the years, few things have emerged that impact our daily lives, that is until recently.
Over the last several years we have seen several breakthroughs that lead us closer to the science fiction dream of quantum computers and the power they promise. These breakthroughs include the development of quantum-based Random Number Chips, and short range teleportation of data through the use of entanglement. But the breakthrough with potentially the biggest impact is the recent implementation of a scalable Shor’s algorithm. Shor’s algorithm is one of the algorithms that has been developed for quantum computing to derive the factors of integers. Previous implementations of Shor’s algorithm were limited to providing factors for only smaller numbers (i.e., the number 15). This new implementation of Shor’s algorithm is scalable up to large numbers, and capable of performing the factorization of large numbers in a very small fraction of the time it takes with today’s super-computers.
A truly scalable implementation means potential danger to much of the cryptographic processing that occurs today, in particular the foundation in which PKI is built upon. Modern PKI systems use a formula that is based upon keeping large prime numbers secret. The primary means of keeping these prime numbers in obscurity is the amount of time it takes to factor large numbers. Examples provided for factoring a 2048 bit key is given at 1.5 million years. This time is primarily because the process of determining those prime numbers is done through process of elimination. In the quantum world the calculation is done through positive determination, and in parallel with a single processing cycle.
While the researchers only showed the factoring of the number 15, the method they proposed is a large leap from the prior demonstration done in 2001 by MIT that also factored 15. The MIT demonstration was limited to performing the factorization of only the number 15, one factor at a time. This new implementation allows for the factorization of larger numbers, providing a larger answer set all within one calculation cycle. Being able to quickly discover the factors of prime numbers will make many of our current security systems vulnerable. More on this in a later article.
So, are we there yet? Not quite, but we are getting closer each day. It will still be a while before we will be buying quantum computing systems for our home, but the ability to get started in quantum computing is here now. A couple months ago Microsoft released The Language-Integrated Quantum Operations (LIQUi|〉) simulator quantum tool kit on github. LIQUi|> provides yet another step forward in the quantum computing arena. The way that you write algorithms for quantum computers is very different from today’s digital computers. In many ways the simple digital calculation of 1 + 1 = 2 in the quantum world is much like the proof provided in Principia Mathematica in which the proof covers 4 pages. One of the key elements needed to advance the state of quantum computing is a set of languages that can be used to write applications, along with a different mindset. To this end, Microsoft’s Research Quantum Architecture and Computation group release LIQUi|> as a potential language and simulator. LIQUi|> comes with a number of sample algorithms to play with, including the aforementioned Shor’s algorithm for factoring integers.
In addition to the abundant research going on in the quantum computing field, there are some real products available that are based upon the quantum technology. These primarily revolve around the creation of random numbers, another concept that is critical to cryptography. One such product, IDQ’s Quantis QRNG uses a technique called Quantum Photon Randomness to generate truly random numbers that can used for key generation. This is very different from the Pseudo Random Number Generation (PRNG) technique that is used in digital computers. If you know a few key elements (seed, cycles) of the PRNG you can predict the next set of numbers that are going to be generated. In the case of the QRNG everything in the environment (heat, magnetics…) adds to the randomness of the numbers being generated. The National Institute of Standards and Technology (NIST) is working on a standard for evaluating quantum-based random number generation.
While, just like in the development of the digital computing system we have today, it will take some time to get there. We can expect the impact of quantum computing to be more prevalent in our daily lives, even though we may not be aware of its presence. As it progresses there will be both positive and negative uses. As Active Cybersecurity experts, we will need to be aware of both positive and negative uses and guard against the emerging prospects of powerful technologies, like quantum computing, on the information and systems to which we are entrusted.
Thanks Randy for sharing these insights about the advances in quantum computing and possible impacts on security. It is becoming apparent that some of the security infrastructure that we have come to rely on will be changing in the face of advances in quantum computing. I look forward to your next article as well. By the way, I think we found the resident expert on quantum computing in the Prime Minister of Canada as demonstrated in this video clip.
And thanks for checking out ActiveCyber.net! Please give us your feedback because we’d love to know some topics you’d like to hear about in the area of active cyber defenses. Also, email firstname.lastname@example.org if you’re interested in interviewing or advertising with us at ActiveCyber.
About Randy Breeden
Randall Breeden is a security research and developer. Over the last 35 years he has been involved and led both commercial and government security projects, including banking, multi-level, and crypto systems. Randall’s current projects include developing a next generation active response framework for enterprise security.
Randall can be reached at rbreeden@IATechnologyResearch.com