RSA kryptering er igen blevet brudt, denne gang er det 768-bit nøglerne.
Endnu en brik I RSA's kryptering er væltet, med meldingen om at kryptografer har brudt 768-bit nøgler med en almindelig brugt "Public Key Algoritme". Gennembruddet fordrer at virksomheder tager kritisk stilling til brugen af mindre nøgler, da de ofte fortsat vil blive anvendt til mange forskellige formål, i særdeleshed på mindre enheder, der ikke har processorkraft til at håndtere større nøgler.
Et internationalt hold af matematikere, it eksperter og kryptografer, har brudt nøglen med NFS - Number Field Sieve - der tillod dem at udlede to primtal, der når de blev ganget med hinanden, skabte et tal på 768 bit. Opdagelsen, som tog omkring to og et halvt år, og hundredvis af standard computere, betyder at man ikke længere kan stole på 768-bit RSA nøgler til kryptering eller godkendelse af følsom kommunikation.
Forudsat at der er en slags gennembrud i NFS eller anden form for matematisk formel - vil der måske kun være et årti indtil at den næststørste RSA nøgle på 1024 bit, på samme måde er brudt.
"Det er en vigtig milepæl," sagde Benjamin Jun, Vice President for teknologi fra sikkerhedsfirmaet Cryptography Research. "Der er ubestridelige beviser på, at 768-bit nøgle ikke er nok. Det er en ret interessant måde at lukke et årti."
Holdet formåede at lave det 232-cifret tal, som RSA holdt ud som en repræsentant for 768-bit nøglen. De tilbragte et halvt år med 80 processorer til udregning af ligninger med en eller flere ubekendte faktorer bygget over polynomiske metodikker. Sorteringen tog næsten to år og blev udført på "mange hundrede maskiner". Til interesserede læsere kan det nævnes at sorteringen ved hjælp af en single-core 2.2GHz AMD Opteron med 2 GB RAM, ville have taget omkring 1.500 år.
At bryde den 768-bit nøgle var "flere tusinde gange hårdere" end at bryde en 512-bit nøgle, et resultat der blev opnået i 1999. Derimod vil det, at bryde en 1024-bit krypteret RSA nøgle, være omkring 1.000 gange hårdere end den seneste milepæl.
Hvis forskerne er optimistiske, mener de at det kan være muligt at bryde en 1024-bit RSA nøgle inden for de næste ti år ved hjælp af en akademisk indsats og værktøjer i samme begrænsede omfang, som var til rådighed ved bruddet af 768 nøglen. "Fra et praktisk sikkerhedsmæssigt synspunkt er dette ikke en "big deal", da krypteringsstandarderne anbefaler at udfase 768 bit nøglerne ved udgangen af 2010."
Men Nate Lawson, en kryptograf, og chef for sikkerhedsfirmaet Root Labs, mener at mindre nøgler ofte fortsat vil blive anvendt til mange forskellige formål, i særdeleshed på mindre enheder, der ikke har processorkraft til at håndtere større nøgler.
Forskerholdet omfatter Thorsten Kleinjung, Arjen K. Lenstra, Joppe W. Bos og Dag Arne Osvik af EPFL IC LACAL, i Lausanne, Schweiz; Kazumaro Aoki af NTT, i Tokyo, Jens Franke fra University of Bonn's Institut for Matematik, Emmanuel Thomé, Pierrick Gaudry, Alexander Kruppa og og Paul Zimmermann i Frankrig, og Peter L Montgomery, Herman te Riele Andrey Timofeev af Microsoft. En kopi af rapporten er her (pdf).
