III.5.  RSA-menetelmä

Englantilaiset Rivest, Shamir ja Adleman julkaisivat vuonna 1978 erään suuriin alkulukuihin perustuvan salausmenetelmän, joka on osoittautunut tarpeeksi yksinkertaiseksi, mutta kuitenkin riittävän suojaavaksi. Menetelmää kutsutaan nykyään RSA-menetelmäksi. Se perustuu seuraavaan tulokseen.

Lause 3.5.1.

Olkoot ja eri alkulukuja, ja . Olkoon edelleen kokonaisluku sellainen, että , ja kokonaisluku sellainen, että . Silloin pätee, että .

Todistus. (Jos todistus ei tunnu kiinnostavalta, hyppää sen yli! Todistuksen ideoita ei tarvita myöhemmin.) Oletuksen nojalla jollekin kokonaisluvulle . Silloin

,

joten riittää osoittaa, että . Koska , luku ei jaa lukua eli . Fermat'n pikkulause 3.4.6 ilmoittaa silloin, että

ja siten

.

Vastaavasti symmetriasyistä . Siten sekä että jakavat luvun . Koska ne ovat eri alkulukuja, myös niiden tulo jakaa samaisen luvun. Siten on saatu, että , mikä pitikin todistaa.

Itse menetelmän kulku selvinnee parhaiten esimerkin avulla.

Esimerkki 3.5.2. (RSA-menetelmän algoritmi)

1° Koodin laatija valitsee kaksi (yleensä suurta) alkulukua, esimerkiksi

ja .

2° Laatija laskee luvut

ja .

3° Laatija valitsee koodausavaimen siten, että , esimerkiksi

.

4° Laatija laskee luvulle käänteisalkion renkaassa : Jakoyhtälön mukaisesti , joten . Siten ja edelleen eli . Niinpä nyt

.

5° Laatija antaa viestin lähettäjälle tiedoksi vain luvut ja . Ja viestin vastaanottajalle vain luvut ja . Luku on ns. purkuavain.

6° Lähettäjä lähettää sellaisen (numero)viestin , jolle , koodattuna kaavalla ; esimerkiksi viestille

,

lähetettävä viesti on

.

Koska ja , koodatuksi viestiksi saadaan laskettua

.

7° Vastaanottaja purkaa koodatun viestin kaavalla :

.

Tarkistetaan vielä, että purkutulos on oikein. Kun lasketaan modulo 143, saadaan ensinnä alkion 48 neliön neliöille jne:

,    ,    ,
,    ,    .

Käyttäen potenssiluvun 103 binääriesitystä hyväksi saadaan siten, että

Miksi sitten viestin purku onnistuu aina? Jos merkitään, että , on silloin ja , joten edellä olevaa lausetta 3.5.1 voidaan käyttää. Sen mukaan

eli todellakin

.

Eräs RSA-menetelmän etu on se, että siinä viestin lähettäjä ja vastaanottaja käyttävät eri avaimia. Perinteisissä salausmenetelmissä he yleensä ovat käyttäneet samaa avainta. Pelkästään toisen avaimen avulla on myös lähes mahdotonta murtaa salausmenetelmää.

Edes koodauksen perustana olevan luvun tietäminen ei anna heti murtomahdollisuutta. Tätä kuvannee hyvin internet-verkossa 1990-luvun alussa julkaistu koodattu viesti, jonka ilmoitettiin perustuvan annettuun 129−numeroiseen lukuun. Ensimmäisenä ratkaisun löytänyt ryhmä ilmoitti käyttäneensä viestin murtamiseen kahdeksan kuukautta ja noin 600 alilaskijaa 20 eri maassa. Yhteenlaskettuna tietokoneaikaa tarvittiin noin 5000 mips-vuotta (mips = miljoona toimintoa sekunnissa)!

[Ylempi pääsivu] [Edellinen sivu] [Seuraava sivu]