211service.com
Hoe een kwantumcomputer de 2048-bits RSA-codering in 8 uur kon breken
Een close-up van de D-Wave Vesuvius-chip Steve Jurvetson | Flickr
Veel mensen maken zich zorgen dat kwantumcomputers bepaalde codes kunnen kraken die worden gebruikt om beveiligde berichten te verzenden. De codes in kwestie versleutelen gegevens met behulp van wiskundige valluikfuncties die gemakkelijk in de ene richting werken, maar niet in de andere. Dat maakt het coderen van gegevens eenvoudig, maar het decoderen ervan enorm moeilijk zonder de hulp van een speciale sleutel.
Deze encryptiesystemen zijn nooit onbreekbaar geweest. In plaats daarvan is hun beveiliging gebaseerd op de enorme hoeveelheid tijd die een klassieke computer nodig zou hebben om het werk te doen. Moderne coderingsmethoden zijn speciaal ontworpen zodat het decoderen ervan zo lang zou duren dat ze praktisch onbreekbaar zijn.
Maar kwantumcomputers veranderen dit denken. Deze machines zijn veel krachtiger dan klassieke computers en zouden deze codes met gemak moeten kunnen breken.
Dat roept een belangrijke vraag op: wanneer zullen kwantumcomputers krachtig genoeg zijn om dit te doen? Na die datum wordt alle informatie die door deze vorm van codering wordt beschermd, onveilig.
Dus computerwetenschappers hebben geprobeerd te berekenen hoeveel hulpbronnen zo'n kwantumcomputer nodig heeft en vervolgens uit te rekenen hoe lang het duurt voordat zo'n machine kan worden gebouwd. En het antwoord is altijd decennia geweest.
Tegenwoordig moet dat denken worden herzien dankzij het werk van Craig Gidney bij Google in Santa Barbara en Martin Ekerå bij het KTH Royal Institute of Technology in Stockholm, Zweden. Deze jongens hebben een efficiëntere manier gevonden voor kwantumcomputers om de codebrekende berekeningen uit te voeren, waardoor de middelen die ze nodig hebben in orde van grootte worden verminderd.
Bijgevolg zijn deze machines beduidend dichter bij de werkelijkheid dan iedereen vermoedde. Het resultaat zal onaangenaam lezen zijn voor regeringen, militaire en veiligheidsorganisaties, banken en iedereen die gegevens voor 25 jaar of langer moet beveiligen.
Eerst wat achtergrond. In 1994 ontdekte de Amerikaanse wiskundige Peter Shor een kwantumalgoritme dat beter presteerde dan zijn klassieke equivalent. Het algoritme van Shor houdt rekening met grote getallen en is het cruciale element in het proces voor het kraken van op valluiken gebaseerde codes.
Trapdoor-functies zijn gebaseerd op het vermenigvuldigingsproces, dat gemakkelijk in één richting kan worden uitgevoerd, maar veel moeilijker in omgekeerde richting. Het is bijvoorbeeld triviaal om twee getallen met elkaar te vermenigvuldigen: 593 keer 829 is 491.597. Maar het is moeilijk om met het getal 491.597 te beginnen en uit te zoeken welke twee priemgetallen moeten worden vermenigvuldigd om het te produceren.
En het wordt steeds moeilijker naarmate de aantallen groter worden. Computerwetenschappers vinden het namelijk praktisch onmogelijk voor een klassieke computer om getallen te ontbinden die langer zijn dan 2048 bits, wat de basis is van de meest gebruikte vorm van RSA-codering.
Shor toonde aan dat een voldoende krachtige kwantumcomputer dit met gemak kan, een resultaat dat schokgolven door de beveiligingsindustrie stuurde.
En sindsdien zijn kwantumcomputers steeds krachtiger geworden. In 2012 gebruikten natuurkundigen een kwantumcomputer van vier qubits tot factor 143. In 2014 gebruikten ze een soortgelijk apparaat tot factor 56.153.
Het is gemakkelijk voor te stellen dat kwantumcomputers in dit tempo van vooruitgang binnenkort in staat zouden moeten zijn om beter te presteren dan de beste klassieke.
Niet zo. Het blijkt dat kwantumfactoring in de praktijk veel moeilijker is dan anders zou worden verwacht. De reden is dat ruis een groot probleem wordt voor grote kwantumcomputers. En de beste manier om ruis op dit moment aan te pakken, is door foutcorrigerende codes te gebruiken die zelf aanzienlijke extra qubits vereisen.
Als u hiermee rekening houdt, nemen de middelen die nodig zijn om 2048-bits getallen te factoriseren drastisch toe. In 2015 schatten onderzoekers dat een kwantumcomputer een miljard qubits nodig zou hebben om het werk betrouwbaar te doen. Dat is aanzienlijk meer dan de 70 qubits in de moderne kwantumcomputers.
Op basis daarvan hadden beveiligingsexperts wellicht het idee kunnen rechtvaardigen dat het tientallen jaren zou duren voordat berichten met 2048-bits RSA-codering door een kwantumcomputer zouden kunnen worden verbroken.
Nu hebben Gidney en Ekerå laten zien hoe een kwantumcomputer de berekening kan doen met slechts 20 miljoen qubits. Ze laten inderdaad zien dat zo'n apparaat slechts acht uur nodig zou hebben om de berekening te voltooien. [Als resultaat] is de schatting in het slechtste geval van hoeveel qubits nodig zijn om 2048-bits RSA-getallen te factoriseren, bijna twee ordes van grootte gedaald, zeggen ze.
Hun methode is gericht op een efficiëntere manier om een wiskundig proces uit te voeren dat modulaire machtsverheffing wordt genoemd. Dit is het proces van het vinden van de rest wanneer een getal wordt verhoogd tot een bepaalde macht en vervolgens wordt gedeeld door een ander getal.
Dit proces is de meest rekenkundige bewerking in het algoritme van Shor. Maar Gidney en Ekerå hebben verschillende manieren gevonden om het te optimaliseren, waardoor er aanzienlijk minder middelen nodig zijn om het algoritme uit te voeren.
Dat is interessant werk dat belangrijke implicaties zou moeten hebben voor iedereen die informatie voor de toekomst opslaat. Een kwantumcomputer van 20 miljoen qubit lijkt tegenwoordig zeker een verre droom. Maar de vraag die deze experts zichzelf zouden moeten stellen, is of een dergelijk apparaat binnen de 25 jaar dat ze de informatie willen beveiligen mogelijk is. Als ze denken van wel, dan hebben ze een nieuwe vorm van encryptie nodig.
Beveiligingsexperts hebben inderdaad post-kwantumcodes ontwikkeld die zelfs een kwantumcomputer niet kan kraken. Het is dus nu al mogelijk om data te beveiligen tegen toekomstige aanvallen door kwantumcomputers. Maar deze codes worden nog niet standaard gebruikt.
Voor gewone mensen is er weinig risico. De meeste mensen gebruiken 2048-bits codering of iets dergelijks voor taken zoals het verzenden van creditcardgegevens via internet. Als deze transacties vandaag worden geregistreerd en over 25 jaar worden verbroken, gaat er weinig verloren.
Maar voor regeringen staat er meer op het spel. De berichten die ze vandaag verzenden - tussen ambassades of het leger bijvoorbeeld - kunnen over 20 jaar heel belangrijk zijn en dus de moeite waard om geheim te houden. Als dergelijke berichten nog steeds worden verzonden via 2048-bits RSA-codering of iets dergelijks, moeten deze organisaties zich snel zorgen gaan maken.
Referentie: arxiv.org/abs/1905.09749 : Hoe u 2048-bits RSA-gehele getallen in 8 uur kunt factoriseren met 20 miljoen luidruchtige qubits