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
Lisätietoja
Tagit
Erikoisosaaminen
Tietoturva |
Omat tagit
TIVIA ry - Asiantuntijat ja yhteyshenkilöt
TIVIA ry - Muita referenssejä
TIVIA ry - Muita bloggauksia
It- ja ohjelmistoalan työpaikat
- Laura - Lead developer, eInstant Platform
- Laura - Lead/Senior Backend Developer, vedonlyöntipelit
- Laura - Testiautomaatioasiantuntija
- Laura - Laatuasiantuntija (vuorotteluvapaasijaisuus)
- Laura - Sovelluspäällikkö
- Laura - Software Architect
- Efima Oyj - Senior Service Manager
Premium-asiakkaiden viimeisimmät referenssit
- IsoSkills Oy - Nearshore resursseilla lisättiin kyvykkyyttä Tosibox Oy:n it-kehityshankkeisiin
- Symbio - Tuotannon turvallistamisjärjestelmä
- Asiakas Group Oy - Moneksin palvelut Googlen etusivulle Asiakkaita.comin toimesta
- Solu Digital Oy - Uusi projektinhallinta- ja tuntikirjausratkaisu helpottaa työtä ja säästää aikaa
- Solu Digital Oy - Hankintasalkku Microsoft 365 -ympäristöön
- Solu Digital Oy - Projektidokumentit hallintaan Solu 365 -ratkaisulla
- Solu Digital Oy - Paikkariippumatonta työskentelyä Microsoft 365 -ratkaisuilla
Tapahtumat & webinaarit
- 05.04.2024 - Webinaari: Miten käytän tekoälyä markkinoinnin tehostamiseen?
- 11.04.2024 - On-demand webinar: NetSuite Best Practices for Software Companies
- 18.04.2024 - Aamiaistilaisuus: Ennustettavampaa liiketoimintaa vastuullisesti
- 24.04.2024 - Reviewing the Nordic SaaS market with Monterro
- 16.05.2024 - Five Years Out Helsinki
Premium-asiakkaiden viimeisimmät bloggaukset
- Nordea - Nordean asiakaspalveluun tarkoitettu Jodel-kanava palkittiin digitaalisen median Grand One -kilpailussa
- Vaimo Finland Oy - PWA ja hakukoneoptimointi
- Staria Oyj - Kuinka NetSuite tekee projektiliiketoiminnasta sujuvampaa
- IsoSkills Oy - AI's Role in Test Automation: Boosting Speed and Accuracy
- Efima Oyj - Suuri ERP-seikkailu odottaa montaa kaupan alan yritystä
- Nordea - Työn ja vapaa-ajan tasapaino Nordealla
- Altoros Finland Oy - Tekoälyn käyttöönotto - avain yritysten kilpailukyvyn säilyttämiseen
Digitalisaatio & innovaatiot blogimediaBlogimediamme käsittelee tulevaisuuden liiketoimintaa, digitaalisia innovaatioita ja internet-ajan ilmiöitä |