RSA-Algoritmen

Numer är RSA tillsammans med DES och md5 en känd krypteringsalgoritm. RSA används för så kallade PKI-krypton. PKI står för Public Key Infrastructure, dvs publika nycklar används. I RSA används en publik nyckel och en privat nyckel. Den publika nyckeln kan användas av alla som vill kryptera ett meddelande till en viss mottagare (fysisk eller juridisk person). Meddelandet kan dock endast dekrypteras med hjälp av den privata nyckeln.

Matematiken bakom RSA

Kryptoalgoritmer av samma typ som RSA hade länge stått högst upp på många myndigheters önskelistor. Med RSA löser man ett av de största historiska problemen inom kryptografin, hur utbytet av den hemliga kryptonyckeln ska ske på ett säkert sätt. För att detta skulle kunna bli verklighet måste man hitta så kallade matematiska envägsfunktioner, dvs en funktion som tar viss indata och lämnar utdata som inte kan användas för att återskapa den ursprungliga indatan med hjälp av funktionen. Man kan jämföra med funktionen y=x3. Vi matar in en klartext i form av ASCII-koden för tecknet A, nämligen talet 65 i funktionen. Vi får då y=653= 274625. 274625 motsvarar då kryptotexten i vårt fall. Tyvärr är det ganska lätt att återskapa klartexten med hjälp av samma funktion som genererat kryptot. Vi använder den så kallade inversa (omvända) funktionen, dvs x=y1/3 och då får vi x=2746251/3=65! Tänk dig alltså att man på något sätt kunde hitta en funktion som bara går åt "ena hållet"!

RSA-algoritmen är inte helt lätt att förstå utan studier i matematik på mer avancerad nivå. Däremot är du säket nyfiken på hur det hela fungerar så vi ger en liten översikt över algoritmen med ett exempel.

Två personer vill utväxla ett hemligt meddelande, vi kan kalla dem Alice och Bob.

Nyckelgenerering

  1. Alice, som vill kunna ta emot meddelanden från Bob, väljer slumpmässigt två stora primtal. Dessa primtal kallas p och q.
  2. Alice multiplicerar sina två stora primtal och kallar produkten för n. n ingår i både den publika och den privata nyckeln.
  3. Alice väljer ett heltal e sådant att e och produkten (p-1)(q-1) är relativt prima, dvs den största gemensamma delaren är 1. Dessutom måste det gälla att 1<e<(p-1)(q-1).
    1. e väljer Alice att göra publikt som sin så kallade publika nyckel.
  4. Till sist beräknar Alice ett tal d sådant att de=1+k((p-1)(q-1)) där k är ett heltal.
    1. d måste Alice hålla hemligt, det är hennes så kallade privata nyckel.

Kryptering

Alice har nu sin privata och publika nyckel genererad och klar.

  1. Bob tar del av hennes publika nyckel, talen n och e.
  2. Bob omvandlar först bokstäverna eller tecknen i sitt meddelande till siffror enligt någon bestämd metod. Man kan t ex tänka sig att använda ASCII-koderna för tecknen. Siffersekvensen kallas för m.
  3. Meddelandet krypteras nu av Bob genom beräkningen c = me mod n, där c står för engelskans ciphertext, chiffer- eller kryptotext.
  4. Bob skickar det krypterade meddelandet till Alice.

Dekryptering

  1. Alice tar emot meddelandet och dekrypterar det genom att göra beräkningen m = cd mod n