RSA:n kryptoanalyysi

RSA on jo neljän vuosikymmenen ajan säilyttänyt asemansa vahvana kryptografisena menetelmänä. Pitkä käytännön kokemus siis puoltaa ajatusta RSA:n turvallisuudesta, mutta periaatteellisella tasolla RSA:n vahvuuteen liittyy avoimia kysymyksiä. Paras saatavilla oleva tapa arvioida RSA:n turvallisuutta on koetella sitä käytännössä kryptoanalyysin keinoin. RSA on tiedon salauksen ja digitaalisen allekirjoittamisen menetelmä, joka on ollut käytössä yli 40 vuotta. RSA esiteltiin vuonna 1977 eräänä ensimmäisistä julkisen avaimen salausmenetelmän toteutuksista. Salausmenetelmänä RSA:sta ei ole neljän vuosikymmenen aikana (tiettävästi) löydetty mitään sellaista perustavanlaatuista epäkohtaa tai haavoittuvuutta, joka olisi vesittänyt ajatuksen sen kryptografisesta vahvuudesta. RSA:ta käytetäänkin edelleen yleisesti ratkaisemaan niitä ongelmia, joiden ratkaisemiseksi se alunperin kehitettiin. Keskeisin näistä ongelmista on kahden (tai useamman) toisilleen entuudestaan tuntemattoman tahon kommunikointi turvattoman tietoverkon välityksellä. RSA tarjoaa välineet tiedon luottamuksellisuuden, aitouden ja kiistämättömyyden varmistamiseen. Oikein käytettynä RSA toimii myös ratkaisuna klassiseen avaimenvaihto-ongelmaan, jossa (symmetristä) salausavainta ei voida lähettää toiselle osapuolelle turvattoman tietoverkon välityksellä salausavaimen paljastumisen vaaran takia. Ajatus RSA:sta vahvana kryptografisena menetelmänä on kahtalainen. Yhtäältä laaja ja pitkäaikainen käytännön kokemus ja empiirinen tutkimus tukee ajatusta RSA:n turvallisuudesta. Toisaalta RSA:n turvallisuutta ei ole koskaan pystytty osoittamaan periaatteellisella tasolla. Matematiikan ja formaalien mallien tasolla RSA:n asema vahvana kryptografisena menetelmänä on siis avoin kysymys, jolla on suora yhteys tiettyihin teoreettisen tietojenkäsittelytieteen ja lukuteorian toistaiseksi ratkaisemattomiin ongelmiin.

RSA salausmenetelmänä yleisesti

Julkisen avaimen salausmenetelmänä RSA perustuu kahden toisiinsa sidotun, mutta kuitenkin erillisen salausavaimen käyttöön. Näitä kahta salausavainta kutsutaan julkiseksi ja yksityiseksi avaimeksi, ja nimensä mukaisesti vain jälkimmäinen on tarkoitettu yksinomaan avainparin haltijan tietoon. Periaatteessa siis kuka tahansa voi salata viestin (digitaalisen tiedon) tahon X julkisella avaimella. Viestin salauksen purku ei kuitenkaan onnistu julkisella avaimella, vaan siihen tarvitaan vastaava yksityinen avain, jonka vain X tietää. Tähän perustuu se, että X voi kommunikoida luottamuksellisesti Y:n kanssa ilman yhteistä salaisuutta. Mielenkiintoista RSA:n kahdessa salausavaimessa on sekin, että myös yksityisellä avaimella voi "salata" viestejä, jolloin viestin saa takaisin alkuperäiseen muotoonsa vain vastaavalla julkisella avaimella. Tähän perustuu se, että RSA toimii myös välineenä tiedon aitouden ja kiistämättömyyden takaamisessa. Jos nimittäin viesti aukeaa X:n julkisella avaimella, on se osoitus siitä, että se oli lukittu X:n yksityisellä avaimella.

"RSA tarjoaa välineet tiedon luottamuksellisuuden, aitouden ja kiistämättömyyden varmistamiseen."

RSA-avainparin luominen on laskennallisesti sen verran kevyt toimenpide, että se onnistuu tavallisella kotikoneella tai matkapuhelimella. Samoin RSA:lla tehtävä salaus ja salauksen purku ovat algoritmisessa mielessä melko tehokkaita toimenpiteitä. Kuten muutkin julkisen avaimen salausmenetelmät, RSA perustuu ajatukselle yksisuuntaisesta funktiosta eli siihen, että tietty toimenpide on helppo suorittaa yhteen suuntaan, mutta vaikea suorittaa käänteiseen suuntaan. RSA:n tapauksessa keskeinen esimerkki tästä on se, että hyvinkin suurten kokonaislukujen kertominen keskenään käy tehokkaasti, kun taas päinvastainen suunta eli kokonaislukujen tekijöihinjako on laskennallisesti vaikea toimenpide.

RSA ja laskennan vaativuusteoria

Eräs laskennan vaativuusteorian peruskysymyksistä on se, onko annetun laskennallisen ongelman ratkaisemiseksi löydettävissä tehokasta algoritmia. Ongelmaa voidaan pitää vaikeana tai laskennallisesti raskaana niin kauan, kunnes tehokas algoritmi sen ratkaisemiseksi löydetään. Jos kaikki ongelman tunnetut ratkaisualgoritmit ovat ei-tehokkaita, kasvavat ongelman ratkaisemiseksi tarvittavat laskennalliset resurssit eksponentiaalisesti ongelman mittasuhteiden kasvaessa lineaarisesti. RSA:n toimintaperiaatteen lähtökohta on se, että kun alkuluvut p ja q ovat riittävän suuria, niin niiden tulon pq tekijöihinjako on käytännössä mahdotonta. Ei siis tunneta tehokasta tekijöihinjaon algoritmia. Toisaalta on kuitenkin periaatteessa mahdollista, että tällainen algoritmi vielä joskus löydetään. RSA:n turvallisuuden arviointi edellyttää siis laskennan vaativuusteorian ja lukuteorian uusimpien tulosten seuraamista. RSA:n toteuttamiskelpoisuus selittyy osittain sillä, että sen tarvitsemiin näennäisesti raskaisiin laskennallisiin operaatioihin on olemassa tehokkaat algoritmit. Esimerkkinä tästä on modulaarinen potenssiinkorotus kantaluvulla, eksponentilla ja moduluksella, joiden kymmenkantaiset esitykset ovat monisatanumeroisia.

RSA:n kryptoanalyysi

Kandidaatintutkielmani keskeinen teema on RSA:n kryptoanalyysi. Pääasiallinen syy valinnalleni on se, että RSA:n kryptografisen vahvuuden osoittaminen periaatteellisella tasolla ei näytä olevan käytännössä mahdollista. Tällöin ainoaksi mahdollisuudeksi arvioida RSA:n turvallisuutta jää sen toimintaperiaatteen haastaminen ja koetteleminen käytännössä eli RSA:n kryptoanalyysi. Rinnastan tutkielmassani RSA:n toimintaperiaatteen ymmärtämisen sen kryptoanalyysin opiskelulle. Kysymykset miten RSA toimii ja miksi RSA toimii ovat eroavat vahvasti toisistaan ja mielestäni vain jälkimmäinen niistä on olennainen. Teksti: Henrik Lindberg Lindbergin kandidaattityö sai kunniamaininnan Tietoturva ry:n opinnäytetyökilpailussa, jonka tunnustukset jaettiin 7.11.2019 Lindbergin kandidaattityö on luettavissa verkossa : https://bit.ly/kandi-lindberg