RSA

RSA on epäsymmetrinen julkisen avaimen salausalgoritmi, jota käytetään laajalti muun muassa elektronisessa kaupankäynnissä. Ron Rivest, Adi Shamir ja Len Adleman kuvasivat algoritmin vuonna 1977; menetelmän nimi tulee heidän sukunimiensä alkukirjaimista.

Englantilainen matemaatikko Clifford Cocks kuvasi vastaavan algoritmin jo vuonna 1973 brittiläisen tiedusteluelin GCHQ:n (Government Communications Headquarters) sisäisessä muistiossa. Työ julistettiin kuitenkin salaiseksi, eikä sitä paljastettu ennen vuotta 1997.

RSA:n turvallisuus perustuu olettamukseen, jonka mukaan erittäin suurien kokonaislukujen tekijöihinjako on vaikeaa.

MIT patentoi algoritmin 1983 Yhdysvalloissa. Patentti raukesi syyskuussa 2000. Patentti ei koskenut muita maita, koska algoritmi oli jo julkaistu ennen patenttihakemusta.

Toiminta

Avainten luonti

Oletetaan että Liisa haluaa lähettää Pekalle yksityisen viestin turvatonta reittiä pitkin. Hän toimii seuraavasti luodakseen julkisen avaimen ja yksityisen avaimen:

1. Valitse kaksi suurta alkulukua p ≠ q satunnaisesti ja toisistaan riippumatta. Laske N = p q.
2. Valitse kokonaisluku 1 < d < N jolle (p-1)(q-1) on suhteellinen alkuluku.
3. Laske e siten, että d e ≡ 1 (mod (p-1)(q-1)).
4. Tuhoa kaikki p:tä ja q:ta koskevat tiedot.

• (Kohdat 2 ja 3 voidaan suorittaa laajennetulla Eukleideen algoritmilla; ks. modulaariaritmetiikka.)

N ja e muodostavat julkisen avaimen ja N sekä d muodostavat yksityisen avaimen. Huomaa, että ainoastaan d on salainen ja että N on julkisesti saatavilla. Liisa lähettää julkisen avaimen Pekalle ja pitää yksityisen avaimen salaisena.

Viestin salaaminen

Sitten lasketaan c:

$c\; \backslash equiv\; n^e\backslash \; (\backslash mathrm\{mod\}\backslash \; N)$

Salauksen purkaminen

Liisa saa c:n Pekalta ja tietää salaisen avaimensa d. Hän voi palauttaa n:n c:stä seuraavan kaavan avulla:

$c^d\; \backslash equiv\; n\backslash \; (\backslash mathrm\{mod\}\backslash \; N)$

Liisa voi nyt selvittää muuttujan n, koska n < N. Hän voi palauttaa alkuperäisen viestin m, mikäli hän tuntee muuttujan n.

Purku toimii, koska

$c^d\; \backslash equiv\; n^\{e\; \backslash cdot\; d\}\backslash \; (\backslash mathrm\{mod\}\backslash \; N)$

ja ed ≡ 1 (mod p-1) ja ed ≡ 1 (mod q-1). Fermat'n pieni teoreema antaa

$n^\{e\; \backslash cdot\; d\}\; \backslash equiv\; n\backslash \; (\backslash mathrm\{mod\}\backslash \; p)$     ja     $n^\{e\; \backslash cdot\; d\}\; \backslash equiv\; n\backslash \; (\backslash mathrm\{mod\}\backslash \; q)$

jonka mukaan (koska p ja q ovat erisuuria alkulukuja)

$n^\{e\; \backslash cdot\; d\}\; \backslash equiv\; n\backslash \; (\backslash mathrm\{mod\}\backslash \; pq)$

Allekirjoittaminen

RSA:ta voidaan käyttää myös viestien allekirjoittamiseen. Tällöin viestistä lasketaan nk. tiiviste (engl. hash) tiivistefunktion (esim. MD5, SHA-1) avulla. Tiiviste kryptataan yksityisellä allekirjoitusavaimella. Kun viestin allekirjoitus sitten halutaan tarkastaa, puretaan tiivisteen salaus ja lasketaan viestistä uusi tiiviste. Jos uusi tiiviste on sama kuin viestin mukaan alun perin kryptattu tiiviste, viesti ei ole muuttunut matkalla, ja viesti on juuri siltä henkilöltä jolta se väittää olevansa. Katso myös digitaalinen allekirjoitus.

Algoritmit

RSA:n toteutus perustuu nopeaan potenssiinkorotusalgoritmiin jäännösluokkarenkaassa modulo $N$. Potenssiinkorotuksen toteuttamiseksi tarvitaan nopea kertolaskualgoritmi samassa renkaassa.

Järjestelmän avainten valinnassa tarvitaan isoja alkulukuja, jotka on mahdollisimman satunnaisesti valittu. Tätä varten tarvitaan nopeita ja luotettavia alkulukutestejä.

Turvallisuus

Oletetaan että Eeva sieppaa julkisen avaimen N ja e sekä salatekstin c.

Toistaiseksi ei ole todistettu, että N:n tekijöihinjako olisi ainoa tapa päätellä n c:n perusteella. Helpompaa menetelmää ei kuitenkaan ole toistaiseksi keksitty. Niinpä yleisesti oletetaan, ettei Eeva voi lukea viestiä, jos N on tarpeeksi suuri.

Peter Shor osoitti 1993 että kvanttitietokone voisi periaatteessa suorittaa tekijöihinjaon polynomisessa ajassa. Jos kvanttitietokoneista tulee käyttökelpoisia, Shorin algoritmi tekee RSA:sta vanhentunutta teknologiaa.

Kirjallisuutta

Singh, Simon 1999. Koodikirja : salakirjoituksen historia muinaisesta Egyptistä kvanttikryptografiaan. Helsinki: Tammi

Aiheesta muualla

• M. K. Sinisalon RSA-esitelmä (PowerPoint)