The Internet as we know it is on borrowed time. Quantum computers will break 90% of the encryption we use today. Financial transactions, medical records, and other sensitive information are in jeopardy. Our personal data will no longer be safe.
Okay, scary talk aside, this is a really big deal. The National Security Agency (NSA) has already warned that quantum computing poses a “severe threat” to national security. If we don’t overhaul our internet with post-quantum cryptography, it will eventually collapse.
The Internet as we know it could be gone in 10 years.
This is not a drill. This is not a drill. Here’s the reality: Today’s most prevalent encryption protocol (RSA) could become utterly obsolete within 10 years.
What is RSA encryption and why is it so widespread?
In 1977, Rivest, Shamir, and Adleman developed the RSA encryption algorithm. Today, RSA is used by over 90% of internet connections as part of the SSL handshake.
When you visit a website that uses HTTPS, your browser and the website’s server use RSA to exchange keys. These keys are then used to encrypt all further messages. Your messages will basically be a jumbled mess during transit. Only your intended recipient can decrypt them.
RSA is also used for digital signatures. Digital signatures prove a message or document is real and hasn’t been tampered with. RSA is widely used for digital signatures, email clients, software distribution platforms, and many other applications we take for granted.
RSA is popular because it’s difficult to brute force with current supercomputers. It’s also quite efficient in speed and memory usage. This makes it a good choice for applications where performance is important, such as online banking or e-commerce.
Two other factors in RSA’s favor are its ease of use and versatility. Open-source libraries make it easy to use RSA in any programming language. And it can be used to encrypt a wide variety of data, including text, images, and files.
Which Internet services use RSA today?
RSA is the most widespread encryption algorithm on the Internet. It’s used all over the place, including:
- Web browsers: When you connect to a website through HTTPS, your browser will use RSA encryption to establish a secure connection. This protects your data during transit, so that it cannot be intercepted by third parties.
- Email: Many email services, including Gmail and Outlook, use RSA encryption to secure email messages. This prevents your emails from being read by unauthorized users.
- VPNs: Virtual private networks (VPNs) use RSA encryption to create a secure tunnel between your computer and a remote server. This allows you to connect to the Internet securely, even when you are using a public Wi-Fi network.
- File sharing: Some file sharing services, such as Dropbox and Google Drive, use RSA encryption to protect your files.
- Digital signatures: RSA encryption can be used to create digital signatures, which prove a document is real and verify the sender.
All of these will be at risk in a post-quantum cryptography world.
How does RSA work and why is it in danger?
Imagine you have a mailbox on the street. Anyone can drop a letter inside, but only you have the key to open it and read the letters.
The mailbox is like RSA encryption. When someone wants to send you a secret message, they “lock” it using your mailbox (public key encryption). Once it’s locked, only you, with your unique key (private key), can open it and read the message inside. This is called an asymmetric key system.
So, why is this system in danger? Well, it has to do with how those encryption keys are created. In overly simplified terms, RSA works by multiplying two large prime numbers to generate the public key. That public key (mailbox) can be shared with others, but the original numbers are kept secret by the user.
But what if someone really were able to factor the public key (find the original numbers that were multiplied together)? They’d crack the encryption. They’d be able to get into the mailbox and steal all the mail.
In other words, RSA is based on the assumption that factoring large numbers is a very hard mathematical problem. Some RSA algorithms use numbers that are over 400 digits long. Factoring that type of key size using brute force is futile. Even a supercomputer would need millions of years.
But quantum computers don’t play by classical rules. A quantum computer would break that 400-digit encryption in just a few days or hours. That’s because they can run a special algorithm called Shor’s Algorithm. This algorithm is specifically designed to factor large numbers, but it won’t work on classical computers.
That’s why we’ll need new, dedicated encryption schemes for post-quantum cryptography. We’ll need schemes that don’t rely on assumptions of mathematical difficulty.
Quantum computers don’t play by classical rules.
In classical computers, a bit can only be in one state at a time, either a 0 or a 1. So if you had two bits, they could be in one of four possible states:
| Bit State | Decimal Equivalent |
| 00 | 0 |
| 01 | 1 |
| 10 | 2 |
| 11 | 3 |
And if you had three bits, they could be in one of eight possible states:
| Bit State | Decimal Equivalent |
| 000 | 0 |
| 001 | 1 |
| 010 | 2 |
| 100 | 3 |
| 011 | 4 |
| 101 | 5 |
| 110 | 6 |
| 111 | 7 |
Let’s say each of these states represents a number from zero to seven. Now, let’s say you want to perform a calculation, e.g. raising three to the power of one of these numbers.
To do so, you’d need to perform each calculation separately, one state at a time. For example, you could calculate 3^2 = 9. Then, you could calculate 3^3 = 27. Etc.
Qubits bring an exponential increase in computation capacity.
Qubits (quantum bits), on the other hand, can exist in all possible states at once. This is known as “superposition,” and it’s the reason old methods won’t work in post-quantum cryptography.
If we repeat the above calculation using qubits, we can actually perform it for all those numbers at once. We’d end up with a superposition of different answers:
1, 3, 9, 27, …
Each additional qubit doubles the number of possible states (2^x states where x is the number of qubits). So if we added a fourth qubit, we’d have 16 possible states. A fifth qubit allows 32 states. Etc.
The number of possible states grows exponentially as qubits are added. This is why quantum computing is so potent. Just 30 qubits are enough to represent over a billion states (2^30 = 1,073,741,824). In essence, you’d be able to compute a billion different options at once.
So what’s the catch?
This sounds incredibly powerful and it is, but there is one very big catch. All the answers to the computation are embedded in a superposition of states… but you can’t simply read out this superposition.
Measuring a quantum system makes it collapse into a single state. All other information is lost. This makes quantum computers very tricky to use in practice. You’d need to end up with one state that contains only the information you want. As a result, quantum computers won’t work for most everyday applications.
How many qubits are needed to break RSA?
It’s still a debate how many qubits are needed to break RSA. The most widely cited estimate is 10,000 qubits to break a 2048-bit RSA key. However, this is an old estimate based on Shor’s algorithm for factoring integers.
The actual number could be much lower. For example, a 2022 paper proposed a new quantum algorithm that needs only 372 qubits for a 2048-bit key. The lower this number becomes, the more urgently we’ll need reliable post-quantum cryptography.
This number also depends on the qubits’ error rate and the computer’s error correction ability. To understand what error rate is, imagine you’re playing a game of “telephone.”
You whisper a message to the person next to you, and they pass it on until it reaches the last person in line. If every person is a qubit, then the error rate is like how often each person mishears the message and passes on the wrong thing.
A high error rate means the message gets jumbled up quickly, while a low error rate means it stays pretty close to the original. Qubits today still have pretty high error rates. So we need many extra qubits to act as redundant information.
The Quantum Race is Underway
Intelligence agencies already intercept and store large amounts of encrypted data. This data is hoarded in deep, secure vaults… without actually being opened or read.
Store Now, Decrypt Later (SNDL)
Store now, decrypt later (SNDL) is a surveillance strategy for “harvesting” files that can’t be immediately opened. These files are then stored until quantum computers can crack them.
This is effective because some of the information around today will still be valuable in a decade: sensitive data; state secrets; financial records; scientific research; etc.
According to a White House national security memorandum:
“A quantum computer of sufficient size and sophistication… will be capable of breaking much of the public-key cryptography used on digital systems across the United States and around the world. When it becomes available, [it] could jeopardize civilian and military communications, undermine supervisory and control systems for critical infrastructure, and defeat security protocols for most Internet-based financial transactions.”
Post-Quantum Cryptography (Quantum-Resistant Cryptography)
Since we rely so much on RSA, quantum computing poses a major threat. That’s why post-quantum security is such a hot topic. We’ll need new encryption methods that are quantum resistant. These methods must still work even if computing power makes leaps of progress.
In 2022, the U.S. government kicked off a plan to adopt quantum-resistant algorithms nationwide. The National Institute of Standards and Technology (NIST) started this process even earlier—in 2016. The current timeline is as follows:
| 2016 | NIST initiates a competition to find quantum-resistant algorithms. |
| 2017 | NIST releases a request for proposals (RFP). |
| 2018 | NIST receives over 80 submissions in response to the RFP. |
| 2019-2021 | NIST narrows the submitted algorithms to a list of 15 candidates. |
| 2022 | NIST announces the first four quantum-resistant cryptographic algorithms: Crystals-Kyber, Crystals-Dilithium, Falcon, and SPHINCS+. |
| 2023-2025 | NIST evaluates the other 11 candidates and may announce more finalists. |
| 2026 | NIST publishes a final standard for quantum-resistant cryptography. |
NIST also wants these algorithms to work with current systems. This will make it easier for organizations to switch to post-quantum cryptography.
