768-bitars RSA-nyckel faktoriserad

Bruce Schneier har en kort notis i sitt senaste nyhetsbrev, Crypto-Gram, om att en grupp forskare lyckats faktorisera en 768-bitars RSA-nyckel. Med hjälp av en distribuerad datorkraft bestående av hundratals processorer som arbetade i knappt tre år lyckades man visa att heltalet:

12301866845301177551304949583849627207728535695953347921973224521517

26400507263657518745202199786469389956474942774063845925192557326303

45373154826850791702612214291346167042921431160222124047927473779408

0665351419597459856902143413

är en produkt av primtalen

33478071698956898786044169848212690817704794983713768568912431388982

883793878002287614711652531743087737814467999489

och

36746043666799590428244633799627952632279158164343087642676032283815

739666511279233373417143396810270092798736308917

Skrivet på ett mer abstrakt algebraiskt vis så består en RSA-nyckel av ett heltal, N, som är en produkt av två primtal, P och Q, dvs N = P*Q. Det går relativt snabbt att skapa en RSA-nyckel genom att slumpa fram två primtal och multiplicera dem för att bilda N, som är den publika nyckeln som man kan sprida till alla sina kontakter, gärna i form av ett certifikat. Den privata RSA-nyckeln, som det gäller att hålla hemlig (exempelvis genom att lagra den på ett smart kort) består av de två primtalen P och Q. För att forcera en publik RSA-nyckel kan man alltså försöka "dela upp" N i sina beståndsdelar P och Q. Denna process kallas faktorisering och det är alltså vad forskarna har lyckats med för ett heltal i storleksordningen 2768, vilket motsvarar 232 decimala siffror (kontrollräkna gärna på heltalet ovan den som orkar). Ju större heltal (dvs ju fler bitar eller siffror som ingår i heltalet), desto längre tid tar det att faktorisera det. Därför måste RSA-nycklar bestå av heltal med tusentals bitar (motsvarande över 300 decimala siffror).

Bruce's blogginlägg om detta citerar ordagrant från forskarnas artikel:

(På svenska:) "Eftersom det är tio år sedan en 512-bitars RSA-nyckel först faktoriserades är det inte otroligt att 1024-bitars RSA-nycklar kommer att kunna faktoriseras inom det närmsta decenniet". Således rekommenderar forskarna att "det skulle vara klokt att fasa 1024-bitars RSA nycklar inom de närmaste 3-4 åren".

Det är naturligt att man måste bevaka utvecklingen inom kryptoanalys och ständigt öka nyckellängden för att hålla en rimlig säkerhetsnivå. Redan idag rekommenderas exempelvis att nyckellängden för utfärdare av certifikat (CA) bör vara minst 2048 bitar.

Betyder då det här att man snarast måste ersätta alla 1024-bitars nycklar?

Nja, det är lite vanskligt att resonera om riskerna för 1024-bitars nycklar givet att man lyckats faktorisera en 768-bitars nyckel. Först och främst bör man tänka på att för varje (slumpad) bit som man lägger till nyckellängden så fördubblas svårigheten att forcera den. Nu är i och för sig detta inte helt sant. Den snabbaste faktoriseringsalgoritmen man känner till (GNFS) är något snabbare än exponentiell tid.

Det kan vara upplysande att fundera på vad vi skulle göra idag om vi hade RSA-nycklar på 768 bitar. Fortfarande är det ju så att en lyckad forcering tycks kräva ett par års arbete av ett hundratal processorer som är sammankopplade i ett nätverk. Det ger lite respit. Risken är att någon bestämmer sig för att attackera just vår nyckel och sedan ser till att skaffa fram den nödvändiga utrustningen i form av processorer och programvara (GNFS är en extremt komplicerad algoritm). Även om alla dessa villkor är uppfyllda lär det ändå dröja ett par år innan vår nyckel blivit röjd.

Notera att om vi endast använder vår 768-bitarsnyckel för att legitimera oss och logga in i datorsystem så kan vi skydda oss genom att helt enkelt byta nyckel en gång per år.

Vilken risk löper vi då om vi använder 768-bitarsnyckeln för elektroniska underskrifter? Tja, så länge vi ser till att tidsstämpla de elektroniskt undertecknade dokumenten (naturligtvis med en nyckel som innehåller fler bitar) så kan vi faktiskt även hantera den situationen. Vi bör även i detta fall se till att byta nycklar en gång per år. Om vi inte tidsstämplar dokumenten kan vi dock få problem. Man vill ju i regel att en elektronisk underskrift ska vara giltig under en längre tid och i det här fallet går det inte att garantera.

Det största problemet uppstår dock om vi vill använda vår 768-bitarsnyckel för att kryptera känslig information. Efter ett par år kan vi inte längre vara säkra på att den krypterade informationen fortfarande är hemlig. Någon kan ha röjt vår nyckel och dekrypterat informationen. Mot bakgrund av detta rekommenderar jag att RSA-nycklar som ska användas för kryptering bör vara mer än 1024 bitar långa.

Kanske börjar det ändå snart vara dags att på allvar börja överväga att införa nycklar baserade på elliptiska kurvor (ECC = Elliptic Curve Cryptography) i stället för att bara öka nyckellängden för RSA-nycklarna.

Jag brukar annars sällan rekommendera användning av baserade på elliptiska kurvor av den enkla anledningen att det är för få system som stödjer det ännu. I regel vill man ju ha en lösning som fungerar mellan så många system och användare som möjligt och då är RSA fortfarande helt överlägset. Med elliptiska kurvor kan man emellertid erhålla en högre säkerhetsnivå med kortare nycklar. En ECC-nyckel på 160 bitar sägs vara ungefär lika svårforcerad som en RSA-nyckel på 1024 bitar. Även 160 bitar är dock för mycket för en människa att hålla i huvudet (i Base64 skulle det bli 27 tecken) så det är förmodligen inte en tillräckligt stor vinst att gå över till ECC bara för att minska nyckelländen.


 

Jag tänkte avsluta med en liten anekdot om faktorisering, där både Bruce Schneier och Simon Singh, en av mina favoritförfattare när det gäller populärvetenskap, figurerar.

Simon Singh gjorde succé med den osannolika bestsellern Fermats gåta, som handlar om hur matematikern Andrew Wiles 1995 lyckades bevisa Fermats stora sats. Uppföljaren, som kom ut 1999, var en bok om kryptografins historia som lite fyndigt döptes till Kodboken. Norstedts förlag anordnade ett seminarium med Simon Singh i samband med lanseringen av Kodboken på svenska. Vi var väl ett tjugotal åhörare som hade bänkat oss för att få oss till livs en intressant exposé om kampen mellan kodskapare och kodknäckare alltsedan Maria Stuarts 1500-tal fram till dagens moderna kvantkrypteringsmetoder.

Nu visade det sig att en av åhörarna som dök upp var ingen mindre än Bruce Schneier himself, med både skägg och kryptopiska precis som man tänker sig honom. Schneier var i Stockholm i ett helt annat ärende, vill minnas att han skulle tala vid något större seminarium senare på helgen, och hade en eftermiddag att slå ihjäl. Så i stället för att sitta på hotellrummet och häcka valde han att gå och lyssna på när Simon Singh la ut texten om kryptografins historia.

Bruce Schneier är en erkänt skicklig kodskapare, i synnerhet när det gäller symmetriska chiffer (bl.a. Blowfish och Twofish). Mest känd är han dock kanske som en slags journalist inom krypto och säkerhet. Efter 11 september 2001 har han mest fått uttala sig om flygplatssäkerhet, terrorism och liknande, med skarpsinniga och sansade åsikter som så väl behövs i USA idag.

Simon Singh å andra sidan doktorerade i partikelfysik innan han började på BBC som vetenskapsreporter. Som kryptolog är han dock väldigt okänd (vilket emellertid inte hindrar honom från att skriva en bra bok om kryptografins historia).

Hur som helst, det märktes på Simon att han blev rätt nervös när han upptäckte att Bruce Schneier satt i publiken. Det är väl ungefär som att föreläsa om kosmologi för, tja, Stephen Hawking. I alla fall nästan. Bruce höll dock en relativt låg profil och gjorde bara ett par inlägg på direkt uppmaning av Simon. Jag minns dock ingenting av vad det var han sa men det var säkert något vettigt.

Vad har då detta med faktorisering att göra? Jo, längst bak i Kodboken hade Simon Singh lagt in en utmaning (Crypto Challenge) i form av tio krypterade meddelanden som man skulle forcera. Simon Singh tillkännagav att den första som lyckades lösa alla chiffer skulle vinna ett pris på 10 000 pund. Problemen var ordnade i svårighetsgrad där de första kunde lösas med papper och penna. Det tionde och sista chiffret var krypterat med en 512-bitars RSA-nyckel.

Simon Singh hade nog tänkt att det skulle bli en nöt som skulle hålla läsekretsen sysselsatt ett bra tag. Faktorisering av 512-bitars RSA-nycklar var det yttersta frontlinjen vid denna tid. Redan efter ett år och en månad lyckades dock ett svenskt lag, mestadels bestående av doktorander vid KTH, presentera lösningar på alla tio uppgifter. Läs den om den rafflande historien på Simon Singhs egen websida eller vinnarlagets egen berättelse!

0 kommentarer :: 768-bitars RSA-nyckel faktoriserad

Skicka en kommentar