Julkisia salaisuuksia

(Eric Sonstroem/Flickr. CC-BY 2.0.)

Viime kerralla tutustuimme salakirjoitukseen. Kaikissa viimekertaisissa menetelmissä oli kuitenkin se ongelma, että kummallakin osapuolella täytyy olla sama avain. Nykypäivän käyttötarkoituksiin se ei yksinkertaisesti kelpaa — jokainen suojattu nettiyhteys tarvitsee uuden avaimen sinun ja täysin tuntemattoman toimijan välille. Suojaamattoman yhteyden yli avainta ei voi sellaisenaan lähettää ilmeisistä syistä.

Vaihtoehtoja on kaksi: joko perustaa joka kylälle avainkioskeja, joilla pitää käydä aina Facebookiin halutessaan — tai käyttää ovelaa matematiikkaa. Blogin teemasta on pääteltävissä, kumpaan reittiin tutustumme: julkisen avaimen salakirjoitukseen, joka pystyy siirtämään avaimen turvallisesti pahisten nenän edestä.

Maalikikka

Matemaattiselle selitykselle on mielestäni kätevä vertaus, jonka itse opin vuosia sitten John MacCormickin kirjasta 9 Algorithms That Changed the Future (Princeton University Press, 2012). Kuvitellaankin, että salakirjoitus perustuu väreihin, jolloin tarkoituksenamme on sekoittaa samanlainen maalisekoitus paljastamatta sitä muille. Voimme sekoittaa värejä rauhassa, mutta kaikki välisemme viestintä tapahtuu kansainvälisessä vakoojakonferenssissa.

Aloitetaan. Ensin sovimme yhteisen värin. Sanotaan vaikkapa, että sekoitat muutaman purkin kivaa vaaleansinistä väriä. Jätät purkit pöydälle, jolta minä haen yhden. (Muut katoavat mystisesti...)

Seuraavaksi kumpikin valitsee itselleen salaisen värin. Tällä kertaa päätät tehdä raikkaan limenvihreää, kun taas minä teen tummaa verenpunaista. Sitten tapahtuu maaginen vaihe: kumpikin ottaa purkin sitä maalia ja sekoittaa sen purkkiin yhteistä väriä. Sinulle tulee turkoosia, minulle tummahkoa violettia.

Vaihdamme tölkkejä pöydän kautta, taas muutama kappale matkalla kadoten, ja palaamme nurkkauksiimme.

Yhdistät saamasi tölkin ja toisen purkin salaista väriäsi. Siitä tulee harmaata: yksi osa sinistä, yksi osa vihreää ja yksi osa punaista.

Yhdistän saamani tölkin ja toisen purkin salaista väriäni. Siitä tulee harmaata: yksi osa sinistä, yksi osa vihreää ja yksi osa punaista.

Entä mitä värejä vakoojilla on? Vaaleansinistä, vihreä-vaaleansininen-yhdistelmää ja punainen-vaaleansininen-yhdistelmää. Niistä ei voi sekoittaa samaa suhdetta kuin meillä on! Kahdesta jälkimmäisestä tulisi purppuraa, koska sinistä on tuplamäärä.

Sama luvuilla

Sitten tehdään sama luvuilla. Ensinnäkin valitaan kaksi yhteistä lukua, kantaluku $a$ ja kellotaulu $k$. Näille luvuille on tiettyjä ehtoja: $k$ on alkuluku ja luku $a$ korotettuna erisuuruisiin potensseihin tuottaa kaikki luvut nollaa lukuunottamatta $k$-kokoisella kellotaululla. Valitaan esimerkiksi $k = 13$ ja $a = 6$.

Nyt kumpikin valitsee salaisen luvun. Otat luvun $x = 2$ ja lasket arvon lausekkeelle $a^x \mod k$. Tämä tarkoittaa yksinkertaisesti potenssiinkorotusta, joka tapahtuu kellotaululla: $6^{2} = 36$, ja tämä jaettuna $13$:lla jättää jakojäännökseksi $10$.

Minä otan luvun $y = 8$ ja lasken $6^8 \mod 13 = 3$. Sitten vaihdamme juuri saamiamme lukuja.

Korotat antamani luvun salaisen lukusi mukaiseen potenssiin: $3^2 \mod 13 = 9$. Minä teen samoin antamallesi luvulle: $10^8 \mod 13 = 9$. Kappas, meillehän tuli sama tulos!

Tämä toimii siksi, että annoit luvun $a^x$ ja minä luvun $a^y$. Korottamalla ne omaan potenssiin kummallekin tulee kellotaulun luku $a^{xy}$. Puolestaan sivustakatsoja ei pysty päättelemään vaihtamistamme tiedoista lopullista lukua.

Miksi tätä ei pureta

Juuri käyttämäämme menetelmää kutsutaan Diffie-Hellmanin algoritmiksi, jonka herrat julkaisivat vuonna 1976. Hassua kyllä, sama menetelmä oli esitelty jo hieman aiemmin brittien tiedustelupalvelun sisällä, mutta sen huippusalaisuusluokitus purettiin vasta 1997. Vuonna 1977 julkaistiin samantyylinen RSA-algoritmi, josta tuli ensimmäinen laajasti käytettävä salausmenetelmä, jossa avain on julkinen. Kuka tahansa voi kirjoittaa viestin julkista avainta käyttäen, mutta vain salaisen avaimen omistaja voi lukea sen.

Mutta, mutta. Eikös jollain matemaattisella kommervenkillä voi kuitenkin selvittää lopullisen avaimen? Vastaus on nykytietämyksellä "ei järkevässä ajassa". Esimerkkimme pienet luvut aukeaisivat hetkessä, mutta todelliset järjestelmät käyttävät satoja numeroita pitkiä lukuja. Potenssiinkorotus kellotaululla on varsin helppoa, kun taas takaperin ongelmaan ei ole juuri kokeilemista parempaa ratkaisua. Koska isoja lukuja on paljon,^[lähde?] valtavalla laskentavoimallakin tieto vanhenisi ennen sen purkamista.^[1]

Tavallaan (käytännössä) ratkaisemattomat ongelmat ovatkin siis ihan hauskoja. Toinen vaikea pulma on kahden suuren alkuluvun tulon palauttaminen takaisin alkuluvuiksi — RSA-salaus perustuu puolestaan tähän. Kvanttitietokoneiden kehittyminen saattaa tehdä ongelmista ratkaistavia, mutta toisaalta tuo mukanaan uuden joukon vaikeita ongelmia.

---

^[1] Eräistä teknisistä syistä salaus on peruskäytössä heikompi, joten suurimmat tiedustelupalvelut saattavat pystyä purkamaan perussurffailua mikäli sille päälle tulevat.