Leestijd: 6 minuten
Categorie: Post-Quantum Cryptography
And when you look along the way we’ve come, there are spirals of vultures wheeling.
— Bruce Chatwin, The Songlines (2012)
De noodzaak van security
Soms hebben we een zachte herinnering nodig aan harde realiteiten. Security is geen luxeproduct; security is een basisvoorwaarde voor overleving. Helemaal onderaan de piramide van Maslow’s hiërarchie van menselijke behoeften vinden we fysiologische behoeften; direct daarboven liggen de veiligheidsbehoeften. Zonder security is er niets dat onze fysiologische behoeften beschermt. En als de middelen van ons bestaan worden bedreigd, dan zijn wij dat ook. Hetzelfde geldt als er niets is dat ons uit de gevarenzone houdt.
Security is een breed begrip. Het omvat beschikbaarheid, zeker. We hebben voedsel en water nodig. We hebben ook integriteit nodig; ons water moet drinkbaar zijn, ons voedsel eetbaar. Als er niets is dat voorkomt dat ze worden vergiftigd, zijn we niet veilig.
Omdat we mensen zijn, een plannenmakend, berekenend, complotterend kuddedier in plaats van een solitair roofdier, vergroten we onze collectieve kracht door samen te werken in groepen. Dit houdt in dat we signalen uitwisselen (communicatie), en het kan van levensbelang zijn dat die communicatie vertrouwelijk blijft. Als die vertrouwelijkheid wordt geschonden, kan onze coördinatie ontsporen en wordt het bereiken van onze gezamenlijke doelen moeilijker.
In vijandige omstandigheden kunnen concurrerende groepen succesvolle tegenstrategieën gebruiken wanneer vertrouwelijkheid wordt doorbroken. In communicatie zijn zowel integriteit als vertrouwelijkheid belangrijk. Cryptografie is het spel dat we spelen omdat we moeten communiceren, en dat betrouwbaar en privé moeten doen. Integriteit en vertrouwelijkheid. Het is een kwestie van overleven.
Dus, hoe doen we het?
Omdat we slimme symboolmanipulators zijn, maken we gebruik van een aantal wiskundige problemen die als moeilijk op te lossen worden beschouwd. Neem bijvoorbeeld priemfactorisatie[0]. Als je twee grote priemgetallen (zeg p en q) met elkaar vermenigvuldigt, krijg je een heel groot getal n dat alleen deelbaar is door p en q. Als je alleen n hebt, zonder verdere informatie, kost het enorm veel tijd om p en q te achterhalen (dit heet ‘factoren’). Maar als je p (of q) al kent, is het heel eenvoudig om q (respectievelijk p) te berekenen. Dit is de basis van het Rivest-Shamir-Adleman (RSA) cryptografische schema. Het wordt sinds 1977 gebruikt en zal voorlopig nog wel bij ons blijven.
(Opmerking: RSA is niet de enige methode. Er bestaan ook andere cryptografische schema’s; RSA is gewoon een typisch en representatief voorbeeld.)
Hoe moeilijk is het om p en q uit n te halen? Dat hangt af van de lengte van n, die natuurlijk wordt bepaald door de lengtes van p en q. Die lengte wordt uitgedrukt in het aantal bits van de binaire representatie van n. Kleiner is makkelijker, groter is moeilijker. Het ontbinden van het getal 9 is niet zo moeilijk, toch? En 143? Probeer nu 16016003. Gelukt? Dan nu 4097280091. Nog steeds bij de les? Probeer dan 250112012543. Het wordt snel lastig. Het laatste getal gebruikt 20-bits getallen. Klein spul, maar toch al behoorlijk uitdagend.
Tot nu toe doen we het goed. Uitgebreide cryptanalyse heeft geen werkbare aanvallen opgeleverd tegen cryptografie die gebruikmaakt van voldoende grote sleutelgroottes. Brute force werkt niet; de grootste RSA-sleutel die ooit is gekraakt was RSA-250, met een sleutelgrootte van 829 bits. Dat kostte 2700 ‘core-jaren’ aan rekenkracht[1]. 2048-bit RSA-sleutels zijn al lange tijd de ondergrens in best practices, terwijl 1024-bit RSA sinds 2013 als verouderd wordt beschouwd.
OH ja?
Wat goed dat je het vraagt. Er wordt volop durfkapitaal opgehaald, investeerders smeden plannen, en de daaropvolgende FOMO-gekte in de wereld van tech-investeerders draait op volle toeren. Waarom? Er zijn een paar theoretische doorbraken geweest in de wereld van kwantumalgoritmen.
Shor’s en Grover’s algoritmen
In 1994 liet Peter Shor zien [2] dat een kwantumcomputer gebruikt kan worden om een getal n in polynomiale tijd te factoriseren, en daarmee in feite RSA te breken.
Daarnaast publiceerde Lov Grover in 1996 [3] een generiek zoekalgoritme dat gebruikmaakt van kwantumsuperpositie. Daardoor kunnen meerdere mogelijkheden tegelijk worden doorzocht, wat resulteert in een kwadratische snelheidswinst.
Indrukwekkende theoretische resultaten, zeker. Maar is dat genoeg om klassieke cryptografie de das om te doen?
Q DAY
Om Shor’s algoritme uit te voeren is een kwantumcomputer nodig met een aantal qubits dat in verhouding staat tot de sleutellengte. Het kraken van een 2048-bit RSA-sleutel binnen acht uur vereist iets meer dan ongeveer 6000 logische qubits (uitgaande van een basale foutmarge van 0,001).
Dat is een hoop qubits. De grootste kwantumcomputers die momenteel bestaan, zijn IBM’s Condor en Atom’s Atomic Array, die allebei iets meer dan 1000 qubits hebben [4]. De vraag is dus: wanneer (als het ooit gebeurt) zullen we kwantumcomputers zien die een orde van grootte groter zijn?
En als dat moment komt (als het ooit komt), welk deel van onze huidige cryptografie-architectuur zal instorten, en welke delen zullen overeind blijven?
En dat is waarom we hier zijn
We hebben geen glazen bol (sorry). Zoals Niels Bohr zei: “prediction is very difficult, especially of the future.”
Wat we wél weten, is dat dingen tijd, toewijding en geld kosten. We kunnen ons afvragen wat de ontwikkeling eigenlijk aandrijft. Louter nieuwsgierigheid wordt zelden royaal gefinancierd, dus er moeten realistische (of in elk geval als realistisch beschouwde) use cases worden gepresenteerd. Daar is tot nu toe een gebrek aan. Behalve het verzwakken van een deel van de oude cryptografie is er weinig tot niets concreets aangedragen. Dat roept vragen op over de haalbaarheid van het hele proces.
Als het kraken van bestaande crypto de enige reden zou zijn om kwantumcomputers te bouwen, waarom zou iemand dat dan nog doen zodra cryptografie quantum-proof is gemaakt? Ondanks beweringen van het tegendeel zijn er tot nu toe geen overtuigende, concrete use cases uit de echte wereld gepresenteerd.
Someday — and that day may never come — I’ll call upon you to do a service for me.
— Marlon Brando as Don Corleone in The Godfather (1972)
Of we nu wel of niet weten wanneer krachtige kwantumcomputers hun intrede doen, we kunnen nu al de gevolgen van hun komst in kaart brengen en ons erop voorbereiden. Op basis van Q-day en een analyse van de cryptografie die dan mogelijk kwetsbaar is, kunnen we vaststellen welke eisen er gelden voor data die nu wordt opgeslagen en op Q-day nog steeds beschermd moet zijn. Er kunnen plannen worden gemaakt, aanpakken worden gedefinieerd en transities worden uitgevoerd.
We zijn hier. Dat is wat we doen.
REFERENties
0. Though it should be noted that it has not been proven that prime factorization is intractable (superpolynomial), see [1]
1. Integer factorization Wikipedia (March 30, 2025) https://en.wikipedia.org/wiki/Integer_factorization
2. Shor’s Algorithm Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484-26. Doi: https://dx.doi.org/10.1137/S0097539795293172
3. Grover’s Algorithm Grover, Lov K. (1996-07-01). “A fast quantum mechanical algorithm for database search”. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing – STOC ‘96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery. pp. 212–219. arXiv:quant-ph/9605043. Bibcode:1996quant.ph..5043G. doi:10.1145/237814.237866. ISBN 978-0-89791-785-8. S2CID 207198067
4. SpinQ, ‘Discover the World’s Largest Quantum Computer in 2025′
https://www.spinquanta.com/news-detail/discover-the-worlds-largest-quantum-computer-in20250106092507
