Zooma in / Konceptuell datorkonstverk av elektroniska kretsar med blått och rött ljus som passerar genom dem, som representerar hur data kan kontrolleras och lagras i en kvantdator.
Getty bilder
Inom en inte alltför avlägsen framtid – så lite som ett decennium, kanske ingen vet exakt hur länge – kommer kryptografin som skyddar dina banktransaktioner, chattmeddelanden och medicinska journaler från nyfikna ögon att brytas spektakulärt med tillkomsten av kvantdatorer . På tisdagen namngav en amerikansk statlig myndighet fyra reservkrypteringsscheman för att förhindra denna kryptopokalyps.
Några av de mest använda krypteringssystemen för offentliga nyckel – inklusive de som använder RSA, Diffie-Hellman-algoritmer och Diffie-Hellman elliptiska kurvor – är beroende av matematik för att skydda känslig data. Dessa matematiska problem involverar (1) faktorisering av det stora sammansatta numret av en nyckel (vanligtvis betecknad N) för att extrahera dess två faktorer (vanligtvis betecknade P och Q) och (2) beräkning av den diskreta logaritmen som nycklarna är baserade på.
Säkerheten för dessa kryptosystem beror helt på svårigheten hos klassiska datorer att lösa dessa problem. Även om det är lätt att generera nycklar som kan kryptera och dekryptera data efter behag, är det praktiskt taget omöjligt för en motståndare att beräkna siffrorna som får dem att fungera.
Under 2019 faktoriserade ett team av forskare en 795-bitars RSA-nyckel, vilket gjorde den till den största nyckelstorleken som någonsin gissat. Samma lag beräknade också den diskreta logaritmen för en annan nyckel av samma storlek.
Forskarna uppskattade att summan av beräkningstiden för båda nya rekorden var cirka 4 000 kärnår med Intel Xeon Gold 6130-processorer (som körs på 2,1 GHz). Liksom de tidigare posterna uppnåddes dessa med en komplex algoritm som kallas Number Field Sieve, som kan användas för att utföra både heltalsfaktorisering och diskreta logaritmer med finita fält.
Kvantberäkning är fortfarande i experimentfasen, men resultaten har redan visat att den kan lösa samma matematiska problem direkt. Att öka storleken på nycklarna hjälper inte heller, eftersom Shors algoritmkvantberäkningsteknik utvecklad 1994 av den amerikanske matematikern Peter Shore fungerar storleksordningar snabbare för att lösa heltalsfaktorisering och diskreta logaritmiska problem.
Reklam
Forskare har vetat i årtionden att dessa algoritmer är sårbara och varnar världen att förbereda sig för den dag då all data som har krypterats med dem kan avkodas. Främst bland supportrarna är det amerikanska handelsdepartementets National Institute of Standards and Technology (NIST), som har kampanjat för postkvantkryptering (PQC).
På tisdagen sa NIST att de hade valt ut fyra kandidat-PQC-algoritmer för att ersätta de som förväntas störtas av kvantberäkningar. De är: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON och SPHINCS+.
CRYSTALS-Kyber och CRYSTALS-Dilithium är sannolikt de två mest använda ersättningarna. CRYSTALS-Kyber används för att upprätta digitala nycklar som två datorer som aldrig har interagerat med varandra kan använda för att kryptera data. De andra tre används under tiden för att digitalt signera krypterad data för att avgöra vem som skickade den.
“CRYSTALS-Kyber (nyckeletablering) och CRYSTALS-Dilithium (digitala signaturer) valdes ut för sin starka säkerhet och utmärkta prestanda, och NIST förväntar sig att de fungerar bra i de flesta applikationer”, skrev NIST-tjänstemän. “FALCON kommer också att standardiseras av NIST, eftersom det kan finnas användningsfall där CRYSTALS-Dilithium-signaturerna är för stora. SPHINCS+ kommer också att standardiseras för att undvika att förlita sig enbart på säkerheten för signaturnät. NIST söker offentlig feedback om en version av SPHINCS+ med ett lägre maximalt antal signaturer.”
De val som aviserats i dag kommer sannolikt att få en betydande inverkan i framtiden.
“NISTs val spelar verkligen roll eftersom många stora företag måste följa NISTs standarder, även om deras egna chefskrypteringsmakare inte håller med om deras val”, säger Graham Steele, VD för Cryptosense, ett företag som tillverkar programvara för kryptografihantering. “Men med det sagt tror jag personligen att deras val är baserade på sunda resonemang, med tanke på vad vi för närvarande vet om säkerheten för dessa olika matematiska problem och prestationsavvägningen.”
Nadia Henninger, docent i datavetenskap och teknik vid UC San Diego, höll med.
“De algoritmer som valts ut av NIST kommer att vara den de facto internationella standarden, med undantag för alla oväntade utvecklingar i sista minuten”, skrev hon i ett mejl. “Många företag har väntat med kvarnade andetag på att detta val ska tillkännages så att de kan genomföra det så snart som möjligt.”
Även om ingen vet exakt när kvantdatorer kommer att finnas tillgängliga, är det mycket brådskande att flytta till PQC så snart som möjligt. Många forskare säger att det är troligt att brottslingar och nationalstatsspioner spelar in stora mängder krypterad kommunikation och lagrar dem för den dag de kan dechiffreras.
