Quantum Cryptanalysis

Explore the algorithms that make a Cryptographically Relevant Quantum Computer (CRQC) a threat to modern cryptography. Simulate Shor's algorithm for factoring composites and Grover's algorithm for unstructured search.

The Quantum Threat

Classical cryptography relies on problems that take classical computers billions of years to solve. However, quantum computers exploit quantum mechanical phenomena—like superposition and entanglement—to solve some of these problems exponentially faster.

Shor's Algorithm: Breaks RSA (integer factorization) and ECC (discrete logarithm) in polynomial time.
Grover's Algorithm: Weakens symmetric ciphers (like AES) and hash functions (like SHA) by searching an unstructured database quadratically faster than classical brute force. This essentially halves the effective bit-strength (e.g., AES-128 becomes 64-bit secure).

Number to Factor (N)

Guess Base (a)

Algorithm Execution

1.Initialize registers. Upper register in superposition (Hadamard gates).

2.Apply controlled modular exponentiation: |x⟩|7^x mod 15⟩

3.Apply Inverse Quantum Fourier Transform (IQFT) to upper register.

4.Measure upper register. This gives a state close to k*(Q/r).
Found period r = 4

5.Classical post-processing:
gcd(7^(4/2) - 1, 15) = 3
gcd(7^(4/2) + 1, 15) = 5
Factors: 3 × 5

Simulated Measurement Probability (Upper Register)

Loading CryptoViz...