By National Institute of Standards and Technology paves the way to a post-quantum (computing) world.
The three standards are:
ML-KEM (originally CRYSTALS-Kyber)
ML-DSA (originally CRYSTALS-Dilithium)
SLH-DSA (originally SPHINCS+)
This marks as a first real step towards protecting encrypted data from the upcoming possible threats of quantum computers. I know overall this sounds alarmist, like most news lately, but honestly, I do understand the rush and panic of the fact that a lot of existing encryption algorithms are currently vulnerable against a quantum computer.
Inherent Vulnerability To Quantum Attacks
Even without a deep understanding of the underlying mathematics, I can point out however that some widely-used encryption algorithms like AES and SHA are expected to remain relatively secure against quantum attacks, while others like RSA and the popular Curve25519 are not.
RSA is primarily used for secure web browsing (HTTPS), SSH connections, email encryption, VPNs, digital certificates, and software licensing.
Curve25519, on the other hand, is commonly found in messaging apps (Signal, WhatsApp), VPN protocols, secure boot, and cryptocurrencies.
RSA And Shor’s Algorithm
In my opinion, one of the most important cryptographic algorithms that has been widely used in encryption schemes, is the RSA (Rivest–Shamir–Adleman) algorithm. The algorithm is still remarkable to this day: you pick two large prime numbers and multiply them to get a public key that anyone can use to encrypt messages. However, only someone with the knowledge of the original primes (the private key) can decrypt these messages.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
import random def generate_prime(bits): while True: candidate = random.getrandbits(bits) if is_prime(candidate): # Assume a 'is_prime' function exists return candidate p = generate_prime(1024) q = generate_prime(1024) n = p * q phi_n = (p - 1) * (q - 1) # Euler's totient function e = 65537 d = pow(e, -1, phi_n) # Modular inverse # Encryption ciphertext = pow(message, e, n) # Decryption message = pow(ciphertext, d, n) |
RSA’s security relies on the difficulty of factoring large numbers into their prime components. And this makes is fundamentally vulnerable to quantum computing attacks because of Shor’s algorithm, a quantum computing technique that directly undermines the RSA foundation by offering an efficient method for factorization.
Let’s Attempt To Break RSA
So we can imagine a secure messaging app that uses RSA for the encryption key exchange that happens between users. Further on, we intercepted the message containing an RSA-encrypted key. Now, to decrypt the message, the attacker needs to factor the large modulus ‘N’ used in the RSA encryption.
Classical: Simulating RSA Key Generation and Shor’s Attack (Conceptual)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
import random import time from sympy import isprime, randprime def extended_euclidean_algorithm(a, b): if b == 0: return a, 1, 0 else: gcd, x1, y1 = extended_euclidean_algorithm(b, a % b) x = y1 y = x1 - (a // b) * y1 return gcd, x, y def modular_inverse(a, m): gcd, x, y = extended_euclidean_algorithm(a, m) if gcd != 1: return None else: return x % m def find_period_classical(a, N): x = 1 while True: if (a ** x) % N == 1: return x x += 1 def shor_attack(N): a = random.randint(2, N-1) if math.gcd(a, N) != 1: return math.gcd(a, N), N // math.gcd(a, N), None r = find_period_classical(a, N) if r % 2 != 0: return shor_attack(N) x = a**(r//2) + 1 y = a**(r//2) - 1 p = math.gcd(x, N) q = math.gcd(y, N) phi_N = (p - 1) * (q - 1) _, d, _ = extended_euclidean_algorithm(e, phi_N) d = d % phi_N # Ensure 'd' is positive return p, q, d # Generate an RSA key pair e = 65537 public_key, private_key = generate_rsa_key() N = public_key[1] # Simulate the attacker using Shor's algorithm to factor N start_time = time.time() p, q, d = shor_attack(N) end_time = time.time() if p and q: print(f"Shor's algorithm (classical simulation) factored N in {end_time - start_time:.2f} seconds") print(f"The factors of {N} are: {p} and {q}") print(f"The private exponent d is: {d}") # Attacker now has the private key and can decrypt any messages # ... else: print("Shor's algorithm (classical simulation) failed to factor N") |
Explanation:
Even without a deep understanding of the math, a basic grasp of the code reveals why classical computers still struggle to break RSA:
- Exponential complexity.
- Key Size. Computers can do maths fast, but astronomically large numbers that are still hard to compute. Just imagine doing 600 decimal digit long calculations.
- No known efficient algorithm that can somehow solve the memory issues.
Overall key point is the size of qubits stored in memory. Factoring a 2048-bit RSA is required estimated 4 milion qubits. Each additional qubits, as we know doubles the memory required to represent the quantum state. There are many more issues such as Gate Operations, but in short, simulating a large ammount of qubits is impossible for now in classical computers, and even the most powerful supercomputer will deplete it’s memory in a matter of seconds when working with these calculations.
To estimate how long it would take to break a 2048-bit RSA key, we must first assume we can harness a supercomputer’s processing power, while ensuring its memory isn’t exhausted in the process. Even then, we’re looking at decryption times ranging from years to decades. However, stacking assumptions upon assumptions rarely leads to accurate predictions.
Quantum: RSA, Shor’s Attack (with Qiskit Simulation)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
import random import time import math from sympy import isprime, randprime from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute, Aer from qiskit.circuit.library import QFT def extended_euclidean_algorithm(a, b): if b == 0: return a, 1, 0 else: gcd, x1, y1 = extended_euclidean_algorithm(b, a % b) x = y1 y = x1 - (a // b) * y1 return gcd, x, y def modular_inverse(a, m): gcd, x, _ = extended_euclidean_algorithm(a, m) if gcd != 1: return None else: return x % m def modular_exponentiation(a, power, N): result = 1 while power > 0: if power % 2 == 1: result = (result * a) % N a = (a * a) % N power //= 2 return result def quantum_period_finding(a, N): n_qubits = 2 * math.ceil(math.log2(N)) qr = QuantumRegister(n_qubits) cr = ClassicalRegister(n_qubits) qc = QuantumCircuit(qr, cr) qc.h(qr) for i in range(n_qubits): qc.append(QFT(n_qubits), qr) qc.measure(qr, cr) simulator = Aer.get_backend('qasm_simulator') result = execute(qc, simulator, shots=1024).result() counts = result.get_counts() max_count = 0 period = None for measured_value, count in counts.items(): if count > max_count: max_count = count period = int(measured_value, 2) return period def generate_rsa_key(bits=2048): p = randprime(2**(bits//2 - 1), 2**(bits//2)) q = randprime(2**(bits//2 - 1), 2**(bits//2)) N = p * q phi_N = (p - 1) * (q - 1) e = 65537 d = modular_inverse(e, phi_N) return (e, N), (d, N) def shor_attack(N, e): a = random.randint(2, N-1) if math.gcd(a, N) != 1: return math.gcd(a, N), N // math.gcd(a, N), None r = quantum_period_finding(a, N) if r % 2 != 0: return shor_attack(N, e) x = modular_exponentiation(a, r // 2, N) + 1 y = modular_exponentiation(a, r // 2, N) - 1 p = math.gcd(x, N) q = math.gcd(y, N) phi_N = (p - 1) * (q - 1) _, d, _ = extended_euclidean_algorithm(e, phi_N) d = d % phi_N return p, q, d e = 65537 public_key, private_key = generate_rsa_key(bits=32) N = public_key[1] print(f"RSA Modulus (N): {N}") # Simulate the attacker using Shor's algorithm to factor N start_time = time.time() p, q, d = shor_attack(N, e) end_time = time.time() if p and q: print(f"Shor's algorithm (simulated) factored N in {end_time - start_time:.2f} seconds") print(f"The factors of {N} are: {p} and {q}") print(f"The private exponent d is: {d}") else: print("Shor's algorithm (simulated) failed to factor N") |
Note: Actual implementations of Shor’s algorithm and quantum period finding on real quantum hardware would be much more complex.
RSA’s Quantum Achilles’ Heel
Shor’s algorithm uses the Quantum Fourier Transform. Think of QFT as a high-performance function in your code library. You can feed it quantum data (like a list of qubits), and it returns the most prominent frequencies or patterns hidden within that data. Quantum computers can leverage superposition by allowing qubits to exist in multiple states simultaneously. Shor’s algorithm uses this to evaluate multiple potential factors of the large number at the same time.
Kind of like looking for a book in a astronomical library, in classical computing you search for one book at a time, while quantum approach allow you to scan all the books simultaneously.
In Conclusion
The National Institute of Standards and Technology’s release is a necesary wake up call, in the face of a possible quantum computing revolution. The potential breakthroughs of this new tech are unimaginable, but the prospect of breaking current encryption algorithms, is something that can rightfully keep people up at night.
News Source: https://www.schneier.com/blog/archives/2024/08/nist-releases-first-post-quantum-encryption-algorithms.html
Photo Source: https://www.flickr.com/photos/feuilllu/46753932291