Lukuteoriaan perustuvia salausmenetelmiä

Abstract

Tämän tutkielman tarkoitus on tutustuttaa lukija salakirjoituksen maailmaan lukuteorian näkökulmasta. Tutkielma sisältää salausmenetelmiin tarvittavat matemaattiset pohjatiedot, Diffie-Hellmanin salausmenetelmän ja RSA-salausmenetelmän, sekä molemmille salausmenetelmille soveltuvat purkumenetelmät. Monet esitetyistä tuloksista perustuvat algebraan, mutta tähän tutkielmaan tulokset on pyritty muuttaaman lukuteorian piiriin siten, että lukija ei välttämättä edes tiedä lukevansa algebraan perustuvia tuloksia. Ensimmäisessä luvussa tutustutaan jaollisuuteen, lukuteoriaan ja kokonaislukujen tekijöihinjakoon. Tarkoituksena on esittää riittävän kattava pohja salausmenetelmiä varten, jotta kaikki niissä käytetty matematiikka olisi hyvin perusteltua. Toisessa luvussa käsitellään lisää jaollisuustuloksia modulaariaritmetiikan näkökulmasta. Kolmannessa luvussa käsitellään primitiivisiä juuria, jotka ovat tärkeässä roolissa Diffe-Hellmanin salausmenetelmän turvallisuuden perustelemisessa. Ensin osoitetaan, miten primitiivisten juurten moninkertojen avulla saadaan esitettyä salausmenetelmässä käytössä oleva lukujoukko. Tämän jälkeen osoitetaan, että salausmenetelmässä käytetyssä lukujoukossa on aina olemassa primitiivinen juuri. Salausmenelmät esitetään neljännessä ja viidennessä luvussa siten, että niiden toimivuus perustellaan aiemmin esiteltyjen tuloksien avulla ja niistä näytetään havainnollistavat esimerkit. Neljännessä luvussa käsitellään Diffie-Hellmanin salausmenetelmää, jonka tarkoituksena on pystyä luomaan informaation lähettäjälle ja vastaanottajalle yhteinen salausavain, jota muut ulkopuoliset eivät pääse lukemaan. Sen jälkeen tutustutaan Shankin algoritmiin, jonka avulla ulkopuolinen henkilö voi yrittää selvittää tätä salausavainta. Viidennessä luvussa käsitellään RSA-menetelmää, jonka tarkoituksena on pystyä lähettämään viesti kahden henkilön välillä siten, että ulkopuolinen ei pysty lukemaan sen sisältöä. Lopuksi esitellään Pollardin p-1 -menetelmä, jolla ulkopuolinen henkilö voi yrittää avata salattua viestiä. Käyttämällä tutkielmassa esitettyjä salausmenetelmiä yhdessä, voidaan tietojen vaihtaminen toteuttaa turvallisesti esimerkiksi internet-sivustoilla. Liitteissä on laskettu Maxima-ohjelmalla esimerkit kaikista käytetyistä salaus- ja purkumenetelmistä. Liitteet on pyritty tekemään mahdollisimman helppolukuisiksi Maximaa käyttämättömille henkilöille siten, että he voisivat toteuttaa itsenäisesti samat esimerkit.