Slutet för PKI?

Publicerat: 1 april 2011 i Uncategorized

image

En fd lärare till mig på Universitetet i Karlstad, Jens Jidbom, som numera forskar inom IT-säkerhet, har utvecklat en algoritm som i 0,013% av försöken lyckats heltalsfaktorisera stora primtal. Jaha, tänker du, vad har detta med ”slutet för PKI” att göra då?

Jo, PKI står för Public Key Infrastructure, dvs det en infrastruktur som hanterar certifikat som bygger på publika och privata nycklar. Den publika nyckel sprider du fritt, och den privata ska bara du ha tillgång till. Detta möjliggör pålitlig kryptering och signering.

Nycklarna bygger på extremt stora primtal, så stora att det krävs 1024, 2048 eller 4096 bitar att representera dom. Vi snackar alltså stoooora tal med flera hundra siffror I sig. Nycklarna har en relation till varandra. Klippt från Wikipedia-artiklen om krypteringsalgoritmen RSA:

Generering av nycklarna

För att ta fram nycklarna som behövs för att använda RSA-algoritmen görs följande beräkningssteg

  1. Välj först slumpmässigt två olika mycket stora primtal, p och q .
  2. Multiplicera därefter p och q och kalla produkten n.
  3. Välj sedan ett annat heltal, e så att e och (p-1)(q-1) är relativt prima och 1 < e < (p-1)(q-1) .
  4. Beräkna slutligen ett heltal d sådant att ed ≡ 1 (mod (p-1)(q-1)).

Den publika nyckeln består av talen e och n och den privata nyckeln av talen d och n.

Finessen är att även om e och n är kända, går det inte att räkna ut de båda primfaktorerna p och q, inom rimlig tid, eftersom det inte finns någon effektiv algoritm för primtalsfaktorisering. Därmed kan man inte heller räkna ut d. Endast den rätte mottagaren känner till p, q och d och kan därmed avkoda meddelandet.

Jens har alltså trots allt lyckats hitta en “effektiv algoritm för primtals-faktorisering”. Nåja, effektiv kanske den inte är, men den finns och funkar ibland.

Även om han “bara” lyckas i 0,013% av fallen och även att det tar flera dagar när man lyckas så kan man nu inte längre räkna med att ett certifkat är giltigt.

Notera att det inte spelar någon roll hur hög assurans certifikatet har, dvs hur noggrann kontroll som gjordes att certifikatet verkligen gavs ut till rätt person samt hur noga man har skyddat de privata nycklarna. Har jag tur kan jag alltså räkna ut den privata nyckeln till http://www.valfribank.se eller skapa ett giltigt certifikat som får ansluta till vpn.valfrittföretag.com.

Jag var självklart skeptisk till det, så jag skickade 50 test-certifikat till honom tillsammans igår med signerade dokument och imorse ringde han mig och läste upp den privata nyckeln till ett av certifikaten. Jag trodde jag skulle svimma.

Resultatet måste genomgå en s k peer review innan det presenteras, där andra insatta forskare verifierar att resultatet är korrekt. Men jag har ju fått det bevisat att det funkar, så jag är övertygad.

Ska bli spännande att se hur detta påverkar branchen, allt från SSL, kortbetalningar och kryptering av data bygger ju på antagandet att man inte kan heltalsfaktorisera primtal.

Innebär detta att det är dags att byta karriär? Nä, men däremot kommer det inebära att man måste påskynda införandet av certifikat som bygger på eliptiska kurvor. Tekniken finns, men är inte spridd än.

Annonser
kommentarer
  1. Tom Aafloen skriver:

    April april!
    Som ni alla förstår var detta bara ett aprilskämt. ATT någon har lyckats är alltså ett skämt, allt annat i inlägget stämmer.

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s