RSA
Från Rilpedia
- RSA är även beteckning för Sydafrika (Republic of South Africa).
- RSA är även beteckning för The Royal Society for the encouragement of Arts.
- RSA är även beteckning för försäkringsbolaget RSA, tidigare Royal & Sun Alliance
- RSA är även beteckning för IBM Rational Software Architect IBM Rational Software Architect
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.
Innehåll |
Beskrivning av algoritmen
RSA använder två nycklar, en publik nyckel och en privat nyckel. Den publika nyckeln används för att kryptera meddelandet. Meddelandet kan sedan bara dekrypteras med hjälp av den privata nyckeln. Den som ska ta emot ett meddelande bestämmer både den publika och den privata nyckeln och gör sedan den publika känd för alla som ska kunna skicka meddelanden, men behåller kunskapen om den privata nyckeln för sig själv. De nycklar som används av RSA är stora heltal.
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
- Välj först slumpmässigt två olika mycket stora primtal, p och q .
- Multiplicera därefter p och q och kalla produkten n.
- 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) .
- 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.
Kryptering
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
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 restsatsen att
- xed ≡ x (mod pq)
D.v.s
- xed ≡ x (mod n)
eller
- x = xed mod n = yd mod n
Signering
Om avsändaren av ett meddelande vill kunna bevisa att han verkligen är den som sänt meddelandet, 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 privata 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.
Ett "praktiskt" exempel
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 två siffror.
