Peter Shor revolutionized public-key infrastructure (PKI) using concepts that trace back to 4,000-year-old Babylonian mathematics and culminated in futuristic quantum computing. Here, we explore the math with a simple, illustrative tool to break PKI by hand.
This blog is inspired by my amazing friend Ajit Hatti's mandate to present in the cryptographic corner of the Data Security Council of India, Annual Information Security Summit. It was an extremely humbling experience as an amateur enthusiast to present in front of some of the most renowned professional cryptographers. The presentation focused on leveraging Shor's algorithm to break PKI. You can explore the tool and presentation here: https://github.com/satyamtyagi/Shor-Excel.
Coincidentally, Google's recent quantum computing milestone, #Willow, is remarkably relevant to this discussion. Ajit and I also discussed the implications of this announcement in a podcast with EXPLIoT founder Aseem Jaffer, available here: https://youtu.be/eMmD6U3E8ag?si=9Wt7o2ZoA-AZ5wqx
We'll build towards Shor's algorithm by exploring:
Altogether they may look intimidating, but we will explore them in small doses with simple examples.
The father of geometry Euclid devised an efficient method to compute the Greatest Common Divisor (GCD). Here's how:
Example: GCD of 504 and 588
This method is efficient even for large numbers, with complexity O(b²), where b is the number of bits in the numbers.
To factorize both numbers:
While factorization involves identifying and comparing all factors, Euclid's algorithm skips this exhaustive process and directly computes the GCD efficiently.
Babylonian Algebra and its Connection to Modern Cryptography
Over 4,000 years ago, Babylonian mathematicians demonstrated remarkable problem-solving skills, as evidenced by a clay tablet describing the solution to the equation:
x = 7 + 60/x
While their method may seem mysterious at first, it reflects an intuitive understanding of algebraic identities that form the foundation of solving quadratic equations. Let's break down their steps and uncover the algebraic principles behind them.
The tablet outlines the following process:
At first glance, this sequence might seem like numerical wizardry. However, it cleverly applies algebraic identities that modern students encounter in middle school.
The Babylonians implicitly understood key algebraic identities, including the difference of squares:
By subtracting the second identity from the first, we arrive at:
This demonstrates how the Babylonians used quadratic reasoning, even without the modern notation we use today.
The Babylonian insight links directly to the difference of squares formula:
x- y = (x + y) × (x - y)
This formula is crucial in modern algebra and factorization. For example, in the context of Shor's algorithm:
In simpler terms, if we find an x such that x mod N = 1, then x - 1 is divisible by N, and this relationship reveals the factors of N.
Now we go to just a few hundred-year-old math to find such an x Fermat showed that if N is a prime and G is coprime to N, then: G⁻¹ mod N = 1. Euler extended this to non-primes, stating: G mod N = 1, where Φ(N) counts integers coprime to N. Using these theorems, we can pick any G coprime to N for factorizing N. So we know If G and N are coprime we can find some power p of G, G mod N = 1
Just from the above math Shor built his algorithm
You can try some examples and use the illustrative tool implemented in excel from here: https://github.com/satyamtyagi/Shor-Excel
Quantum computing transforms the complexity of factorizing large numbers from O(2ᵇ) (exponential in the number of bits, b) to O(b³) (polynomial). This dramatic improvement is possible because quantum bits, or qubits, behave dramatically different from classical bits.
This allows quantum computers to perform multiple calculations at once. To illustrate this:
Classical Bits Example:
Suppose you want to evaluate a function f(x) for two inputs x = 0 and x = 1. A classical computer would compute f(0) and f(1) sequentially, one after the other.
Quantum Bits Example:
Using a single qubit in superposition, a quantum computer can process both x = 0 and x = 1 simultaneously, effectively performing two calculations at once.
As the number of qubits increases, the quantum system can evaluate exponentially more possibilities in parallel, giving rise to its powerful speed-up.
To understand this speed-up, let's start with a simple example:
Consider solving the equation x + 1 = 3 by testing all possible values of x. Here's how it works on classical and quantum computers:
The answer is x = binary 10 (or decimal 2).
From this parallel computation, we extract x = binary 10 (or decimal 2). While this might not seem significant for small inputs, as the number of qubits grows, the quantum computer's ability to handle all values at once results in exponential speed-up compared to a classical system.
Applying quantum speed up to Shor's algorithm, to factorize N = 35. Here's how the steps compare:
Instead of sequentially searching for P, quantum computers use quantum properties to compute all the results simultaneously.
Quantum computation holds all possible values in a superposition, but extracting the desired result (e.g., the period P) is non-trivial. This is where quantum interference comes into play: the algorithm amplifies the correct answer while suppressing incorrect ones, ensuring the output reflects P when measured.
The Fourier Transform, introduced by Joseph Fourier, is a mathematical tool used to analyze periodic functions. It decomposes a complex waveform into its constituent frequencies. For instance, when you strum a guitar chord, the sound wave is a combination of frequencies from all the strings. The Fourier Transform can isolate these individual frequencies, revealing the notes being played.
In quantum computing, we use a similar technique called the Quantum Fourier Transform (QFT). However, instead of working with classical data, QFT operates on quantum states that encode many possibilities simultaneously (superposition). This makes it a critical step in Shor's algorithm for finding the period (P). As not only G mod N = 1, But also G mod N = G , The (P) is the period of the function G mod N.
The challenge in quantum factorization lies in extracting the period P of the function f(x) = Gmod N. Here's how QFT helps:
In essence, QFT condenses the periodicity information hidden in the quantum state into a readable format, allowing us to extract P.
The output of QFT provides k, and k/2 where n is the number of qubits provides a fractional approximation of j/P, i.e. k/2 = j/P where:
To compute P, we convert k/2 into its simplest fractional form using continued fractions. Let's work through an example:
Once QFT provides an approximation of the frequency, we use continued fractions to compute P. This ancient technique, even known to the Babylonians, refines the fractional approximation into its simplest form.
This process elegantly combines QFT and continued fractions to extract the period of our function G mod N needed for factorization. QFT extracts periodic information, while continued fractions convert it into a usable form.
Public Key Infrastructure (PKI) and RSA encryption rely on the assumption that factorizing large numbers is computationally infeasible for classical computers, ensuring the security of modern communication.
Quantum computers, leveraging Shor's algorithm, can disrupt this security paradigm by making factorization exponentially faster using clever mathematical insights and quantum principles.
While advancements in quantum hardware, like Google's #Willow achieving over 100 physical qubits, are impressive, the number of logical qubits -- error-corrected and usable qubits -- remains limited. It will still take time to build systems powerful enough to break RSA in practice.
One startling update comes from Australia, which has outlined plans to transition its cryptographic systems to post-quantum standards by 2030, as noted in recent guidance from the Australian Cyber Security Centre. This is partly because a quantum-based attack, derived from Shor's algorithm, can undermine virtually all conventional asymmetric cryptography -- spanning RSA, Diffie-Hellman, ECDH, and ECDSA -- once a sufficiently powerful quantum computer emerges. Although such a machine does not yet exist, the rapid progress in quantum technology indicates these older methods will eventually need to be replaced. Consequently, any new cryptographic tools intended for use beyond 2030 should align with post-quantum cryptographic standards approved by security authorities, ensuring long-term protection against future quantum threats.
In response, mathematicians and cryptographers are actively developing quantum-resistant algorithms, such as lattice-based cryptography, to secure systems against future quantum attacks.
I am hopeful that the mathematical beauty behind quantum computing, and cryptography inspires others as it inspires me. By exploring these ideas, we can drive breakthroughs uncovering innovative ways to break cryptography and, in the process, create even stronger cryptography.