TECHNOLOGY

How does Shor's algorithm threaten public-key cryptography?

Last updated:

Shor's algorithm is a quantum computing method that can quickly break the math problems that protect most internet encryption, meaning a powerful quantum computer could decode secret messages and passwords that are currently considered secure. This threatens public-key cryptography because the mathematical puzzles it relies on would become solvable in minutes instead of thousands of years.

Continue in Reels Listen and swipe through more answers in Technology
What it breaksRSA and elliptic curve encryption, which protect most online communications
Why it worksQuantum computers can test many solutions simultaneously, while regular computers test one at a time
Current statusQuantum computers are not yet powerful enough to run Shor's algorithm on real encryption keys
Time to break encryptionA sufficiently large quantum computer could break RSA-2048 in hours instead of billions of years
ResponseScientists are developing quantum-resistant encryption methods to prepare for this threat

How Public-Key Cryptography Currently Works

Public-key cryptography protects online banking, email, and shopping by using two linked mathematical keys. One key is public and can be shared with anyone, while the other key is private and kept secret. The security depends on math problems that are easy to do one way but extremely hard to reverse. For example, multiplying two large prime numbers together is easy, but breaking the result back into those original numbers takes a regular computer thousands of years.

What Shor's Algorithm Does

Shor's algorithm is a set of steps designed to run on quantum computers, which work differently than regular computers. While a regular computer checks possible answers one at a time, a quantum computer can check many possibilities at the same time. Shor's algorithm uses this quantum advantage to quickly solve the math problems that protect encryption. It can find the prime factors of large numbers, which would break RSA encryption, or solve other hard math problems used in elliptic curve encryption.

Why This Is a Threat

The threat is significant because most of today's encrypted communications rely on these math problems being too hard to solve. If someone builds a quantum computer with enough power, they could use Shor's algorithm to decode encrypted messages sent today or stored for the future. This means secret information that is safe right now could become exposed years later once quantum computers become available. Banks, governments, and companies all depend on this encryption to protect sensitive data.

Current Reality and Timeline

Quantum computers exist today but are not yet powerful enough to run Shor's algorithm on real encryption keys used in practice. Current quantum computers have only a few hundred qubits, while breaking modern encryption would require millions of qubits. Experts estimate it could take 10 to 20 years or longer before quantum computers are powerful enough to threaten current encryption. However, some experts warn about the threat of harvest now, decrypt later, where attackers record encrypted messages today to decrypt them once quantum computers become available.

What Is Being Done to Prepare

Governments and scientists are actively working to develop new encryption methods that would be safe from quantum computers. These are called post-quantum cryptography or quantum-resistant encryption methods. The U.S. National Institute of Standards and Technology has selected several new encryption algorithms designed to resist quantum attacks. Organizations are beginning to plan how they will switch to these new encryption methods before quantum computers become a real threat.

Sources

  1. nist.gov (nist.gov)
  2. quantum.ibm.com (quantum.ibm.com)
  3. nasa.gov (nasa.gov)