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?