Het algoritme van Shor is de reden dat Q-Day bestaat. Uitgevonden door wiskundige Peter Shor in 1994 — meer dan een decennium voordat een quantumcomputer krachtig genoeg was om het uit te voeren — beschrijft het exact hoe een quantumcomputer grote getallen exponentieel sneller kan factoriseren dan welke klassieke machine dan ook. Omdat RSA-encryptie, de beveiligingsstandaard die het grootste deel van het internet beschermt, zijn kracht ontleent aan de moeilijkheid van het factoriseren van grote getallen, is het algoritme van Shor de directe dreiging. Het begrijpen ervan is begrijpen waarom de cryptografische migratie die momenteel plaatsvindt niet optioneel is.
Waarom RSA afhankelijk is van de moeilijkheid van factoriseren
RSA-encryptie werkt vanwege een wiskundige asymmetrie: het is triviaal om twee grote priemgetallen te vermenigvuldigen, maar buitengewoon moeilijk om het resultaat terug te factoriseren in zijn componenten. Het genereren van een RSA-sleutelpaar duurt een fractie van een seconde. Het kraken ervan door de priemfactoren te vinden van het resulterende 2048-bits getal zou op de snelste klassieke supercomputer, met het beste bekende klassieke algoritme, langer duren dan de huidige leeftijd van het universum.
De kern van het algoritme: factoriseren is periodiek
De centrale inzicht van Shor was dat het probleem van het factoriseren van een getal N kan worden herleid tot een ander probleem: het vinden van de periode van een wiskundige functie. Voor een willekeurig gekozen getal a (kleiner dan N) is de functie f(x) = aˣ mod N periodiek — ze doorloopt waarden en herhaalt zich uiteindelijk. Als je de periode r kunt vinden, kun je die gebruiken om de factoren van N te berekenen. Het factoriseringsprobleem wordt een periodezoekopdracht.
Stap voor stap: hoe het algoritme werkt
Het klassiek factoriseren van een RSA-2048-getal met het General Number Field Sieve vereist ongeveer 10³⁴ bewerkingen — meer dan het aantal atomen op aarde. Het algoritme van Shor heeft ongeveer 10¹² quantumgate-bewerkingen nodig — een verhouding van ruwweg 10²². Dat is geen kwantitatieve verbetering; het is een kwalitatieve verandering in wat berekenbaar is.
Wat het algoritme van Shor wel en niet breekt
Het algoritme van Shor bedreigt specifiek RSA en elliptische-curvecryptografie (ECC) — beide afhankelijk van wiskundige problemen (geheel-getal-factorisering en discrete logaritmen) die Shor efficiënt kan oplossen. Het breekt symmetrische encryptie zoals AES niet direct. Het algoritme van Grover kan een ongesorteerde database kwadratisch sneller doorzoeken, waardoor het effectieve beveiligingsniveau van een symmetrische sleutel wordt gehalveerd. AES-256 daalt naar ruwweg AES-128-equivalent beveiliging — wat nog steeds als veilig wordt beschouwd.
De praktische implicatie: elke HTTPS-verbinding, certificaatautoriteit, VPN, codehandtekening en cryptocurrency-portemonnee die afhankelijk is van RSA of ECC is theoretisch kwetsbaar. NISTs post-quantum standaarden — ML-KEM, ML-DSA, FN-DSA en SLH-DSA — zijn ontworpen als quantumresistente vervangingen. Migreren naar deze standaarden vóórdat een cryptografisch relevante quantumcomputer arriveert is de gehele Y2Q-uitdaging.