End of the Security as we know it?
Quantum Computers — The next gen hacker
It is undoubtedly the Quantum Computers — One of the mysterious realities in 21st century, will change the world that we already know. But will it be the destroyer of the giant wall of digital security?. Well the answer is yes and no. Let’s dive deep to find out why.
First of all quantum computers are one of the best designs of human intelligence. But underlying principles that govern this unique design are still unclear. (More details on this topic : ) Due to the remarkable and mysterious behavior of quantum elements, quantum computers will outrun any existing binary computer or any future binary computer with its processing power. The number of Qbits (Basic fundamental objects of quantum computers) in a Quantum Computer is the key parameter that decide the power of its processing. Amazing thing is, increment of these Qbits will increase the processing power of computer exponentially.
Even-though this phenomenon seems to be amazing, that is the point where the entire security of digital world becomes highly vulnerable. To understand that, lets look at how today’s digital security works. In today’s binary world, Public-Private key encryption is claimed to be the most powerful tool in web security. Most of the critical areas in web like bank account details, top secret messaging services, even bit coins use this key encryption concept to make their services secured. This key encryption is designed based on the RSA algorithm created by three genius mathematicians at MIT back in 1970s. RSA is a complex algorithm and it is been formulated by advance concepts in Number Theory. Amazing thing is, even though RSA is really complex, basic principle that lies under the hood is a elementary mathematics— The Prime Factorization.
If you are given a number like 15 and asked to represent it as a multiple of two prime factors, it will just take couple of seconds to tell the answer as 5 and 3. This entire procedure is known as prime factorization. But if you think carefully about that, you will understand that you didn’t follow any algorithm to get that answer. It just came to your mind. This is the place where all the interesting things begin to happen. No algorithm has been found to solve this problem in a limited time. The simplest thing we can do is start from the first prime number (2) and check whether the given number is divisible or not. Since there is no simple way to check whether a given number is a prime or not the task becomes much more complex. Now imagine the given number has 10 or 15 digits, the task becomes a complete nightmare. Actually when the number of digits in the given number becomes really big, this process becomes a nightmare to the digital processors as well. Just as an example if we consider a computer with a 10⁸⁰ CPUs and each of those CPUs could enumerate one modulus per millisecond, to complete a prime factorization of 309 digits number approximately it would take 5.95×10²¹¹ years in the basic method that was discussed. Actually the number of CPUs in this example is nearly equal to the number of atoms in the observable universe. And this operation takes 5.95×10²¹¹ years and the age of our universe is 13.75×10⁹ years!!!
(It is important, in this example it was assumed that, basic brute force method is used. This is just a theoretical demonstration of the power of this little concept. In today’s world there are faster algorithms than this, but the truth which is still unbroken is, those algorithms also provide unrealistic statistics which are more or less similar to this. As a matter of fact, there are no trusted information about a successful attempt of factorizing a number with 309 digits. The largest number that is recorded is 232 digits and a computer cluster empowered by advanced mathematical algorithms with 2.2 x 2000 GHz computation power took nearly two years break that. )
This complexity is the backbone of RSA algorithm. And this complexity is the reason that primary key encryption is still unbreakable. (Even though we used 309 digits number for the example, in real world applications very large numbers (617) are used. With number of digits increased, factorization time is also increases exponentially. ) One day if a genius comes up with a really simple algorithm to perform this prime factorization with in an acceptable time, that will be the end of this security schema. And with the power of quantum computers we are about to enter that era. We are about to experience a world, that the security mechanisms we trusted as the best, are no longer functional. The end of the security at least as we know it !!!
According to data from D-Wave (a quantum computing company in Canada) their DW-2 quantum computer is 3600 faster than any known existing super computers in the world. Normally the best supercomputers are capable of processing at 93.42 x 10¹⁵ floating point operations per second. Rest is mathematics. It is crystal clear that the dooms day of the powerful guardian, the unbreakable algorithm RSA- 2048 (617 digits RSA key ), is not far away. It is important to remember that DW-2 contains only 439 Qbits, and this number will be increased in near future. So this is the story of farewell of a great invention. But do we really need to worry about that?
According to Nadia Heninger, an assistant professor of computer and information science at the University of Pennsylvania, “No we don’t”. According to researches they have conducted, attacking a terabyte-size key using Shor’s algorithm would require around 2¹⁰⁰ operations on a quantum computer (an enormous number comparable to the total number of bacterial cells on Earth). This Shor’s algorithm is considered as one of the miracles in the world of mathematics. In 1994 at MIT this algorithm was formulated by an American professor and mathematician Peter Shor, as a quantum algorithm (an algorithm that runs on a quantum computer) for integer factorization. Informally it solves the following problem: given an integer N, find its prime factors. According to Nadia, even with that miraculous algorithm still quantum computers are defeated by this simple Prime Factorization.
Are we safe ? This is the point that we don’t have an answer. According Nadia’s statistics key is a terabyte sized key. Keys which are used in today including RSA — 2048 are few thousand bits. A terabyte is 1 x 10¹² x 8 bits. Using such a giant key is simply unrealistic. Next important thing is the accuracy of these assumptions. Because history teaches us the assumptions in binary world don’t last long. It was never expected that SHA-1 encryption would be broken this much earlier. But it happened, with their unimaginable server power, Google broke it. And due to the mind blowing research findings of D-Wave one of the golden-rule in computer science —“Moore Law” is about to break. These incidents continuously tell us assumptions in bit world are meant to be broken.
Once the Decoherence phenomenon in quantum nature is properly solved, the era of hand-held quantum computers will not be far beyond. So the million dollar question is, when that day comes will RSA be able to protect us?
