RSA

Från Wikipedia
Hoppa till: navigering, sök
Denna artikel handlar om krypteringsalgoritmen RSA. Se även RSA (olika betydelser).

RSA-krypteringen är en av de mest kända krypteringsalgoritmerna. Det var den första allmänt beskrivna algoritmen som använder så kallad asymmetrisk kryptering. Detta innebär att man använder en nyckel för att kryptera ett meddelande och en annan för att dekryptera det. Denna egenskap gör den också användbar för att signera ett meddelande så att mottagaren garanterat vet vem som är avsändaren. Beteckningen RSA är bildat av begynnelsebokstäverna i namnen på upphovsmännen Ron Rivest, Adi Shamir och Len Adleman som beskrev den 1977. Avslöjanden har visat att amerikanska NSA betalat de ursprungliga skaparna att göra standardprogrammeringen (BESAFE/FIPS/NIST) svagare och långsammare (dubbelelliptisk) i sin kryptering.[1]

Beskrivning av algoritmen[redigera | redigera wikitext]

RSA använder två nycklar, en offentlig nyckel och en hemlig nyckel. (På engelska heter den hemliga nyckeln "private key" vilket inte är detsamma som det svenska "privat"). Den publika nyckeln används för att kryptera meddelandet. Meddelandet kan sedan bara dekrypteras med hjälp av den hemliga nyckeln. Den som ska ta emot ett meddelande bestämmer både den offentliga och den hemliga nyckeln och gör sedan den förstnämnda känd för alla som ska kunna skicka meddelanden, men behåller den hemliga nyckeln för sig själv. De nycklar som används av RSA är mycket stora primtal.

Generering av nycklarna[redigera | redigera wikitext]

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 stora primtal, p och q .
  2. Multiplicera därefter p och q och kalla produkten för 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 offentliga nyckeln består av talen e och n och den hemliga nyckeln av talen n och d.

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.

Kryptering[redigera | redigera wikitext]

Den som vill sända ett meddelande omformar detta till ett tal x < n, eller en följd av sådana tal. Detta sker med en i förväg överenskommen reversibel algoritm. För varje x beräknas talet y

y = xe mod n

Talet y eller följden av sådana tal är det krypterade meddelandet.

Dekryptering[redigera | redigera wikitext]

För varje mottaget tal y kan det ursprungliga talet x beräknas med

x = yd mod n

och därefter kan det ursprungliga meddelandet återskapas. Att så är fallet följer av följande matematiska resonemang

yd mod n = (xe mod n)d mod n = (xe)d mod n = xed mod n

Eftersom ed ≡ 1 (mod (p-1)(q-1)) så gäller också

ed ≡ 1 (mod p-1)

och

ed ≡ 1 (mod q-1)

och av Fermats lilla sats följer då

xed ≡ x (mod p)

och

xed ≡ x (mod q)

Eftersom p och q är olika primtal, får man genom att tillämpa Kinesiska restklassatsen att

xed ≡ x (mod pq)

D.v.s

xed ≡ x (mod n)

eller

x = xed mod n = yd mod n

Signering[redigera | redigera wikitext]

Om avsändaren av ett meddelande vill kunna bevisa att han verkligen är den som sänt meddelandet, och samtidigt garantera att meddelandet inte kan ha ändrats på vägen, kan han använda RSA för att signera sitt meddelande. Detta går till på följande sätt.

Först beräknas ett hashvärde h av meddelandet där 0 < h < n. Detta görs med någon överenskommen algoritm, och hashvärdet krypteras sedan med avsändarens hemliga nyckel:

s = hd mod n

Det krypterade hashvärdet sänds sedan som en signatur tillsammans med meddelandet till mottagaren. Mottagaren kan verifiera att avsändaren är den han utger sig vara, genom att dekrypera signaturen s med avsändarens publika nyckel:

h = se mod n

Mottagaren kontrollerar sedan den dekrypterade signaturen genom att själv beräkna hashvärdet från det mottagna meddelandet och jämföra det med den dekrypterade signaturen. Om värdena överensstämmer vet mottagaren att endast den angivna avsändaren kan ha producerat meddelandet.

Förhållande med NSA[redigera | redigera wikitext]

RSA: s relation med NSA förändrats under åren. Reuters Joseph Menn, liksom cyber analytiker Jeffrey Carr, har noterat att de två en gång hade ett motsägande förhållande. I företagets tidiga år, RSA och dess ledare var framstående förespråkare för stark kryptografi för allmänheten, medan NSA och Bush och Clinton administrationer försökte förhindra dess spridning.

I mitten av 1990-talet, RSA och Bidzos ledde en offentlig kampanj mot Clipper Chip, en krypteringschip med en bakdörr för att låta den amerikanska regeringen för att dekryptera meddelanden. Clintonadministrationen pressade telekomföretag att använda chip i sina enheter, och avslappnad exportrestriktioner för varor som använt det. Sådana begränsningar hade förhindrat RSA Security sälja sin mjukvara utomlands.

Förhållandet skiftade från kontradiktoriska till kooperativ efter Bidzos avgick som vd under 1999, enligt Victor Chan, som ledde RSA: s tekniska avdelning fram till 2005: "När jag gick var det 10 personer i labbet, och vi kämpade NSA Det blev. ett helt annat bolag senare. "Till exempel var RSA rapporterades ha accept $ 10.000.000 från NSA under 2004 i en affär för att använda NSA-designade Dual_EC_DRBG slumpgenerator i deras BSAFE bibliotek, trots många tecken på att Dual_EC_DRBG var både av dålig kvalitet och eventuellt backdoored. RSA Security släppas senare ett uttalande om Dual_EC_DRBG bakdörr:

Vi tog beslutet att använda Dual EG DRBG som standard i BSAFE verktygslådor under 2004, inom ramen för en branschgemensam satsning för att utveckla nya, starkare metoder för kryptering. På den tiden, NSA hade en betrodd roll i samhället omfattande insats för att stärka, inte försvaga, kryptering. Denna algoritm är bara ett av flera alternativ som finns tillgängliga inom BSAFE verktygslådor, och användare har alltid varit fria att välja vilken som bäst passar deras behov. Vi fortsatte med algoritmen som ett alternativ inom BSAFE verktygslådor som vunnit acceptans som en NIST-standarden och på grund av sitt värde i FIPS efterlevnad. När oro dök runt algoritmen under 2007 fortsatte vi att lita på NIST som skiljedomare i den diskussionen. När NIST utfärdat nya riktlinjer rekommenderar inte längre har användning av denna algoritm i september 2013 följs vi till denna vägledning, denna rekommendation till kunder och diskuterade förändringen öppet i media. -RSA, Säkerhetsdivisionen inom EMC[2]

Ett "smidigt" exempel[redigera | redigera wikitext]

Primtalen 1 249 och 1 049 ger n = 1 310 201. Vi väljer e = 1 013 varpå d = 843 101. Själva uträknandet av d görs genom en diofantisk ekvation, 1 013d - (p-1)(q-1)k = 1, men det är bara detaljer.

Har vi ett meddelande x, som lyder 444 807 och som vi vill kryptera görs detta genom att räkna ut xe (mod n), alltså 444 8071 013 (mod 1 310 201). Det krypterade meddelandet blir då 503 328.

Dekryptering av ovanstående meddelande y görs genom yd (mod n), alltså 503 328843 101 (mod 1 310 201). Självklart blir detta 444 807, som var vårt ursprungliga meddelande.

Meddelandet 444807 kan i realiteten betyda vad som helst. Det skulle kunna representera bokstäver i en mening; meningar representerade till siffror brukar dock kräva större tal än detta i och med att varje bokstav brukar representeras av minst två siffror.

Referenser[redigera | redigera wikitext]

Noter[redigera | redigera wikitext]

  1. ^ Reuters
  2. ^ RSA Säkerhet