RSA


RSA (en förkortning av skaparnas namn: Rivest, Shamir and Adleman Algorithm) är det publika nyckelsystem som är spritt i någon större omfattning. RSA är ett så kallat blockchiffersystem i vilken originaltexten och den chiffrerade texten är heltal mellan 0 och n-1 för något n. Kryptering och dekryptering sker på följande sätt för någon originaltext M och chiffrerad text C (e står för encryption och d står för decryption):
C= Me mod n
M= Cd mod n= (Me)d mod n= Med mod n 

Både sändaren och mottagaren måste veta värdet på n. Sändaren vet värdet på e och bara mottagaren vet värdet på d. Det innebär att detta är ett publikt nyckelkrypteringsalgoritm med den publika nyckeln KU= {e,n} och en privat nyckel KR= {d,n}. För att denna algoritm ska fungera som en publik nyckelkryptering måste följande krav vara uppfyllda:
1. Det är möjligt att hitta värden på e, d och n så att för alla M<n så är Med mod n= M.
2. Det ska vara relativt enkelt att räkna ut Me och Cd för alla värden på M<n.
3. Det är omöjligt att bestämma d om man har e och n

De första två punkterna gäller för RSA och det är bara den tredje punkten som är lite tveksam. Detta krav gäller dock om man väljer tillräckligt stora värden på e och n.

Princip för att kunna välja n och båda nycklarna:
n= a*b (a och b ska vara primtal)
g= (a-1)*(b-1) (g är ett tal som vi kommer att använda för att begränsa val av publika nyckeln)

Nu är det dags att välja publika nyckeln (e), följande är begränsningar för valet:

  1. Publika nyckel måste vara ett primtal.
  2. Talet g får inte vara delbart med primtalet.
När vi har valt publika nyckeln (e) då är det dags att beräkna privata nyckeln(d):
följande formel ska gälla för de valda nycklarna:
(d*e) mod  g = 1

Vi tar ett exampel:
primtal={2,3,5,7,11,13,17,19,23,29,...}

    1. Välj talet n:
      n är multipel av a och b då a  och b är båda ett primtal (i praktiken väljer man a och b jätte
      jätte stor så att det tar lång tid att kunna räkna fram n för att kunna försöka knäcka koden)
      vi väljer 3 och 13 för att det ska vara lätt att förstå
    2. beräkna g: g=(a-1)*(b-1)=(3-1)*(13-1)=2*12=24
    3. Val av publika nyckeln (e):
      e är alltså ett primtal som g (24 i det här fallet) inte är delbart med . Talet 5 passar bra, så e=5.
    4. Beräkna privata nyckeln d, följande förmel ska gälla:
      (d*e) mod g = 1
      alltså (d*5) mod 24=1 för , det syns att 29 passar så bra, för att 29*5=145
      145 mod 24 = 1
Anta nu att person A vill skicka ett tal t.ex 20 till person B (person B har publik nyckel 5 enligt ovan)
 A krypterar talet 20 med publika nyckeln 5, alltså:
C=Me mod n= 205 mod 39= (202 202 201) mod 39= (202 mod 39)*(202 mod 39)*(201 mod 39)=
(400 mod 39)*(400 mod 39)*20=10*10*20=2000
2000 är fortfarande större än 39 då kan vi fortsätta på samma sätt:

C=2000 mod39= ((10*10) mod 39)* (20 mod 39)= 100 mod 39* 20=22*20=440 >39
då fortsätter vi:
C=440 mod 39=11

alltså det krypterade talet är 11.

så A skickar 11 till B.
Nu har B fått 11, då är det dags att dekryptera det med sin privata nyckel( som är hemlig och det var 29).
M= Cd mod n= 1129 mod 39=(112)14  *11 mod 39= (112 mod 39)14 *11
=(121 mod 39)14 * 11= 414*11= (43)4 * 42*11=(64 mod39)4* 16*11=254*176=
(625 mod 39)*(625 mod 39) *(176 mod 39)=1*1*20=20
vad var det A ville skicka?