Närmare att knäcka det oknäckbara: quantum computing och förbättrade kvantalgoritmer för att bryta RSA-kryptering

StockholmKvantdatorer kan potentiellt bryta krypteringsmetoder som tidigare ansågs säkra. Traditionella datorer har svårt att faktorisera stora tal, men kvantdatorer skulle kunna lösa dessa problem snabbt med Shors algoritm. Dock har det varit utmanande att bygga praktiska kvantdatorer eftersom de kräver enorma mängder resurser.

Under de senaste åren har forskare gjort framsteg inom två viktiga områden:

• Konstruktion av större kvantdatorer
• Förbättring av algoritmer som kan köras på mindre kvantkretsar

Oded Regev från New York University föreslog ett sätt att snabba upp Shors algoritm, men det krävde mer minne. Forskare vid MIT utvecklade därefter en bättre algoritm som bevarar Regevs hastighet och använder Shors minneseffektivitet. Denna nya algoritm använder färre kvantbitar och är bättre på att hantera kvantbrus. Dessa förbättringar kan hjälpa till att skapa kvantdatorer som kan ta itu med verkliga kryptografiska problem.

Att knäcka RSA-kryptering skulle kunna få enorma konsekvenser. RSA är en central del av moderna säkra kommunikationer och är svårt att bryta eftersom det innefattar faktorisering av stora tal. Shors algoritm kan potentiellt bryta denna säkerhet genom att göra det möjligt att faktorisera dessa tal med en kvantdator. Dock är det fortfarande en stor ingenjörsmässig utmaning att bygga en kvantdator som är kraftfull nog för detta.

Läs också:

Idag · 12:24

Innovativ process förvandlar växtavfall till grönt flygbränsle

Dagens största kvantdatorer har ungefär 1 100 qubits, men experter tror att vi behöver cirka 20 miljoner qubits för att använda Shors algoritm för att bryta kryptering på ett användbart sätt. MIT:s nya metod hanterar några av dessa utmaningar genom att minska antalet kvantportar som behövs, vilket är viktigt eftersom varje port tillför störningar.

MIT-teamet koncentrerar sig också på att korrigera fel eftersom kvantdatorer behöver fungera nästan felfritt för att behålla noggrannheten. De har utvecklat ett nytt sätt att minska fel, vilket gör deras algoritm mer praktisk för verkliga kvantmaskiner.

Det finns fortfarande viktiga frågor att besvara. En central fråga är om dessa förbättringar kommer att möjliggöra faktorisering av stora tal som används i modern kryptering, såsom de 2 048-bitars tal som används i RSA-kryptering. Även om dessa tekniker visar potential, krävs mer arbete innan de kan användas i säkerhetssystem i verkligheten.

Denna forskning, presenterad vid den internationella kryptologikonferensen 2024, visar framsteg inom kvantdatorer. Förbättringar av algoritmer och felkorrigering gör kvantdatoranvändning mer praktisk. Den huvudsakliga utmaningen är att skala upp dessa framsteg till den nivå som krävs för att påverka nuvarande krypteringsmetoder.