Finding the private key for a RSA protocol can take years on the fastest supercomputers. ImageȘ Pixabay

Quantum computers might soon render RSA encryption obsolete

Many protocols like SSH, OpenPGP, S/MIME, and SSL/TLS rely on RSA encryption where access to data is secured with two keys. The encryption key is public and differs from the decryption key which is kept secret. The cryptosystem’s reliability exploits the fact that factoring large primes takes years to do even for today’s fastest supercomputers, so protocols based on RSA have proven paramount to anything from processing payments to storing classified intelligence. RSA, however, might become obsolete soon as quantum computer system become stabler and more efficient. Using only five atoms, a team of international researchers showed how to factor a prime, albeit a trivial one for demo purposes. The researchers say there aren’t any physical restrictions that might hinder scalability. Theoretically, more atoms could be added in the process and large primes could be solved at lightning speed. That doesn’t make the engineering challenges easy, though.

Finding the private key for a RSA protocol can take years on the fastest supercomputers. ImageȘ Pixabay

Finding the private key for a RSA protocol can take years on the fastest supercomputers. ImageȘ Pixabay

RSA was first described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology. In this asymmetric cryptography,  two different but mathematically linked keys, one public and one private, are used to decrypt a message. The public key, which anyone can see and use to encrypt a message, is based on the product of two large primes, and an auxiliary exponential. Multiplying two large primes to an integer is easy, but determining the original primes that make the product with no other info is very difficult.

In 1994, Peter Shor, the Morss Professor of Applied Mathematics at MIT, came up with a quantum algorithm that calculates the prime factors of a large number, vastly more efficiently than a classical computer. To actually run the algorithm though a quantum computer would require many qubits or quantum bits.

In conventional computers, operations that transform inputs into outputs work with bits which can be 0s or 1s. Qubits  are atomic-scale units that can be 0 and 1 at the same time — a state known as a superposition. What this means is that a quantum computer can essentially carry out two calculations in parallel. A system that works with qubits can be not twice but millions of times faster than a conventional computer.

Previously, scientists designed quantum computers that could factor the number 15 (primes 3 and 5), but these couldn’t be scaled to factor larger numbers. “The difficulty is to implement [the algorithm] in a system that’s sufficiently isolated that it can stay quantum mechanical for long enough that you can actually have a chance to do the whole algorithm,”  Isaac Chuang, professor of physics and professor of electrical engineering and computer science at MIT.

Chuang and colleagues at MIT and the University of Innsbruck in Austria claim they not only found a way to make a quantum system scalable, but also more efficient. Typically, it took 12 qubits to factor the number 15. The researchers factored the same number using only five qubits or atoms. These five atoms are held in an ion trap, which removes an electron from each atom thereby charging it. The system is stabilized by holding the atoms in place with a magnetic field.

Logic gates operations are performed using laser pulses on four of the atoms, while the fifth is used to store or extract results. Using the fifth atom to store information was the brilliant part. “Measuring a qubit knocks it out of superposition and thereby destroys the information it holds. Restricting the measurement step to the fifth ion kept the four involved in the computation from being corrupted,” wrote Amy Nordrum in an article  for IEEE.

The number 15, albeit trivial to solve, is the smallest that can meaningfully demonstrate Shor’s algorithm. A working system developed at University of Innsbruck factored the number with  a confidence exceeding 99 percent, as reported in the journal Science.

 “In future generations, we foresee it being straightforwardly scalable, once the apparatus can trap more atoms and more laser beams can control the pulses,” Chuang says. “We see no physical reason why that is not going to be in the cards.”

To decrypt a typical  1024-bit key, the same system would need thousands of qubits or simultaneous laser pulses. This is doable, but highly challenging and it might take a long time before you can use a quantum computer to break RSA.

Moreover, many researchers are already aware of the limitations of current cryptosystem and are preparing for the future: “quantum-resistant public-key algorithms”.

“Continued advances in quantum computing will draw broad attention to the threat it represents to all of today’s widely used public-key cryptosystems – the cryptography that underlies electronic commerce and secure communications on the Internet. The security community will begin planning the migration to new `quantum-resistant’ public-key cryptosystems for which quantum computers provide no computational advantage,” said Brian LaMacchia,  Director, Security & Cryptography, Microsoft Research.

11 thoughts on “Quantum computers might soon render RSA encryption obsolete

  1. IJK

    Define “soon”. In geological terms, it might be soon. In human terms… This sounds like little more than hype and hoopla.

  2. Jake

    It’s definitely not hype. There’s so much we don’t know about the quantum world, but what we do know tells us that the quantum world is amazing.

  3. Pingback: MIT’s Riffle Aims to Compete with Tor for Spot as Anonymity King - Protect Your Bitcoins

  4. Pingback: Altcoin News - AltcoinsNews MIT’s Riffle Aims to Compete with Tor for Spot as Anonymity King -

  5. Pingback: MIT’s Riffle Aims to Compete with Tor for Spot as Anonymity King | Bitcoin News for Buy, Sell and Mining Bitcoins

  6. Pingback: MIT’s Riffle Aims to Compete with Tor for Spot as Anonymity King – Silicon Islands

  7. Pingback: MIT’s Riffle Aims to Compete with Tor for Spot as Anonymity King | Welcome to ValidCoin.Net

  8. Pingback: MIT’s Riffle Aims to Compete with Tor for Spot as Anonymity King | New Internet Media

  9. Pingback: MIT’s Riffle Aims to Compete with Tor for Spot as Anonymity King - Business 4 portal , B2B B2C

  10. Pingback: MIT’s Riffle Aims to Compete with Tor for Spot as Anonymity King | Bani-Digitali.ro

  11. Pingback: You can now tinker around with IBM’s quantum computers – straight from your couch | Mihai Andrei – ZME Science | The Center of the Decentralized

Leave a Reply

Your email address will not be published. Required fields are marked *