RSA-protokolla ja sen murtaminen

Abstract

Yksi tietoturvan keskeinen osa-alue on tiedon luottamuksellisuus, eli se että kukaan sivullinen ei pääse käsiksi tietoihin. Internetin välityksellä siirrettävän tiedon luottamuksellisuus pyritään säilyttämään salaamalla keskustelevien osapuolien välinen viestintä. Nykyisin salaukseen käytetään useimmiten jotakin julkisen avaimen salausalgoritmia. Julkisen avaimen salausalgoritmeja on monia ja kaikilla niistä on omat vahvuutensa ja heikkoutensa. Tässä työssä esitellään Rivest-Shamir-Adleman-algoritmi, josta käytetään lyhennelmää RSA. Lisäksi johdetaan viestin salaamiseen ja salauksen purkamiseen käytetyt yhtälöt. Lopuksi annetaan esimerkki algoritmin toiminnasta käytännössä ja mietitään keinoja salauksen murtamiseen.

RSA-algoritmin salaus perustuu lukujen tekijöihin jaon laskennalliseen vaikeuteen. Tekijöihin jako on sitä vaikeampaa ja hitaampaa, mitä suuremmat luvun tekijät ovat. RSA-algoritmi tuottaa kahden suuren alkuluvun pohjalta julkisen avaimen e ja yksityisen avaimen d. Algoritmissa käytetyt alkuluvut piilotetaan kertomalla ne keskenään, jolloin saadaan luku n. Luku n on puolialkuluku eli luku, jolla on täsmälleen kaksi alkulukutekijää. Saadut avaimet ovat toistensa vastaluvut modulaarisen kertolaskun suhteen modulo n. Tämän vuoksi niistä voidaan muodostaa kaksi funktiota, jotka kumoavat toisensa. Jäljelle jää vain alkuperäinen viesti. Toista funktioista käytetään tiedon salaamiseen ja toista salauksen purkamiseen. Toinen avaimista valitaan julkiseksi avaimeksi, jota käytetään tiedon salaamiseen. Julkinen avain voidaan jakaa julkisesti, koska siitä ei voida helposti laskea yksityistä avainta.

RSA-salaus voidaan murtaa suoralla hyökkäyksellä jakamalla luku n tekijöihin. Muitakin suoria hyökkäyksiä on, mutta koska ne ovat vielä tekijöihin jakoakin tehottomampia, jätetään ne tämän työn ulkopuolelle. Tekijöihin jaosta tekee haastavaa se, että jaettava puolialkuluku on parhaassakin tapauksessa satoja merkkejä pitkä. Koska nykyisille tietokoneille ei ole riittävän tehokkaita tekijöihin jako algoritmeja, tekijöihin jakoon kuluva aika kasvaa eksponentiaalisesti jaettavan luvun koon funktiona. Teoreettisella tasolla on kuitenkin onnistuttu luomaan kvanttialgoritmeja, eli kvanttitietokoneelle kehitettyjä algoritmeja, joilla pystyttäisiin jakamaan suuremmatkin puolialkuluvut tekijöihin sekunneissa. Nykyiset kvanttitietokoneet eivät ole kuitenkaan vielä läheskään niin edistyneitä, kuin kyseiset algoritmit vaatisivat. Toisaalta koska RSA-algoritmin salaus perustuu laskennalliseen vaikeuteen tarkoittaa se sitä, että kaikki RSA-avaimet ovat murrettavissa. Oleellista on, että salauksen murtaminen kestää niin kauan, että salattu tieto ei ole enää relevanttia.

Toinen tapa murtaa RSA-salaus on epäsuora hyökkäys. Epäsuora hyökkäys ei kohdistu suoraan algoritmiin vaan pyrkii etsimään haavoittuvuuksia muualta. Tyypillisiä kohteita ovat laite, jolla algoritmia ajetaan ja sen käyttäjä. Esimerkiksi on mahdollista tarkkailla tietokoneen prosessorin sähkön kulutusta tai prosessorin pitämiä ääniä sen purkaessa salausta. Saadusta datasta pystytään helposti selvittämään yksityinen avain, eli sitä kautta murtamaan salaus.

Yhteenvetona murtamisesta voidaan todeta, että itse RSA-algoritmia ei olla pystytty murtamaan. RSA-algoritmin vahvuuksiin kuuluukin se, että se on todennäköisesti vahva salaus vielä tulevaisuudessakin. RSA-algoritmin heikkous on sen hitaus, minkä takia sitä käytetäänkin usein jonkin nopeamman algoritmin avainten vaihdossa.