De algoritmen van Shor en Grover uitgelegd

Kwantumcomputers voeren klassieke algoritmen niet alleen sneller uit — ze benutten kwantumsuperpositie en interferentie om bepaalde problemen exponentieel sneller op te lossen. Twee algoritmen vormen een bedreiging voor de meeste cryptografie die momenteel wordt ingezet: dat van Shor (breekt RSA/ECC) en dat van Grover (verzwakt symmetrische cryptografie en hashfuncties).

Het algoritme van Shor (1994) lost integerfactorisatie en het discrete logaritme in polynomiale tijd op een kwantumcomputer op. Hiermee breekt het RSA (gebaseerd op factorisatie), Diffie-Hellman (discrete logaritme modulo p) en ECDH/ECDSA (discrete logaritme op elliptische krommen) rechtstreeks.

Het belangrijkste onderdeel van Shor is de kwantum-Fouriertransformatie (QFT) — een exponentieel snellere kwantumversie van de DFT. Bij het vinden van een periode bepaalt de QFT de periode van f(x) = a^x mod N, waaruit de factoren van N met GCD worden afgeleid.

Om N te factoriseren: (1) Kies een willekeurige a < N en controleer gcd(a,N)=1. (2) Vind de periode r van f(x)=a^x mod N met behulp van de QFT. (3) Met hoge waarschijnlijkheid levert gcd(a^{r/2}±1, N) een niet-triviale factor op. De klassieke stap is O(log N); het kwantumalgoritme voor het vinden van de periode is O((log N)^3) — polynomiaal.

Beste klassieke factorisatiemethode: GNFS — subexponentieel O(exp((64/9 log N)^{1/3} log log N)^{2/3})). Shor op een fouttolerante kwantumcomputer: polynomiaal O((log N)^3). RSA-2048 vereist ongeveer 4000 logische qubits en ongeveer 10^9 poortbewerkingen. De huidige NISQ-computers hebben ongeveer 1000 ruisende qubits — ze vormen nog geen bedreiging.

Het algoritme van Grover (1996) biedt een kwadratische versnelling voor ongestructureerd zoeken. Voor een zoekruimte met N items hebben klassieke algoritmen O(N) query's nodig; Grover heeft O(√N) nodig. Toegepast op cryptografie: het breekt symmetrische sleutels van n bits in O(2^{n/2}) in plaats van O(2^n).

AES-128: klassieke beveiliging 2^128, door Grover teruggebracht tot 2^64 — onveilig tegenover een grote kwantumcomputer. AES-256: 2^256 → 2^128 — nog steeds veilig. Oplossing: verdubbel de grootte van symmetrische sleutels. Botsingsbestendigheid van SHA-256: 2^128 → 2^85 (verjaardagsaanval + Grover). Voorafbeeldingsbestendigheid van SHA-256: 2^256 → 2^128 — in orde.

De huidige NISQ-kwantumcomputers (IBM Heron: 133 qubits, Google Sycamore: 70 qubits) zijn te klein en te ruisend voor cryptografisch relevante berekeningen. Schattingen voor het breken van RSA-2048 liggen tussen 2035 en 2050 met fouttolerante kwantumcomputers. Aanvallen waarbij gegevens nu worden verzameld en later ontsleuteld, vormen nu al een bedreiging.

Tegenstanders verzamelen vandaag versleuteld verkeer en slaan het op. Zodra er een kwantumcomputer beschikbaar is, ontsleutelen ze het met terugwerkende kracht. Hierdoor zijn geheimen met een lange levensduur (geclassificeerde overheidsgegevens, medische dossiers) nu al kwetsbaar. Voor zulke gegevens moet de migratie naar PQC nu beginnen.

Roosterproblemen (LWE, SIS), codegebaseerde problemen (McEliece), hashgebaseerde handtekeningen (SPHINCS+), multivariate problemen — er is geen bekend kwantumalgoritme in polynomiale tijd. Deze problemen vormen de basis van de postkwantumstandaarden van NIST.

De PQC-standaarden van NIST (ML-KEM, ML-DSA, SLH-DSA) zijn in 2024 definitief vastgesteld. Organisaties moeten: het huidige cryptografische gebruik inventariseren, gegevens met een lange levensduur identificeren en de inzet van PQC voor sleuteluitwisseling prioriteren (het meest urgent vanwege aanvallen waarbij gegevens nu worden verzameld en later ontsleuteld). Voor handtekeningen is meer tijd.

Het algoritme van Shor (polynomiale tijd) breekt RSA, DH en ECC. Het algoritme van Grover (kwadratische versnelling) halveert de sterkte van symmetrische sleutels. Oplossing: migreer naar de PQC-standaarden van NIST (gebaseerd op roosters). Volgende onderwerp: CRYSTALS-Kyber KEM.