Nieuw kwantumalgoritme laat 20-miljoen-qubit computer 2048-bit RSA in 8 uur kraken

• Onderzoekers ontwikkelen een nieuw kwantumalgoritme dat minder bronnen gebruikt voor code-kraak berekeningen.
• Een 20-miljoen-qubit kwantumcomputer die op dit algoritme draait, zou slechts 8 uur nodig hebben om 2.048-bit RSA-versleuteling te kraken.

Het is zeker dat kwantumcomputers in staat zullen zijn om bestaande versleutelingscodes te kraken die gebruikt worden voor het verzenden van geheime berichten. Deze versleutelingstechnieken zijn nooit volledig betrouwbaar geweest. In plaats daarvan hangen ze af van complexe wiskundige functies die maar in één richting werken, wat het makkelijk maakt om informatie te versleutelen.

De veiligheid van zulke technieken is gebaseerd op de tijd die een klassieke computer nodig heeft om de informatie te ontcijferen. Moderne versleutelingstechnieken zijn bijna onbreekbaar, omdat het duizenden jaren zou duren voor de huidige computers om hun code te ontcijferen.

Kwantumcomputers zouden deze codes echter met gemak kunnen breken, en deze machines zijn dichter bij de realiteit dan verwacht.

Onlangs bedachten onderzoekers van Google en KTH Royal Institute of Technology in Zweden een efficiëntere techniek die kwantumcomputers kunnen gebruiken om geheime berichten te ontcijferen. Het zou kwantumcomputers toestaan om minder bronnen te gebruiken voor code-kraak berekeningen.

Kwantumcomputers worden krachtiger

In 1994 ontwikkelde de Amerikaanse wiskundige Peter Shor een kwantumalgoritme voor het ontbinden van grote getallen exponentieel sneller dan de beste bestaande algoritmes op een klassieke computer. Hij stelde dat een voldoende krachtige kwantummachine moderne versleutelingstechnieken met gemak zou kunnen breken.

In het afgelopen decennium is veel vooruitgang geboekt in kwantumcomputing. In 2012 waren wetenschappers in staat om een 4-qubit kwantumcomputer te gebruiken om '143' te ontbinden. Twee jaar later gebruikten ze een vergelijkbare machine om '56153' te ontbinden.

Gegeven de voortgangssnelheid, zullen kwantumcomputers binnenkort de huidige computers kunnen overtreffen. Tenminste, dat is wat wetenschappers een paar jaar geleden verwachtten.

Het blijkt dat het ontbinden van grote getallen in kwantummachines veel moeilijker is dan geanticipeerd. Dit komt door de significante ruis in grote kwantumcomputers. Het probleem kan aangepakt worden door foutcorrectiecodes te gebruiken, die zelf extra qubits vereisen.

Referentie: arXiv:1905.09749 | MIT Technology Review

Rekening houdend met deze ruisfactor, zou een kwantumcomputer één miljard qubits nodig hebben om 2048-bit getallen te ontbinden (of om 2048-bit RSA-versleuteling te ontcijferen). Echter, de huidige universele kwantumcomputers hebben slechts 70 qubits.

Modulaire exponentiële

Het nieuwe algoritme stelt kwantumcomputers in staat om deze berekeningen met slechts 20 miljoen qubits uit te voeren. Feitelijk hebben onderzoekers getoond dat een kwantumapparaat dat op dit nieuwe algoritme draait, slechts 8 uur nodig zou hebben om 2.048-bit RSA-versleuteling te kraken.

Hun methode voert modulaire exponentiële uit — een type exponentiële berekening die uitgevoerd wordt over een modulus — op een efficiënte manier. Deze wiskundige operatie is computationeel duur in Shor's algoritme.

Onderzoekers hebben verschillende manieren gevonden om deze operatie te optimaliseren, wat de benodigde bronnen om het algoritme uit te voeren drastisch vermindert.

Hoewel een kwantumcomputer met 20-miljoen-qubit niet haalbaar is in de nabije toekomst, moeten beveiligingsexperten nadenken over een nieuwe vorm van versleuteling die zelfs een krachtige kwantumcomputer niet kan kraken.