RSA

Julkinen avain
[Esittely]
[Salaus]
[Julkinen avain]
+ [Kehitys]
+ [Minne]
+ [Algoritmeja]
+ + [Diffie-Hellman]
+ + [RSA]
+ + [Muita]
+ [Riskit]
+ [Hallinta]
[Tuotteita]
[Termejä]
[Lähdeluettelo]


Jyri Lindström
Teemu Mäkelä

Yleistä

RSA (Rivest-Shamir-Adleman) on tunnetuin julkisen avaimen salausmenetelmä. Kaikista asymmetrisistä salausmenetelmistä se on helpoin ymmärtää ja toteuttaa. Sen kehittivät Ron Rives, Adi Shamir ja Leonard Adleman vuonna 1977. RSA on patentoitu Yhdysvalloissa, mikä on hieman rajoittanut sen käyttöä. Patentti raukeaa 20. syyskuuta 2000.

Käyttökohteita

RSA on hyvin yleinen algoritmi mm. älykorteilla ja sähköpostin suojaamisessa. RSA on lähes kaikkien kaupallisten julkisen avaimen menetelmää käyttävien tuotteiden pohjana.

Käytännössä RSA:ta ei käytetä puhtaasti liikenteen salaukseen asymmetrisesti, sillä symmetrisiin järjestelmiin verrattuna asymmetriset salausmenetelmät ovat jopa 10000 kertaa hitaampia. Tämä ero johtuu siitä, että asymmetrisissä menetelmissä käytetään luokkaa 1024 bitin avaimia, kun taas symmetrisissä järjestelmissä saavutetaan sama turvallisuuden taso luokkaa 128 bitillä. Pidempi avain kasvattaa huomattavasti laskennan tarvetta.

Tämän johdosta RSA yhdistetään usein symmetriseen salausalgoritmiin kuten DES:iin. Tällöin yhteyden DES avain vaihdetaan RSA:lla esim. kättely vaiheessa, ja itse yhteys suojataan käyttämällä DES:iä.

Lyhyissä, kerran lähetettävissä sähköposti sanomissa laskenta-ajan kasvu ei haittaa. Tällöin RSA:ta voidaan käyttää sanoman salaukseen tai allekirjoitukseen.

Algoritmi

RSA on asymmetrinen salausmenetelmä, joten se tarvitsee sekä julkisen että salaisen avaimen. Avainten generointi etenee seuraavasti:

1. Ensin valitaan kaksi alkulukua P ja Q, jotka kerrotaan keskenään ja tulona saadaan N.
2. Valitaan luku E (pienempi kuin N) siten, että E ja (P-1)(Q-1) ovat suhteellisia alkulukuja keskenään.
3. Valitaan luku D siten, että (DE-1) on jaollinen (P-1)(Q-1):llä. D lasketaan kongruenssiaritmetiikan keinoin, laskemalla E:n käänteisluku modulokunnassa (P-1)(Q-1), siis D on (E^-1) mod ((P-1)(Q-1)).

Nyt lukupari (D, N) on salainen avain, ja (E, N) on julkinen avain. Kun luvut on generoitu, tulee P ja Q hävittää, koska näiden pohjalta voidaan julkinen avain tuntemalla laskea salainen avain.

Kun Liisa haluaa lähettää tekstin M Matille salattuna, hän laskee salatun tekstin C Matin julkisella avaimella siten, että C on (M^E) mod N. Saatuaan viestin C Matti laskee M':n seuraavasti: M' = (C^D) mod N. Nyt M' on M, mikä voidaan havaita suorittamalla laskutoimitukset.

Turvallisuus

RSA pohjautuu lähes yksisuuntaisiin funktioihin, RSA:n tapauksessa kahden suuren luvun kertomiseen. Suuren luvun tekijöihin jakaminen on työlästä, joten kertominen on lähes yksisuuntainen funktio. Valitsemalla kerrottavat luvut siten, että molemmat ovat alkulukuja, saadaan tulona luku, jonka jakaminen takaisin kahteen tekijäänsä on erittäin hankalaa. Jos keksittäisiin jokin uusi hyvä keino jakaa lukuja tekijöihin tulisi RSA nopeasti turvattomaksi. Tämä on kuitenkin hyvin epätodennäköistä, mutta RSA:n täyttä turvallisuutta ei ole voitu mitenkään todistaa.

RSA:n avaimessa tarvitaan enemmän bittejä kuin symmetrisissä salauksissa, koska algoritmin rakenteesta johtuen salausta voi yrittää murtaa jakamalla lukuja tekijöihin. Tämä on nopeampaa kuin IDEA:n tai DES:n murtaminen, joka onnistuu nykyisen tietämyksen mukaan vain kokeilemalla kaikki mahdollisuudet läpi.

Suurten lukujen tekijöihin jakaminen on helpottunut jonkin verran sitten RSA:n kehittämisen, mutta ei niin paljoa, että RSA olisi käyttökelvoton. Nopeutta on enimmäkseen lisännyt tietokoneiden laskentatehon lisäys, ja jonkin verran myös erilaiset menetelmät.

256 bitin RSA avaimia voi helposti murtaa kotitekoisesti. 384 bittiä vaati jo enemmän tehoja, ja on mahdollista lähinnä yliopistoissa, suurissa yhtiöissä ja Internetissä useiden koneiden voimin. 512 bittiset avaimet ovat suurimpien valtioiden murrettavissa. 1024 bittiä pitäisi olla riittävä määrä toistaiseksi, mutta 2048 lienee parempi vaihtoehto, jos haluaa suojata tietonsa eliniäksi tai vuosikymmeniksi.

Murtaminen

Luonnollisin tapa murtaa RSA on jakaa julkisessa avaimessa oleva N tekijöihinsä, ja näiden sekä E:n avulla laskea D. Tekijöihin jakamisesta tiedetään kuitenkin, että kaikkien tunnettujen tapojen vaatima laskenta-aika kasvaa eksponentiaalisesti avaimen pituuden kasvaessa.

Valitun salakielisen tekstin hyökkäys on erittäin tehokas RSA:n implementaatioita vastaan. Itse RSA:n algoritmia se ei riko. Tässä hyökkäyksessä Maija saa käsiinsä kuuntelemalla Liisan Matille salattuna lähettämän viestin C. Jos Maija lisää tähän tietyllä menetelmällä satunnaisuutta, jolloin Matti ei tunnista viestiä, ja saa Matin allekirjoittamaan sen omalla salaisella avaimellaan, Matti itseasiassa purkaa viestin C, ja näin Maija saa käsiinsä alkuperäisen viestin.