RSA

RSA on julkisen avaimen salausalgoritmi, jota käytetään laajalti muun muassa elektronisessa kaupankäynnissä. Algoritmin kehittivät Ron Rivest, Adi Shamir ja Len Adleman vuonna 1977. Menetelmän nimi tulee heidän sukunimiensä alkukirjaimista.

Tämä artikkeli käsittelee salausalgoritmia. Lisää merkityksiä täsmennyssivulla.

RSA Securityn valmistama laite, joka tuottaa valtuutusavaimia. Laitteen algoritmi tuottaa vaihtuvan salasanan 60 sekunnin välein. RSA SecurID toimii siten, että kirjautumiseen tarvitaan käyttäjätunnus ja pääsykoodi, joka koostuu käyttäjän salasanasta (esimerkiksi 1234) ja laitteen näyttämästä koodista (esimerkiksi 567890), jolloin pääsykoodi on 1234567890.

RSA:n kuvaus julkaistiin vuonna 1978 Communications of the ACM -julkaisussa. Julkaisussa kehitystyön mainittiin alkaneen Diffie-Hellman -avaintenvaihtoa kuvaavasta artikkelista New Directions in Cryptography.^[1] RSA oli ensimmäinen käytäntöön soveltuva julkisen avaimen salaus. RSA:n turvallisuus perustuu olettamukseen, että erittäin suurien alkulukujen (jaollinen vain itsellään) tulon tekijöihinjako on vaikeaa.^[2] Kyseessä on yksisuuntainen modulaari funktio, joka on helppo laskea mutta todella hankalaa ja aikaa vievää laskea taaksepäin.

MIT sai Yhdysvalloissa RSA:ta koskevan patentin vuonna 1983.^[3] Patentti raukesi syyskuussa 2000.^[3] Patentti ei koskenut muita maita, koska algoritmi oli jo julkaistu ennen patenttihakemusta.

RSA perustuu julkiseen ja yksityiseen avaimeen ja siihen, ettei yksityistä avainta voida nykytekniikalla käytännössä johtaa julkisesta avaimesta. Julkisen avaimen avulla voidaan luoda salattuja viestejä, jotka voidaan lukea ainoastaan yksityisen avaimen avulla. Näin taho, joka esimerkiksi haluaa tarjota kenelle tahansa mahdollisuuden lähettää itselleen salattuja viestejä, voi julkaista julkisen avaimen kaikille, mutta pitää yksityisen avaimen itsellään. Tällöin kuka tahansa voi lähettää kyseiselle vastaanottajalle salatun viestin, jonka ainoastaan vastaanottaja voi yksityisellä avaimellaan avata. Tätä kutsutaan epäsymmetriseksi salaukseksi erotuksena vanhemmasta symmetrisestä salauksesta, jossa lähettäjällä ja vastaanottajalla on sama salausavain, jonka on pysyttävä salassa.^[4][5]

Toisaalta myös yksityisellä avaimella voidaan luoda salattuja viestejä, jotka voidaan avata vain julkisella avaimella; tämän ominaisuuden avulla yksityisen avaimen haltija voi allekirjoittaa viestinsä siten, että julkisen avaimen haltijat voivat olla varmoja siitä, että viestit ovat peräisin häneltä.^[4]

Toiminta

Avainten luonti

Oletetaan että Liisa haluaa Pekan lähettävän hänelle 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 e siten että 1 < e < N jolle (p-1)(q-1) on suhteellinen alkuluku.
3. Valitse d 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 salattu viesti c kun n on Pekan alkuperäinen viesti:

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

Salauksen purkaminen

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

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

Purku toimii, koska

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

ja ed ≡ 1 (mod p-1) ja ed ≡ 1 (mod q-1). Fermat’n pieni lause antaa

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

jonka mukaan (koska p ja q ovat erisuuria alkulukuja)

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

Esimerkki

Valitaan vaikkapa alkuluvut 5 ja 11. Niiden tulo (N) on 55. ϕ(55) = (5-1)(11-1) = 40. Valitaan julkinen avain e, siten että (P, ϕ(R)) = 1. (7, 40) = 1. Julkinen avain e = 7. Henkilökohtaisen avaimen d ratkaisuun tarvitaan luvun 7 käänteisluku mod ϕ(55) = 40. Tähän voidaan löytää ratkaisu 7x ≡ 1 (mod 40), joka on x ≡ 23 (mod 40). d on siis 23. Näin saadaan avainparit (e = 7, N = 55) ja (d = 23, N = 55)

Salattava sanoma olkoon: TERVE koodattuna numeroiksi merkkikoodauksella: 28, 7, 26, 31, 7

Koodataan se julkisella avaimella e, jolla on arvo 7.

28^7 (mod 55) = 13492928512 (mod 55) = 52

7^7 (mod 55) = 823543 (mod 55) = 28

26^7 (mod 55) = 8031810176 (mod 55) = 16

31^7 (mod 55) = 27512614111 (mod 55) = 26

7^7 (mod 55) = 823543 (mod 55) = 28

Sanoma on siis salattuna 52, 28, 16, 26, 28.

Sanoman purkaminen tapahtuu henkilökohtaisella avaimella d, jolla on arvo 23.

52^23 (mod 55) = 2.9381698884548476032434836e+39 (mod 55) = 28

28^23 (mod 55) = 1.9259043800372760688541191e+33 (mod 55) = 7

16^23 (mod 55) = 4951760157141521099596496896 (mod 55) = 26

26^23 (mod 55) = 3.5025714498220057526153130e+32 (mod 55) = 31

28^23 (mod 55) = 1.9259043800372760688541191e+33 (mod 55) = 7

Selkokielellä siitä tulee jälleen TERVE.

Allekirjoittaminen

Pääartikkeli: Digitaalinen allekirjoitus

RSA:ta voidaan käyttää myös viestien allekirjoittamiseen. Sekä lähettäjä että vastaanottaja laskevat tiivistefunktion (esimerkiksi MD5, SHA-1) avulla viestin kryptografisen tiivisteen. Lähettäjä koodaa tiivisteen salaista avaintaan käyttäen (kuten purkaisi julkisella avaimella salatun viestin), ja lähettää koodatun tiivisteen viestin mukana vastaanottajalle. Vastaanottaja avaa koodatun tiivisteen käyttäen julkista avainta (kuin salaisi sen). Mikäli tiivisteen koodauksen avaaminen tuottaa viestin alkuperäisen tiivisteen, vastaanottaja voi pitää varmana sitä, että viestin allekirjoittaja on käyttänyt julkista avainta vastaavaa salaista avainta.

Algoritmit

RSA:n toteutus perustuu nopeaan potenssiinkorotusalgoritmiin jäännösluokkarenkaassa modulo ${\displaystyle 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

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.

RSA-pulmaksi kutsutaan selkokielisen tekstin etsimistä salatun tekstin ja julkisen avaimen perusteella.^[6]

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.