RSA är en mycket vanlig krypteringsmetod. Den anses vara en av de säkrare metoderna och därför använder bl.a. Ålandsbanken denna metod för att kryptering vid inloggning till nätbanken. RSA är dock en ganska långsam krypteringsmetod och den används därför sällan för att kryptera användardata, utan används mest för att skicka krypterade nycklar säkert. Krypteringsmetoden fick sitt namn efter upphovsmännens initialer, Rivest, Shamir och Adleman. RSA grundar sig på att om vi har två väldigt stora primtal så är det enkelt att multiplicera dem, men om man inte vet något annat än produkten är det svårt att faktorisera talet.
Varje användare av systemet väljer själv två stycken primtal p och q. Ju större primtal desto säkrare blir krypteringen. I praktiken används ca 100-siffriga primtal för att göra krypteringen säker. Med våra primtal gör vi två nya beräkningar
n = pq och m = (p - 1)(q - 1)
Ex.
Vi väljer p = 3 och q = 5. Med dessa tal gör vi våra beräkningar.
n = 3 × 5 = 15 och m = (3 - 1) × (5 - 1) = 2 × 4 = 8.
Efter att vi gjort våra beräkningar väljer vi två tal till e och d. För dessa tal ska det gälla att 1 < e, d < m och ed ≡ 1 (mod m).
Ex.
Vi fortsätter på vårt tidigare exempel. Vi väljer e och d så att kraven uppfylls. e = 3 och d = 3. I vanliga fall väljer man två olika tal, men eftersom vi valt så små primtal har vi inte den möjligheten nu.
1 < e, d < m vilket ger oss 1 < 3, 3 < 8 krav 1 uppfyllt.
ed = 3 × 3 = 9 vilket ger oss 9 ≡ 1 (mod 8) krav 2 uppfyllt.
I RSA har vi alltid två så kallade nycklar för att kunna dekryptera meddelandet. En offentlig nyckel och hemlig nyckel. Efter alla våra uträkningar så har vi variabler vi behöver för våra nycklar. Den hemliga nyckeln, som man kan lista ut från namnet, hålls hemlig för omvärlden består av (p, q, m, d). Den offentliga nyckeln, som vem som helst kan se består av (e, n).
Hittills har vi samlat ihop variabler vi behöver för kryptering och först nu kan vi börja kryptera. Ganska ofta vill man kryptera bokstäver, men för att kunna göra det måste man förvandla bokstaven till en siffra först, te.x genom att låta bokstaven representera en siffra så som i kapitlet med Caesarchiffret. Vi kommer inte gå genom varför krypterings och dekrypterings formlerna fungerar, utan endast kolla hur man använder dem. Vi börjar med att kryptera ett tal w som måste uppfylla kravet 1 ≤ w ≤ n, vi kan alltså inte kryptera ett tal större än vårt beräknade n. Krypteringsalgoritmen är följande:
x ≡ we (mod n), där x representerar den enkrypterade siffran w.
Ex.
Vi fortsätter igen med de exempel vi haft tidigare. Vi väljer ett w som uppfyller kravet, w = 2. Efter detta krypterar vi talet.
x ≡ we (mod n)
x ≡ 23 (mod 15)
x ≡ 8 (mod 15), vi kan nu välja vilket x som helst som är kongruent med 8 (mod 15).
x = 23. 23 är nu det enkrypterade talet för w.
För att dekryptera meddelandet använder man en formel som ser ut så här:
y ≡ xd (mod n).
Ex.
Använder som vanligt samma tal som i tidigare exempel.
y ≡ xd (mod n)
y ≡ 233 (mod 15)
y ≡ 12167 (mod 15) vi dividerar 12167 med 15 och får resten 2.
y ≡ 2 (mod 15) eftersom att vi vet att 1 ≤ w ≤ n så vet vi att 2 är talet vi söker efter.
y = 2 = w.
1. Försök hitta program eller hemsidor som använder sig av RSA kryptering.
2. Beräkna de hemliga och offentliga nycklarna när du har valt p = 13 och q = 7. Talen e och d får du välja själv.
3. Antag att du som deltagare i ett RSA-system har offentlig krypteringsnyckel n = 35 och e = 7.
(a) Kryptera meddelandena 6, 10 och 17.
(b) Dekryptera de chiffrerade meddelandena 3 och 8
4. Visa att om för ett RSA-system talet p är känt (utöver n och e), så kan talet d lätt beräknas.