Kunnen quantumcomputers binnenkort al onze encryptie kraken? Nee, het is iets genuanceerder dan dat... Toch is het goed al rekening te houden met de komst van quantumcomputers voor de beveiliging van onze gegevens.
Koen Vervloesem
Quantumcomputers zijn een nieuwe klasse van computers met meer mogelijkheden dan onze 'klassieke' computers. In onze computers is de fundamentele eenheid van informatie een bit, die 0 of 1 als waarde heeft; in quantumcomputers is de fundamentele eenheid van informatie een qubit, die |>0, |1> of alle mogelijke combinaties van |0> of |1> tegelijk als waarde kan hebben. Zo'n combinatie van |0> en |1> noemen we een superpositie.
Op basis van die qubits kun je een hele machinerie van logische poorten opbouwen, net zoals dat bij klassieke computers gebeurt. Een belangrijk verschil is wel dat je met n qubits toestanden tegelijk kunt opslaan. Dus met 1 qubit 2 toestanden, met 2 qubits 4 toestanden, met 3 qubits 8 toestanden enzovoort. Met 32 qubits ben je al in staat om 4 miljard toestanden tegelijk op te slaan.
Werken met een quantumcomputer vereist een hele nieuwe manier van denken
Experimenteren met quantumcomputers
Een van de bedrijven die sterk inzet op quantumcomputers, is IBM. Het bedrijf biedt met IBM Q Experience [1] een publiek toegankelijk, online platform aan waarop je kunt experimenteren met het programmeren van een echte quantumcomputer. Dat begon met een eerste quantumcomputer van 5 qubits in 2016, en in 2017 voegde IBM daar één van 17 qubits aan toe. Het platform heeft al meer dan 75.000 gebruikers en leverde al meer dan 60 wetenschappelijke publicaties op. IBM heeft ook QISKit [2] ontwikkeld, een opensource Python-bibliotheek om quantumalgoritmes te ontwikkelen en op simulators of echte quantumcomputers te draaien.
Eerder dit jaar werd PC-Active uitgenodigd bij IBM in Amsterdam voor een uiteenzetting over quantumcomputers. Marc Ganzhorn, onderzoeker bij IBM Research in Zürich, waarschuwde wel dat het nog veel werk zal kosten om quantumcomputers voor algemeen gebruik beschikbaar te maken. We zijn volgens hem met quantumcomputer nu waar we met klassieke computers in de jaren 60 waren.
Toch zijn er nu al domeinen waar quantumcomputers mogelijk nuttig zijn, bijvoorbeeld in het oplossen van problemen in de quantumchemie (voor het simuleren van een kleine molecuul zijn volgens Ganzhorn 7 qubits nodig), optimalisatieproblemen, portfoliobeheer, chipontwerp enzovoort. IBM heeft met IBM Q een commercieel aanbod voor bedrijven die van quantumcomputers gebruik willen maken. Momenteel is er een 20-qubitcomputer in het aanbod en dit jaar komt er ook een 50-qubitcomputer ter beschikking.
Een quantumcomputer dient gekoeld te worden tot bijna het absolute nulpunt (–273,15 °C)
om te kunnen werken (bron: IBM Research)
Versleutelde communicatie kraken
Bijna altijd als het over quantumcomputers gaat, hoor je dat quantumcomputers onze cryptografie gaan kraken en dat daardoor beveiligde websites en betaalverkeer gekraakt worden. Gregory Neven van IBM Research in Zürich ging tijdens ons bezoek aan IBM in op die kwestie en wat we daaraan kunnen doen.
Nuttig om te weten is dat ook nu al, met onze klassieke computers, cryptografie te kraken is, als de gebruikte sleutel maar klein genoeg is. Als gebruiker A een boodschap versleutelt met een zwakke sleutel en naar gebruiker B stuurt, kan C, die de versleutelde boodschap onderschept, met voldoende rekenwerk de sleutel kraken en zo de boodschap ontcijferen. Maar A en B hebben een belangrijk voordeel tegenover C: als C zijn rekenkracht verdubbelt, hoeft A zijn sleutel maar 1 bit langer te maken om dezelfde graad van beveiliging te bieden. In de praktijk kies je voor versleutelde communicatie dus gewoon een sleutel die groot genoeg is om alle in de wereld beschikbare verwerkingskracht te kunnen weerstaan, en dan ben je voor altijd veilig.
Quantumcomputers kraken asymmetrische encryptie
Met quantumcomputers ligt dat echter anders. Die zijn door gebruik te maken van superpositie immers in staat om specifieke soorten problemen efficiënter op te lossen. En laat nu net een van die problemen de basis vormen van asymmetrische encryptie: de encryptiemethode achter digitale handtekeningen, certificaten van websites (en dus de slotjes in je webbrowser voor websites) en het uitwisselen van sleutels.
Asymmetrische encryptie, waarbij je zowel met een publieke sleutel als met een privésleutel werkt, hangt immers af van het factoriseren van getallen (het ontbinden in priemfactoren) of daarmee equivalente problemen. Voor klassieke computers is dat een moeilijk probleem, maar voor quantumcomputers niet, dankzij het algoritme van Shor. Alle huidige ingeburgerde systemen voor asymmetrische encryptie zijn dus te kraken door quantumcomputers, en dat los je niet zomaar op met grotere sleutels. De snelheidswinst van quantumcomputers in dit soort algoritmes is immers exponentieel: een factorisatie waarvoor een klassieke computer duizenden jaren nodig heeft, duurt op een quantumcomputer volgens Neven mogelijk maar enkele dagen, uren of zelfs seconden.
De sterkte van symmetrische encryptie wordt gehalveerd
Er is ook nog symmetrische encryptie, waarbij je dezelfde sleutel inzet voor de encryptie én decryptie. De algoritmes voor symmetrische encryptie worden niet alleen gebruikt voor encryptie van bestanden, maar ook voor message authentication (om te bevestigen dat een boodschap van de bron komt) en voor een hashfunctie (om bijvoorbeeld een wachtwoord te kunnen verifiëren zonder het wachtwoord zelf op te slaan).
Als een klassieke computer alle mogelijke sleutels van 128 bits wil doorzoeken om een symmetrisch versleutelde boodschap te kraken, heeft die daarvoor een aantal stappen nodig dat evenredig is met . Maar een quantumcomputer heeft met het algoritme van Grover maar de vierkantswortel van dit aantal stappen nodig, dus stappen. In essentie verkleint een quantumcomputer de sterkte van de sleutel tot 64 bits, en dat is niet sterk genoeg.
Gebruik grotere sleutels bij symmetrische encryptie
Toch is symmetrische encryptie er minder erg aan toe. Quantumcomputers kunnen dit soort encryptie dan wel efficiënter aanvallen dan klassieke computers, maar als we gewoon onze sleutels heel wat langer maken, zijn we weer veilig tegen quantumcomputers.
Het standaardalgoritme voor symmetrische encryptie is AES (Advanced Encryption Standard). Neven raadt aan om voor encryptie geen sleutels van 128 bits meer te gebruiken (AES-128), maar sleutels van 256 bits (AES-256). Als er ooit een quantumcomputer verschijnt die AES-encryptie probeert te kraken, wordt de sterkte van die sleutel gereduceerd tot 128 bits, en dat is nog ruimschoots voldoende om alle kraakpogingen te weerstaan. Voor hashfuncties raadt Neven aan om de grootte van de uitvoer van 256 bits naar 384 bits te verhogen om tegen quantumcomputers bestand te blijven.
Paniek?
Voor asymmetrische encryptie ziet het er dus niet goed uit als we ooit bruikbare quantumcomputers hebben. Moeten we dan allemaal in paniek raken? Gelukkig niet, stelt Neven ons gerust. Er zijn zelfs zaken die ook quantumcomputers niet kunnen doen. De vraag is dus of het mogelijk is om cryptografische algoritmes te baseren op problemen die quantumcomputers niet efficiënt kunnen oplossen, net zoals we asymmetrische encryptie gebaseerd hebben op problemen die voor klassieke computers niet efficiënt op te lossen zijn.
En zo komen we bij post-quantum cryptography: cryptografische algoritmes die op een klassieke computer draaien, maar veilig zijn tegenover tegenstanders met een quantumcomputer. Daarmee kunnen we onze gegevens van vandaag beschermen tegen de quantumcomputers van morgen.
Nu al overstappen?
Je stelt je nu waarschijnlijk de vraag waarom we ons nu al met post-quantum cryptography zouden moeten bezighouden. Het duurt misschien nog tientallen jaren voordat quantumcomputers krachtig genoeg zijn om onze cryptografie te kraken. Dat klopt, maar de industrie ontwikkelt zich notoir traag. Al minstens sinds 2004 waarschuwden cryptografie-experts dat de hashfunctie SHA-1 niet sterk genoeg meer is tegen tegenstanders met voldoende (klassieke) rekenkracht en nog altijd zijn er systemen die niet van SHA-1 naar SHA-256 zijn overgestapt.
Bovendien dien je er ook rekening mee te houden dat je nu misschien gegevens opslaat die momenteel nog wel veilig zijn tegen kraken, maar die over 10, 20 of 30 jaar ook nog veilig moeten zijn. Denk maar aan een cryptocurrency die gegevens opslaat in een blockchain, of je testament dat je voor je erfgenamen opslaat. Je wilt van dit soort gegevens niet alleen zeker zijn dat die nu niet te kraken zijn, maar ook over enkele decennia.
Gegevens in een blockchain van een cryptocurrency moeten ook over 30 jaar nog veilig zijn
Nieuwe algoritmes
Het Amerikaanse NIST (National Institute of Standards and Technology), dat eerder al het algoritme AES voor symmetrische encryptie en de hashfunctie SHA-3 na een open competitie standaardiseerde, is in 2016 een proces gestart om een standaard voor Post-Quantum Cryptography [3] te ontwikkelen. Er zijn 27 algoritmes voorgesteld door allerlei cryptografie-experts en die worden nu geanalyseerd. In 2023 wordt er een algoritme gekozen als standaard voor post-quantum cryptography.
Ook IBM neemt deel aan de competitie, onder meer met het algoritme CRYSTALS [4], dat gebruikmaakt van roostercryptografie. Deze tak van de cryptografie verbergt informatie in geometrische structuren (oneindige roosters van punten) in hogere dimensies. CRYSTAL versleutelt informatie met behulp van een wiskundig probleem waarvan niet bewezen is dat quantumcomputers het niet kunnen oplossen, maar waarvoor geen enkele aanwijzing bestaat dat ze het kunnen oplossen. Honderd procent zekerheid hebben we dus nooit, maar dat hebben we bij klassieke computers ook nooit gehad: van factoriseren is ook nooit bewezen dat klassieke computers het niet efficiënt kunnen doen, maar de knapste wiskundeknobbels van de wereld zijn er nooit in geslaagd een oplossing te vinden.
De toekomst?
Volgens Neven hoeven we nog niet te snel te vrezen voor een quantumcomputer die onze asymmetrische encryptie kraakt. Daarvoor hebben we immers een quantumcomputer nodig met miljoenen qubits. Maar voor gegevens die dertig jaar of langer veilig moeten blijven, kun je het best nu al overschakelen naar post-quantum cryptography. Voor symmetrische encryptie kan dat, zoals we zagen, nu al door gewoon een grotere sleutelgrootte te kiezen. En voor asymmetrische encryptie kunnen we over vijf jaar naar de NIST-standaard overstappen.
Maar er zal nog veel meer onderzoek gedaan moeten worden. Zo moeten ook algoritmes voor identiteitsbeheer, elektronisch stemmen, digitale munteenheden enzovoort opnieuw ontwikkeld worden, zodat ze veilig zijn voor quantumcomputers. Voorlopig hebben we voor die toepassingen nog geen praktische oplossingen. Er is dus nog werk aan de winkel om onze hele computerinfrastructuur bestand te maken tegen quantumcomputers.
Gregory Neven van IBM Research raadt het gebruik van post-quantum cryptography aan
voor gegevens die meer dan dertig jaar veilig moeten blijven (bron: IBM Research)
Infolinks
[1] http://research.ibm.com/ibm-qx
[2] https://qiskit.org/
[3] https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
[4] https://pq-crystals.org/
