Quantumcomputers worden steeds beter in het ontbinden van grote getallen. Hoe lang duurt het nog tot de gevreesde Q-dag?

Het is het spookbeeld van alle inlichtingendiensten: een succesvolle aanval op het RSA-cryptosysteem. Overheden, banken en het leger gebruiken deze methode om geheime informatie te versleutelen die nooit in verkeerde handen mag vallen. Het RSA-cryptosysteem kan niet worden gekraakt met conventionele computers. Maar de snelle ontwikkeling van quantumcomputers maakt experts nerveus.

Bedrijven en overheden over de hele wereld zijn daarom begonnen met het implementeren van nieuwe encryptiemethoden die zelfs quantumcomputers niet kunnen kraken . De grote vraag is: hoe lang duurt het nog tot Q-Day, wanneer quantumcomputers het RSA-algoritme kunnen kraken?

De veiligheid van het RSA-algoritme is gebaseerd op het feit dat het ongelooflijk moeilijk is om een groot getal in priemfactoren te ontbinden, d.w.z. om twee priemgetallen te vinden die, wanneer vermenigvuldigd, het gewenste getal opleveren. Voor kleine getallen is de oplossing gemakkelijk te raden (bijvoorbeeld 33 = 3 × 11). Het RSA-2048-algoritme gebruikt echter getallen met meer dan 600 decimalen voor encryptie (wat overeenkomt met 2048 bits in binaire notatie). Zelfs de beste supercomputers falen hierin. Het grootste getal dat tot nu toe met RSA is ontbonden, heeft 250 decimalen. De berekening duurde enkele maanden. Omdat de rekentijd exponentieel toeneemt met de grootte van het getal, vormen supercomputers geen bedreiging.

De huidige quantumcomputers zijn nog verder verwijderd van het ontbinden van een getal van 2048 bits. Het record staat momenteel in handen van Chinese onderzoekers . Door een klassiek algoritme te combineren met een quantumalgoritme, hebben ze onlangs het 25-cijferige getal 1.034.879.359.475.633.166.138.643 ontbonden (de uitkomst is 1.001.721.172.891 × 1.033.101.213.673).

Dergelijke gegevens halen regelmatig de krantenkoppen – vooral als ze uit China komen. Dit komt doordat ze de vrees aanwakkeren dat quantumcomputers de ontleding van grote getallen aanzienlijk zouden kunnen versnellen. Deze vrees is niet geheel ongegrond. Maar ze is niet altijd terecht. Of een quantumcomputer sneller kan rekenen dan een supercomputer, hangt ook af van het gebruikte algoritme.

Sinds 1994 is bekend dat quantumcomputers een potentiële bedreiging kunnen vormen voor het RSA-algoritme. Destijds presenteerde wiskundige Peter Shor een factorisatiealgoritme dat gebruikmaakt van bepaalde quantumeffecten.

Shor kon aantonen dat berekeningen enorm versneld kunnen worden door kwantumeffecten vakkundig te choreograferen. Terwijl de rekentijd met de beste klassieke algoritmen exponentieel toeneemt met de grootte van het getal, schaalt deze met Shors algoritme slechts met een kleine macht van de getalgrootte. Concreet betekent dit dat als een quantumcomputer in staat is om een decimaal getal van 250 cijfers te ontbinden, het ontbinden van een getal met meer dan 600 decimalen geen lastige opgave is.

Toen Shor zijn algoritme publiceerde, bestonden quantumcomputers nog niet. En ook de huidige quantumcomputers vormen geen bedreiging voor het RSA-algoritme. Het grootste getal dat tot nu toe met Shors algoritme op een quantumcomputer is ontbonden , is 21 = 3 × 7. Daarvoor heb je niet eens een rekenmachine nodig.

De reden voor deze bescheiden prestaties is dat de huidige quantumcomputers foutgevoelig zijn. Zelfs de kleinste verstoring kan ervoor zorgen dat de specifieke toestanden van de quantumbits waarmee een quantumcomputer rekent, vervallen. Hoe meer berekeningen er worden uitgevoerd, hoe groter de kans op een onjuist resultaat. En het ontbinden van grote getallen vereist een zeer groot aantal berekeningen.

In principe weten we wat we eraan kunnen doen. Door voldoende foutieve quantumbits in één eenheid te combineren, kunnen de fouten die tijdens de berekening ontstaan, worden gecorrigeerd. Dergelijke fouttolerante quantumcomputers worden momenteel ontwikkeld door bedrijven zoals IBM en Google . Het zal echter nog jaren duren voordat quantumcomputers groot genoeg zijn om complexe problemen op te lossen.

Een ander type quantumcomputer zou het doel mogelijk sneller kunnen bereiken. Het algoritme van Peter Shor vereist een digitale quantumcomputer die informatie in binaire vorm verwerkt. Er bestaan echter ook quantumcomputers die analoog werken, d.w.z. met continu veranderende fysieke grootheden.

Sinds 2011 biedt het Canadese bedrijf D-Wave dergelijke analoge quantumcomputers aan. Hoewel ze niet zo veelzijdig zijn als hun digitale tegenhangers, zijn ze wel minder foutgevoelig.

"Aanvankelijk werden de quantumcomputers van D-Wave belachelijk gemaakt door academici", zegt Dennis Willsch van het Jülich Supercomputing Centre. Daar is inmiddels verandering in gekomen. "De analoge quantumcomputers van D-Wave kunnen bepaalde optimalisatieproblemen beter en vaak energiezuiniger oplossen dan de huidige digitale quantumcomputers."

De taak om een getal te ontbinden kan ook worden geherformuleerd tot een optimalisatieprobleem (door een kostenfunctie te definiëren die geminimaliseerd wordt door de gewenste priemgetallen). Een jaar geleden slaagde de groep van Roberto Sebastiani aan de Universiteit van Trento erin om het getal 8.219.999 te ontbinden. Het resultaat is 32.749 × 251. Dit is het grootste getal dat ooit is ontbonden zonder significante input van een klassieke computer, aldus Sebastiani. Zijn groep gebruikte een D-Wave quantumcomputer met meer dan 5.000 quantumbits.

Zouden de analoge quantumcomputers van D-Wave een bedreiging kunnen vormen voor het RSA-algoritme voordat fouttolerante digitale quantumcomputers beschikbaar komen? "Dat hangt af van hoe de rekentijd wordt geschaald", zegt Willsch. Tot nu toe is alleen het Shor-algoritme bewezen sneller te zijn dan het beste klassieke algoritme dat tot nu toe bekend is.

Samen met andere onderzoekers onderzocht Willsch de rekentijd van drie factorisatiemethoden die specifiek voor analoge quantumcomputers waren ontwikkeld. Net als Sebastiani's groep gebruikte hij een quantumcomputer van D-Wave met meer dan 5000 quantumbits. In alle drie de gevallen suggereren de resultaten een exponentiële toename van de rekentijd. Dit zou betekenen dat het ontbinden van grote getallen niet significant versneld kan worden.

Wat Willschs groep nog niet heeft onderzocht, is het schaalgedrag van hybride methoden zoals die van de Chinese onderzoekers. Zij gebruikten een klassiek algoritme voor factoring. De quantumcomputer van D-Wave nam slechts een bijzonder rekenintensieve subtaak over.

"Er is niets mis met hybride technieken", zegt Sebastiani. "Ze proberen het beste van twee werelden te combineren." Maar het is vrijwel onmogelijk om de respectievelijke bijdragen van quantum- en klassieke computing aan de oplossing van het probleem te kwantificeren. De cruciale vraag of de hybride aanpak een exponentieel snelheidsvoordeel oplevert, is daarom niet eenvoudig te beantwoorden.

Willsch acht het onwaarschijnlijk dat de huidige hybride methoden een bedreiging vormen voor het RSA-cryptosysteem. Hij wil echter niet uitsluiten dat er beter schaalbare algoritmen gevonden kunnen worden. "De mogelijkheden voor hybride methoden zijn er zeker", concludeert hij.

Zolang dergelijke algoritmen niet bestaan, blijven digitale quantumcomputers de grootste bedreiging voor het RSA-algoritme. Q-day zou zelfs eerder kunnen aanbreken dan eerder werd gedacht. Het Shor-algoritme wordt voortdurend verbeterd, waardoor de behoefte aan quantumbits afneemt.

Zo heeft Google-onderzoeker Craig Gidney onlangs aangetoond dat een fouttolerante quantumcomputer met minder dan een miljoen quantumbits voldoende zou zijn om een getal met 2048 binaire cijfers te ontbinden. Voorheen werd aangenomen dat er minstens 20 miljoen quantumbits nodig zouden zijn. Misschien zouden zelfs honderdduizend quantumbits voldoende zijn met behulp van efficiënte foutcorrectiemethoden, zoals die onlangs door IBM zijn geïntroduceerd .

Dergelijke onvoorziene ontwikkelingen maken het moeilijk te voorspellen hoeveel tijd er nog rest voor de overgang naar kwantumveilige encryptiemethoden. Gidney adviseert om kwetsbare cryptosystemen na 2030 te verlaten en na 2035 niet meer toe te staan. Hoewel hij niet verwacht dat er in 2030 voldoende grote kwantumcomputers zullen bestaan, wil hij de beveiliging niet afhankelijk maken van het trage ontwikkelingstempo.