RSA as we know it is a public-key cryptography system invented in 1977, based on the mathematical difficulty of factoring the product of two large prime numbers.

Today, RSA is widely used in securing web browsing via HTTPS, email encryption through protocols like S/MIME, and digital signatures for verifying document authenticity.It also secures virtual private networks (VPNs), file transfers (FTPS and SFTP), etc. Thus being an integral part to data privacy and security.

Today, this data is secure thanks to this encryption method as it would take traditional computers millions of years to break.

But quantum computing is emerging as a game-changer.

Store Now, Decrypt Later: Preparing for the Quantum Age

The SNDL strategy is predicated on the belief that within the next 10 to 20 years, quantum computers will be capable of decrypting this data swiftly, which is a threat. The National Security Administration has warned that if a strong enough quantum computer is developed, it could break all the commonly used encryption methods, making all that stored encrypted data readable.

On January, 2023 The US Congress passed a Bill mandating all agencies to find new cryptographic methods which are ‘quantum-resistant’.

A Brief History of Encryption

Before diving into the implications of quantum computing, it’s important to understand the origin of encryption.

Before the 1970s, secure communication relied on symmetric key algorithms. This required exchanging secret keys in person, which actually was impractical for widespread use.

In 1977, Rivest, Shamir, and Adleman revolutionised encryption with the RSA algorithm, an asymmetric key system that enables secure communication without the need for a prior secret exchange.

RSA encryption uses two keys: a public key for encrypting messages and a private key for decrypting them. Each user creates two large secret prime numbers (private key) and multiplies them together to form the public key. Only someone who knows these original prime numbers can decrypt messages that were encrypted with the public key.

Quantum Computing: A Game Changer
The security of RSA encryption relies on the difficulty of factoring large composite numbers, a task that would take about 16 millions of years even for a Super computer. Quantum computers, however, operate on a fundamentally different principle.

In classical computing, a bit is binary and can exist in one of two states: 0 or 1.
A classical system with two bits can represent any one of four possible states: 00, 01, 10 or 11, representing numbers 1, 2, 3 and 4.
So if we want to do a calculation it can be done only one state at a time.

Or example if we want use any of the number to calculate the power of 5, only one operation can be done at a time by this bit pair. Example, using 11 i.e. 3, to calculate 5n = 53 = 125.

In contrast, a qubit can exist in a state that is a combination of both 0 and 1 simultaneously, thanks to superposition. So 2 Qubits can be at 4 different states at the same time i.e. 00, 01, 10 ,11

Mathematically, a qubit can be described as a linear combination of its basis states:
∣ψ⟩=α ∣0⟩+β ∣1⟩

where 𝛼 and β are complex numbers that describe the probability amplitudes of the qubit's state, and

When multiple qubits are in superposition, they can represent all possible combinations of their states simultaneously. For example, two qubits can be in a superposition of all four states (00, 01, 10, and 11) at the same time. As a result, an n-qubit system can simultaneously represent 2n states, thus able to do 2n calculations in at the same time, reducing the time complexity exponentially compared to classical bits.

But there was once issue. The answers to the calculations of all states also came as a superposition. So even if we calculate, the result is unreadable. That's where the Shor's algorithm comes in, which uses Fourier Transform to separate the superpositions.

Shor's Algorithm and Quantum Factorisation
The breakthrough came in 1994 when Peter Shor developed an algorithm that could leverage quantum computing to factor large numbers exponentially faster than classical algorithms. Here’s a simplified explanation of how a quantum computer could break RSA encryption:

1. Initial Setup: Start with a large number N which is the product of two prime numbers, p and q. The goal is to find these primes.

2. Select a Random Number g: Choose a random number g that doesn't share any factors with N. This is a bad guess for a factor.

3. Periodic Superposition: Use the quantum computer to prepare a superposition of all possible exponents of g.
   Compute g^x mod N for all x in this superposition, creating a periodic pattern due to the modular arithmetic.

4. Quantum Fourier Transform (QFT): Apply QFT to the superposition. This transforms the periodic pattern into a frequency domain, where the period of the original pattern becomes a prominent peak.

5. Extracting the Period: Measure the output of the QFT to find the period r. This period helps in finding factors of N.

6. Classical Post-Processing: Use the period r to compute g^(r/2) + 1, which are likely to share non-trivial factors with N. Apply the Euclidean algorithm to find the greatest common divisor, revealing the prime factors p and q.

The Algorithm might look very complicated, so simple put what we need to keep is mind is as follows:

1. Problem Description: Given a large integer N, the goal is to find its prime factors. For example, if N=15, the factors are 3 and 5.

2. Classical Difficulty: Factoring large integers is computationally hard for classical computers, especially as the numbers grow larger. This difficulty underpins the security of many cryptographic systems, such as RSA encryption.

3. Quantum Speedup: Shor's algorithm can factor integers in polynomial time, specifically in O((log N)2(log log N)(log log log N)), which is exponentially faster than the best-known classical algorithms (e.g., the general number field sieve, which runs in sub-exponential time).

The threat is still far away

Now the implementation lies on the number of perfect Qubits without any imperfections. But Qubits are extremely sensitive to their environment, which can cause them to lose their quantum state through a process called decoherence. Achieving a large number of high-fidelity, low-error qubits remains a significant hurdle.

As per the current technological breakthroughs, the number of physical Qubits needed to break the RSA encryption is around 20 million.

IBM's quantum computers, as an example, are mentioned as having nowhere near the required number of qubits, about 1000 Qubits.The current state of quantum computing is still in the early stages, with significant progress needed to reach the level required for such powerful computations.

Quantum Threat Mitigation: Post-Quantum Cryptography
Realising the upcoming threat from quantum computers, researchers and organisations have been developing post-quantum cryptography (PQC). In 2016, the National Institute of Standards and Technology (NIST) started a contest to find new cryptographic methods that can withstand quantum computer attacks. By 2022, they chose four algorithms to be part of the new standard for post-quantum cryptography.

One of the most promising approaches is lattice-based cryptography, which relies on the complexity of problems like the shortest vector problem (SVP) in high-dimensional lattices. We shall discuss about this in details in the next Blog.

Conclusion
The rise of quantum computing presents a major risk to existing encryption techniques. Although quantum computers powerful enough to break RSA encryption are still years off, the SNDL strategy implies that data encrypted today could be at risk in the future. Therefore, switching to quantum-resistant cryptography is critically important. Researchers are working hard to create and adopt new cryptographic standards to protect our data in a world where quantum computers exist.