DIFFIE–HELLMAN- AVAINTENVAIHTOPROTOKOLLA JA DISKREETIN LOGARITMIN ONGELMA
Kandidaatintyö Tekniikan ja luonnontieteiden tiedekunta Tarkastaja: Henri Hansen Toukokuu 2021
TIIVISTELMÄ
Jere Mäkinen: Diffie–Hellman-avaintenvaihtoprotokolla ja diskreetin logaritmin ongelma Kandidaatintyö
Tampereen yliopisto
Tekniikka ja luonnontieteet, TkK Toukokuu 2021
Diffie–Hellman-avaintenvaihtoprotokolla on menetelmä, jolla kaksi viestinnän osapuolta voivat sopia yhteisestä salausavaimesta julkista viestintäväylää pitkin. Salausavaimen sopiminen ja ja- kaminen viestinnän osapuolten välillä on yksi keskeisistä tietoturvallisuuden ongelmista ja Diffie–
Hellman-avaintenvaihtoprotokolla tarjoaa tähän ratkaisun. Työssä tarkastellaan matemaattisia ra- kenteita protokollan taustalla ja erityisesti diskreetin logaritmin ongelmaa, joka on menetelmän tieto- turvallisuuden perusta. Työssä esitellään Diffie–Hellman-avaintenvaihtoprotokollan toiminnan lisäksi Shankin algoritmi, joka on yksi keino diskreetin logaritmin ongelman ratkaisuun. Shankin algoritmin tehokkuutta vertaillaan myös suoraviivaiseen raa’an voiman ratkaisumenetelmään.
Protokolla perustuu matemaattiseen rakenteeseen nimeltään syklinen ryhmä. Sykliselle ryhmäl- le voidaan löytää virittävä alkio, jonka potenssien avulla voidaan esittää kaikki ryhmän lukujoukon al- kiot. Tämän avulla voidaan määritellä logaritmin käsite myös diskreeteille lukujoukoille ja muodostaa diskreetin logaritmin ongelma. Diskreetin logaritmin ongelman kompleksisuudesta ei ole varmuutta, mutta toistaiseksi yleiselle tapaukselle parhaatkin algoritmit hidastuvat eksponentiaalisesti.
Shankin algoritmi on yksi keino diskreetin logaritmin ratkaisuun. Se on moninkertaisesti tehok- kaampi kuin suoraviivainen yritykseen ja erehdykseen perustuva raa’an voiman menetelmä. Shan- kin algoritmin aikavaativuus onO (√
𝑁), kun taas raa’an voiman menetelmälle päteeO (𝑁). Työssä huomattiin, että kun Shankin algoritmi toteutetaan sopivilla tietorakennevalinnoilla se ratkaisi kaikki 12 käsiteltyä testitapausta nopeammin kuin raa’an voiman menetelmä ratkaisi kaksi yksinkertaisinta tapausta.
Vaikka Shankin algoritmi onkin tehokkaampi, ei senkään tehokkuus riitä, kun käytetään tarpeeksi suuria lukuja salaukseen. Kun menetelmien aikavaativuutta mitataan bitteinä, on Shankin algorit- min aikavaativuusO (2𝑘/2) ja raa’an voiman menetelmänO (2𝑘). Molemmat menetelmät hidastu- vat siis lopulta eksponentiaalisesti. Diffie–Hellman-avaintenvaihtoprotokolla on turvallinen, kunnes kehitetään algoritmi, joka ei hidastu näin jyrkästi.
Avainsanat: diskreetin logaritmin ongelma, Diffie–Hellman-avaintenvaihtoprotokolla, kryptografia, syklinen ryhmä, modulaarinen aritmetiikka
Tämän julkaisun alkuperäisyys on tarkastettu Turnitin OriginalityCheck -ohjelmalla.
SISÄLLYSLUETTELO
1. Johdanto . . . 1
2. Algebraa . . . 2
2.1 Laskutoimitus ja ryhmä . . . 2
2.2 Modulaariaritmetiikkaa . . . 3
2.3 Rakenne(ℤ𝑝\{0},·𝑝) . . . 6
2.4 Diskreetin logaritmin ongelma . . . 9
3. Diffie–Hellman-avaintenvaihtoprotokolla . . . 10
4. Ratkaisualgoritmeja . . . 12
4.1 Shankin algoritmi . . . 12
4.2 Algoritmin tehokkuus. . . 14
5. Yhteenveto . . . 16
Lähteet. . . 17
LYHENTEET JA MERKINNÄT
𝑒 laskutoimituksen neutraalialkio 𝑘 bittien lukumäärä, jos ei toisin mainita mod jakojäännösfunktio
𝑛𝑥 =𝑛◦𝑛◦. . .◦𝑛
⏞ˉˉˉˉˉˉˉˉˉˉˉ⏟⏟ˉˉˉˉˉˉˉˉˉˉˉ⏞
x kpl
, missä on◦on jokin laskutoimitus 𝑝 alkuluku, jos ei toisin mainita
ℝ reaaliluvut 𝑥−1 𝑥:n käänteisalkio ℤ kokonaisluvut
1. JOHDANTO
Ihmisillä on jo pitkään ollut tarve kommunikoida salassa muilta. Alkeellisia kryptografisia me- netelmiä käytettiin esimerkiksi jo antiikin Roomassa sotakomentojen lähettämiseen.[5] Erilaisia salausmenetelmiä on ajansaatossa kehitetty lukuisia. Erityisesti tietotekniikan kehitys on mahdol- listanut hyvinkin tehokkaiden ja käytännössä murtamattomien salausalgoritmien toteuttamisen.
Tyypillisesti salausmenetelmät vaativat toimiakseen jonkinlaisen salausavaimen, joka määrittää kuinka menetelmää käytetään. Ongelmaksi muodostuukin, kuinka tämä salausavain voidaan sopia ja jakaa viestinnän osapuolten kesken turvallisesti, jotta salattu viestintä päästään aloittamaan.
Kryptografiset menetelmät olettivat pitkään, että salausavain on pystyttävä jakamaan jotakin erik- seen suojattua viestintäkanavaa pitkin ennen kuin varsinainen salattu kommunikointi salaamatto- malla väylällä voidaan aloittaa. Tähän käsitykseen saatiin kuitenkin muutos, kun Ralph C. Merkle julkaisi idean avaintenvaihtomenetelmästä salaamatonta viestintäväylää pitkin artikkelissaanSecu- re Communications Over Insecure Channels. Hän esitteli salausmenetelmän, joka perustui vies- tinnän osapuolten julkisiin ja salaisiin arvoihin. Julkiset arvot voitaisiin nimensä mukaisesti ja- kaa julkisesti, mutta salauksen purkaminen vaatisi tietyn henkilökohtaisen salaisen arvon, jota ei tarvinnut jakaa kenellekään.[5] Merklen ajatuksiin pohjautuen julkaisivat Whitfield Diffie ja Mar- tin Hellman vielä tehokkaamman menetelmän avaintenvaihtoon salaamatonta viestintäkanavaa pitkin hyödyntäen algebraa ja alkulukuja [1].Tuo menetelmä tunnetaan nimellä Diffie–Hellman- avaintenvaihtoprotokolla.
Menetelmän taustalla on rakenne, jota kutsutaan sykliseksi ryhmäksi. Syklisen ryhmän ominai- suuksien avulla voidaan määritellä logaritmin käsite diskreetille joukolle. Diskreetin logaritmin löytäminen on vaikea ongelma, jonka kompleksisuudesta ei ole vielä toistaiseksi täyttä varmuutta.
Joillekin erikoistapauksille on olemassa subeksponentiaalisesti hidastuvia algoritmeja, mutta usein joudutaan ainakin toistaiseksi tyytymään eksponentiaalisesti hidastuviin algoritmeihin.[4] Tämä diskreetin logaritmin ongelma on se tekijä, joka takaa Diffie–Hellman-avaintenvaihtoprotokollan turvallisuuden.
Tässä työssä esitellään ensin algebran käsitteitä ja rakenteita, joiden tunteminen on keskeistä Diffie–Hellman-avaintenvaihtoprotokollan kannalta. Kolmannessa luvussa käsitellään protokollan toimintaperiaatetta ja yhteyttä diskreetin logaritmin ongelmaan. Neljännessä luvussa tutustutaan tarkemmin Shankin algoritmiin, joka on yksi keino ratkaista diskreetin logaritmin ongelma. Sa- massa luvussa myös tutkitaan algoritmin tehokkuutta verrattuna suoraviivaiseen raa’an voiman menetelmään. Viidennessä luvussa kootaan yhteen työn keskeisin sisältö ja tehdään johtopäätök- set.
2. ALGEBRAA
Algebra on matematiikan ala, joka keskittyy tutkimaan laskutoimituksia ja niiden ominaisuuksia jossakin määrätyssä joukossa. Laskutoimitukset ja joukot muodostavat erilaisia rakenteita, joilla on erilaisia ominaisuuksia. Tällaisia rakenteita ovat esimerkiksi ryhmät, renkaat ja kunnat. Algebra on melko abstrakti matematiikan suuntaus ja motivaatio sen tutkimiseen tulikin pitkään vain mate- matiikasta itsestään. Nykyään algebralle on kuitenkin löytynyt monia sovelluskohteita esimerkiksi tietotekniikassa ja fysiikassa.[2]
Diffie–Hellman-avaintenvaihtoprotokolla on yksi algebran tietoteknisistä käytännön sovelluksis- ta. Tässä luvussa esitellään muutamia algebran peruskäsitteitä ja käsitellään hieman tarkemmin niitä matemaattisia rakenteita, joihin Diffie–Hellman-avaintenvaihtoprotokolla perustuu. Tukena käytetään myös modulaariaritmetiikkaa ja hiukan lukuteoriaa.
2.1 Laskutoimitus ja ryhmä
Koska algebra keskittyy tutkimaan laskutoimituksia ja niiden ominaisuuksia, on syytä aluksi mää- ritellä, mitä laskutoimituksella tarkoitetaan [2].
Määritelmä 2.1.Olkoon𝑀epätyhjä lukujoukko.Laskutoimitus◦on kuvaus𝜃 :𝑀×𝑀−→ 𝑀.
Laskutoimitus on siis kuvaus karteesisesta tulosta𝑀×𝑀takaisin joukkoon𝑀. Tämä määritelmä vaatii, että suoritettavalla operaatiolla◦ei päästä pois käsiteltävästä joukosta𝑀. Havainnollistetaan tätä ominaisuutta yksinkertaisen esimerkin avulla.
Esimerkki 2.2.Summausoperaatio + on laskutoimitus kokonaislukujen ℤ joukossa, sillä jos (𝑧
1, 𝑧
2) ∈ ℤ× ℤ, niin 𝑧
1+ 𝑧
2 ∈ ℤ. Summausoperaatio + ei kuitenkaan ole laskutoimitus jou- kossa𝐴={1,2,3}, sillä(2,3) ∈ 𝐴×𝐴, mutta 2+3=5∉ 𝐴.
Laskutoimitus ja joukko yhdessä voivat muodostaa matemaattisen rakenteen, jota kutsutaan ryh- mäksi. Rakennetta voidaan kutsua ryhmäksi, jos seuraavan määritelmän mukaiset ehdot täyttyvät [2].
Määritelmä 2.3.Joukko𝐺ja laskutoimitus◦muodostavat ryhmän(𝐺 ,◦), kun
(i) Laskutoimitus◦onassosiatiivinen, eli kun𝑥 , 𝑦, 𝑧 ∈𝐺, pätee 𝑥◦ (𝑦◦𝑧) =(𝑥◦𝑦) ◦𝑧 .
(ii) Laskutoimituksella◦onneutraalialkio, eli sellainen alkio𝑒 ∈𝐺, että 𝑥◦𝑒 =𝑒◦𝑥 =𝑥 ,∀𝑥 ∈𝐺 .
(iii) Jokaisella alkiolla𝑥∈𝐺onkäänteisalkio, eli sellainen alkio𝑥−1 ∈𝐺, että 𝑥◦𝑥−1=𝑥−1◦𝑥 =𝑒 .
Havainnollistetaan tätä määritelmää seuraavaksi esimerkkien avulla.
Esimerkki 2.4.Reaaliluvutℝja summausoperaatio+muodostavat ryhmän (ℝ,+). Summaus on selvästi assosiatiivinen operaatio. Laskutoimituksen neutraalialkio on𝑒 =0, sillä𝑟+0=0+𝑟 =𝑟, missä𝑟 ∈ℝ. Jokaiselle alkiolle𝑟 ∈ℝvoidaan muodostaa käänteisalkio𝑟−1=−𝑟, sillä𝑟+ (−𝑟) = 0=𝑒.
Esimerkki 2.5.Reaaliluvut ja kertolaskuoperaatio·eivät muodosta ryhmää. Kertolaskuoperaatio on selvästi assosiatiivinen ja sen neutraalialkio on𝑒 = 1. Kaikille alkioille ei kuitenkaan voida löytää käänteisalkiota, sillä 0 ∈ ℝ. Nollalle ei löydy käänteisalkiota, koska∀𝑟 ∈ℝ, pätee 0·𝑟 = 𝑟·0=0≠1=𝑒. Niinpä(ℝ,·)ei ole ryhmä.
Ryhmän määritelmässä keskeistä mainitun kolmen ehdon lisäksi on se, että operaation◦on oltava laskutoimitus joukossa 𝐺. Niinpä kun tarkastellaan, onko rakenne (𝐺 ,◦) ryhmä, tulisi aluksi varmistua siitä, että operaatio◦täyttää laskutoimituksen määritelmän.
2.2 Modulaariaritmetiikkaa
Diffie–Hellman-avaintenvaihtoprotokollan kannalta erityisen mielenkiintoinen laskutoimitus on modulaarinen tulo. Jotta tämä laskutoimitus voitaisiin määritellä on syytä käydä läpi muutamia modulaariaritmetiikan peruskäsitteitä. Aloitetaan kongruenssin määritelmästä [6].
Määritelmä 2.6.Kokonaisluvut𝑎ja𝑏ovatkongruenttejamodulo n, jos erotus𝑎−𝑏on jaollinen luvulla𝑛∈ℕ. Tällöin voidaan merkitä
𝑎≡𝑏 (mod𝑛).
Kongruenssin määritelmä voidaan tulkita myös niin, että lukujen 𝑎 ja 𝑏 jakojäännös on sama jaettaessa luvulla𝑛. Tarkastellaan tätä ominaisuutta esimerkin avulla.
Esimerkki 2.7.Kokonaisluvut 11 ja 5 ovat kongruentteja modulo 3, sillä 11−5=6 on jaollinen kolmella. Voidaan siis merkitä 11≡5 (mod 3). Huomionarvoista on myös, että 11 mod 3=2 ja 5 mod 3=2, eli lukujen jakojäännökset ovat samat.
Määritellään seuraavaksi eräs modulaarisen tulon kannalta mielenkiintoinen kokonaislukujen os- ajoukko [3].
Määritelmä 2.8.Joukkoaℤ𝑛={0,1,2, . . . , 𝑛−1}, 𝑛 ∈ℕkutsutaankokonaisluvuiksi modulo𝑛.
Tällaisessa joukossa on aina𝑛kappaletta alkioita, eli|ℤ𝑛|=𝑛.
Esimerkki 2.9.Kokonaisluvut modulo 6 muodostavat joukonℤ6={0,1,2,3,4,5}.
Tällaisessa joukossa voidaan määritellä modulaarinen tulo, joka on kertolaskua muistuttava lasku- toimitus [3].
Määritelmä 2.10.Olkoon𝑎, 𝑏∈ℤ𝑛. Modulaarinen tulo joukossaℤ𝑛määritellään kaavalla 𝑎·𝑛𝑏=(𝑎 𝑏) mod 𝑛.
Tämän määritelmän avulla vältytään esimerkin 2.2, mukaiselta tilanteelta, jossa operaatiolla pää- dyttiin operoitavan joukon ulkopuolelle, sillä on selvää, että (𝑎 𝑏) mod 𝑛 ∈ ℤ𝑛, koska𝑎 𝑏 ∈ ℤ. Laskutoimituksen määritelmä 2.1 siis täyttyy modulaarisen tulon·𝑛kohdalla joukossaℤ𝑛. Tarkas- tellaan seuraavaksi tätä laskutoimitusta yksinkertaisen esimerkin avulla.
Esimerkki 2.11.Tarkastellaan joukkoaℤ6. Lasketaan laskutoimitukset 3·65 ja 4·63.
3·65=15 mod 6=3 4·63=12 mod 6=0
Esimerkistä 2.11 huomataan, että modulaarinen tulo voi tuottaa lopputulokseksi nollan, vaikka kumpikaan tulon tekijöistä ei olisikaan nolla. Perinteisestä kertolaskusta tuttu tulon nollasääntö ei siis ole voimassa modulaarisen tulon kohdalla.
Seuraava lause tarjoaa yksinkertaisen laskukaavan modulaarisen tulon laskemiseen Lause 2.12.Olkoon𝑎, 𝑏 ∈ℤ. Tällöin pätee
(𝑎 𝑏) mod 𝑛=(𝑎 mod 𝑛) ·𝑛(𝑏 mod𝑛).
Todistus. Alkiot𝑎ja𝑏voidaan kirjoittaa muodossa 𝑎 =𝑞 𝑛+𝑟 ,0≤𝑟 < 𝑛 𝑏 =𝑝 𝑛+𝑠,0≤ 𝑠 < 𝑛, missä𝑞, 𝑛, 𝑟ja𝑠ovat kokonaislukuja.
Tästä merkintätavasta huomataan, että
𝑎 mod 𝑛=𝑟 (2.1)
𝑏 mod 𝑛=𝑠 (2.2)
Nyt tulo𝑎 𝑏 saadaan muotoon
𝑎 𝑏 =(𝑞 𝑛+𝑟) (𝑝 𝑛+𝑠)=𝑞 𝑝 𝑛2+𝑞 𝑛𝑠+𝑟 𝑝 𝑛+𝑟 𝑠=𝑛(𝑞 𝑝 𝑛+𝑝 𝑠+𝑟 𝑝) +𝑟 𝑠. (2.3) Yhtälöstä 2.3 huomataan, että määritelmän 2.6 perusteella𝑎 𝑏 ≡𝑟 𝑠 (mod𝑛). Tästä voidaan myös päätellä, että tulojen𝑎 𝑏ja𝑟 𝑠jakojäännökset jaettaessa luvulla𝑛ovat samat. Toisin sanoen
(𝑎 𝑏) mod 𝑛=(𝑟 𝑠) mod 𝑛 (2.4)
Tarkastellaan seuraavaksi lauseen 2.12 yhtälön oikeaa puolta. Kun lasketaan modulaarinen tulo käyttäen merkintöjä 2.1 ja 2.2, huomataan, että
(𝑎 mod 𝑛) ·𝑛(𝑏 mod 𝑛) =𝑟 ·𝑛𝑠=(𝑟 𝑠) mod 𝑛. (2.5) Yhtälöiden 2.4 ja 2.5 perusteella voidaan todeta juurikin lauseen 2.12 mukainen yhtäsuuruus
(𝑎 𝑏) mod 𝑛=(𝑎 mod 𝑛) ·𝑛(𝑏 mod𝑛).
Esitellään vielä kaksi klassista lukuteorian apulausetta. Näitä tullaan käyttämään hyväksi käsi- teltäessä modulaarisen tulon·𝑛ja lukujoukonℤ𝑛ominaisuuksia. Näistä ensimmäisenä esitellään Eukleideen lemma, joka käsittelee tulon jaollisuutta alkuluvulla.
Lause 2.13(Eukleideen lemma).Jos𝑝on alkuluku ja tulo𝑎 𝑏on jaollinen luvulla𝑝, niin ainakin toinen luvuista𝑎ja𝑏on jaollinen luvulla𝑝.
Toinen esiteltävä lause on Fermat’n pieni lause, joka tarjoaa mielenkiintoisen ominaisuuden alku- lukuihin perustuvissa algebrallisissa rakenteissa.
Lause 2.14(Fermat’n pieni lause).Jos𝑝on alkuluku ja lukujen𝑎ja𝑝suurin yhteinen tekijä on 1, niin
𝑎𝑝−1 ≡1 (mod𝑝).
Lauseiden 2.13 ja 2.14 todistukset sivutetaan tässä työssä, mutta ne löytyvät viitteestä [3].
2.3 Rakenne ( ℤ
𝑝\{ 0 } , ·
𝑝)
Diffie–Hellman-avaintenvaihtoprotokollan perusta on rakenne, joka muodostuu joukosta kokonais- luvut modulo𝑝ja modulaarisesta tulosta·𝑝, missä𝑝on alkuluku. Kun joukostaℤ𝑝poistetaan alkio 0, täyttää rakenne(ℤ𝑝\{0},·𝑝)ryhmän määritelmän 2.3. Nollaa ei voida sisällyttää joukkoon, sillä sille ei ole olemassa käänteisalkiota. Seuraavan lauseen ja sen todistuksen myötä huomataan, että tämä rakenne on ryhmä itse asiassa vain silloin, kun p on alkuluku.
Lause 2.15.Rakenne (ℤ𝑝\{0},·𝑝) on ryhmä jos, ja vain jos𝑝on alkuluku.
Todistus. Tarkastellaan ensin tapausta, jossa𝑝ei ole alkuluku. On siis olemassa sellaiset positiiviset kokonaisluvut 𝑙 ja 𝑘, että 𝑝 = 𝑙 𝑘, 0 < 𝑘 , 𝑙 < 𝑝. Lasketaan näiden lukujen modulaarinen tulo joukossaℤ𝑝\{0}määritelmän 2.10 mukaan.
𝑘·𝑝𝑙=(𝑘 𝑙) mod 𝑝=𝑝 mod 𝑝 =0∉ℤ𝑝\{0}
Määritelmän 2.1 mukaan·𝑝ei ole laskutoimitus joukossaℤ𝑝\{0}, eikä rakenne (ℤ𝑝\{0},·𝑝)täten voi olla ryhmä, kun 𝑝ei ole alkuluku.
Oletetaan nyt, että𝑝on alkuluku. Ensinnäkin on syytä tarkastella täyttääkö·𝑝nyt laskutoimituksen määritelmän. On selvää, että kun 𝑎, 𝑏 ∈ ℤ𝑝\{0}, niin 𝑎 ·𝑝 𝑏 = 𝑎 𝑏 mod 𝑝 on yksi luvuista 0,1, . . . , 𝑝−1. Jotta, määritelmä 2.1 toteutuisi on näytettävä, että𝑎·𝑝𝑏≠0.
Näytetään tämä epäsuoralla todistuksella. Oletetaan, että on olemassa sellaiset luvut 𝑎 ja𝑏, että 𝑎 ·𝑝 𝑏 = 0. Eukleideen lemman 2.13 mukaan nyt joko 𝑎 tai 𝑏 on jaollinen luvulla 𝑝. Valitaan, että tämä luku on𝑎. Luku𝑎voidaan nyt kirjoittaa muodossa𝑎 =𝑛 𝑝,𝑛 ∈ ℤ. Toisin sanoen𝑎 on jokin luvuista . . . ,−2𝑝,−𝑝,0𝑝,1𝑝,2𝑝, . . .. Tämä on ristiriita, sillä𝑎 ∈ ℤ𝑝\{0}eli 0 < 𝑎 < 𝑝. Vastaavanlaiset päätelmät voidaan myös tehdä valitsemalla𝑏luvuksi, joka on jaollinen luvulla𝑝. On siis näytetty, että·𝑝on laskutoimitus joukossaℤ𝑝\{0}.
Seuraavaksi tarkistetaan, että määritelmän 2.3 mukaiset ehdot täyttyvät.
(i) Assosiatiivisuus. Olkoon 𝑎, 𝑏, 𝑐 ∈ ℤ𝑝\{0}. Nyt määritelmän 2.10 ja lauseen 2.12 mukaan voidaan todeta, että kyseessä on assosiatiivinen laskutoimitus laskemalla
𝑎·𝑝(𝑏·𝑝𝑐) =(𝑎 mod 𝑝) ·𝑝(𝑏 𝑐 mod 𝑝) =(𝑎 𝑏 𝑐) mod 𝑝 (𝑎·𝑝𝑏) ·𝑝𝑐=(𝑎 𝑏 mod 𝑝) ·𝑝(𝑐 mod 𝑝) =(𝑎 𝑏 𝑐) mod 𝑝 .
(ii)Neutraalialkio. Neutraalialkio on selvästikin 1, joka myös kuuluu joukkoonℤ𝑝\{0}.
(iii)Käänteisalkio. Olkoon𝑎 ∈ℤ𝑝\{0}. Luvun𝑎käänteisalkio on𝑎𝑝−2 mod 𝑝. Kun sovelletaan Fermat’n pientä lausetta 2.14 ja lausetta 2.12 voidaan laskea
𝑎·𝑝(𝑎𝑝−2 mod 𝑝) =(𝑎 mod 𝑝) ·𝑝(𝑎𝑝−2 mod 𝑝)
=(𝑎·𝑎𝑝−2) mod 𝑝
=𝑎𝑝−1 mod 𝑝 =1 Laskutoimitus·𝑝on selvästikin myös kommutatiivinen, joten
(𝑎𝑝−2𝑚 𝑜 𝑑 𝑝) ·𝑝𝑎 =𝑎·𝑝 (𝑎𝑝−2𝑚 𝑜 𝑑 𝑝) =1 Rakenne(ℤ𝑝\{0},·𝑝)täyttää kaikki kolme ehtoa, joten kyseessä on ryhmä.
Eräs mielenkiintoinen ryhmän ominaisuus, joka koskee myös ryhmää (ℤ𝑝\{0},·𝑝)on syklisyys.
Esitellään seuraavaksi sen määritelmä [2].
Määritelmä 2.16.Olkoon(𝐺 ,◦)ryhmä. Jos olemassa sellainen alkio𝑔 ∈𝐺, että
⟨𝑔⟩={𝑔𝑖|𝑖∈ℤ}=𝐺 ,
kutsutaan ryhmää(𝐺 ,◦)sykliseksi ryhmäksi. Alkiota𝑔kutsutaanvirittäjäksija ryhmää𝐺alkion 𝑔virittämäksi joukoksi.
Tämä ominaisuus saattaa vaikuttaa ensisilmäyksellä melko harvinaiselta, mutta seuraava esimerkki osoittaa, että hyvinkin tavalliset ja yleiset ryhmät voivat toteuttaa tämän määritelmän.
Esimerkki 2.17.Ryhmä(ℤ,+)on syklinen ryhmä, jonka virittää alkio 1.
⟨1⟩ ={. . . ,1−3,1−2,1−1,10,11,12,13, . . .}
={. . . ,−1−1−1,−1−1,−1,0,1,1+1,1+1+1, . . .}
={. . . ,−3,−2,−1,0,1,2,3, . . .}
={1𝑖 |𝑖∈ℤ}=ℤ
Itse asiassa kaikki ryhmät (ℤ𝑝,·𝑝), joissa p on alkuluku, ovat syklisiä. Tämä on osa seuraavaa hieman laajempaa lausetta.
Lause 2.18.Ryhmä (ℤ𝑛\{0},·𝑛) on syklinen, jos ja vain jos𝑛on jokin luvuista 1,2,4, 𝑝𝑘,2𝑝𝑘, missä 𝑝on pariton alkuluku ja𝑘 ∈ℕ.
Lause 2.18 ja sen todistus löytyvät viitteestä [8].
Seuraavassa esimerkissä havainnollistetaan ja visualisoidaan rakenteen(ℤ𝑝\{0},·𝑝) syklisyyttä.
Esimerkki 2.19.Alkio𝑔 =3 virittää joukonℤ31\{0}. Tämä joukko on havainnollistettu kuvassa 2.1.
Kuva 2.1.Joukkoℤ31\{0}alkion𝑔 =3virittämänä.
Kuvasta myös nähdään se, että alkiot näyttävät esiintyvän satunnaisessa järjestyksessä. Järjestys ei luonnollisestikaan ole aidosti satunnainen, mutta kuitenkin sellainen, että luvusta𝑖 on vaikea suoraan päätellä arvoa 3𝑖 mod 31. Jos sarjaa jatketaan, alkavat alkiot vain toistua samassa järjes- tyksessä.
Syklisyys antaa mahdollisuuden määritellä seuraavaksi logaritmin käsitteen myös diskreetissä lukujoukossa.
2.4 Diskreetin logaritmin ongelma
Määritellään seuraavaksi se ongelma, johon Diffie–Hellman-avaintenvaihtoprotokollan toiminta ja turvallisuus perustuu [4].
Määritelmä 2.20.Olkoon𝑔joukonℤ𝑝 virittävä alkio. Lukua𝑥, joka toteuttaa yhtälön
ℎ=𝑔𝑥 mod 𝑝
kutsutaan luvunℎdiskreetiksi logaritmiksi kannalla𝑔. Merkitään 𝑥 =log𝑔ℎ mod 𝑝 .
Diskreetin logaritmin ongelmaon löytää sellainen luku𝑥, että yhtälöℎ=𝑔𝑥 mod 𝑝toteutuu.
Jotta ongelman ratkaisu olisi yksiselitteinen, rajataan𝑥:n arvot välille[0, 𝑝−2]. Jos tätä rajausta ei tehdä, on ratkaisuja ääretön määrä, koska jos𝑟on ratkaisu väliltä[0, 𝑝−2], niin myös𝑟+ (𝑝−1) on ratkaisu, sillä
𝑔𝑟+(𝑝−1) =𝑔𝑟 ·𝑝𝑔𝑝−1 =𝑔𝑟 ·𝑝𝑔0=𝑔𝑟 ·𝑝1=𝑔𝑟 =ℎ.
Ongelmasta vaikean tekee se, että logaritmin arvoa on hyvin vaikea päätellä, vaikka luvut𝑝, 𝑔jaℎ olisivatkin tiedossa. Tämä huomattiin myös esimerkissä 2.19. Toisaalta on helppoa laskeaℎluvuista 𝑝, 𝑔 ja𝑥. Päädytään tilanteeseen, jossa salaukseen tarkoitettu funktio on helppoa laskea suoraan, mutta sen lopputuloksesta on hyvin vaikea päätellä alkuarvoa. Tämä ominaisuus on erittäin tärkeä, kun funktioita halutaan hyödyntää salauksessa.
3. DIFFIE–HELLMAN-AVAINTENVAIHTOPROTOKOLLA
Diffie–Hellman-avaintenvaihtoprotokolla on keino, jonka avulla kaksi osapuolta voivat sopia yh- teisen salaisuuden suojaamatonta viestintäväylää pitkin. Tätä yhteistä salaisuutta voidaan käyttää salausavaimena käytettäessä jotakin muuta kryptografista menetelmää viestien sisällön salaami- seen. Salausavaimen sopiminen ja jakaminen viestinnän osapuolten välillä on yksi keskeisistä tie- toturvallisuuden ongelmista ja Diffie–Hellman-avaintenvaihtoprotokolla tarjoaa tähän ratkaisun.
Menetelmä esiteltiin maailmalle ensimmäisen kerran vuonna 1976, kun Whitfield Diffie ja Martin Hellman julkaisivat artikkelinNew Directions in Cryptography". Kyseessä on yksi varhaisimmista kryptografisista menetelmistä, joka hyödynsi ideaa julkisesta ja yksityisestä salausavaimesta. Me- netelmä oli aikanaan mullistava uudistus, sillä aikaisemmin salausavaimen jakaminen viestinnän osapuolten välillä oli vaatinut jonkin erillisen salatun viestintäväylän. [1]
Esitellään seuraavaksi menetelmän eteneminen kahden osapuolen välillä. Viestinnän osapuolet ovat tässä havainnollistuksessa Alice ja Bob.
1. Alice ja Bob valitsevat yhdessä suuren alkuluvun𝑝ja joukon virittäjän𝑔. Nyt siis pätee, että ℤ𝑝\{0}=⟨𝑔⟩. Protokollan laskutoimitukset tehdään ryhmässä(ℤ𝑝\{0},·𝑝).
2. Alice ja Bob valitsevat omilla tahoillaan molemmat omat kokonaislukunsa𝑎 ja𝑏joukosta ℤ𝑝\{0}. Näitä lukuja osapuolet eivät jaa toisilleen.
3. Alice laskee luvun𝐴=𝑔𝑎ja lähettää tämän Bobille.
4. Bob laskee luvun𝐵=𝑔𝑏ja lähettää tämän Alicelle.
5. Alice saa nyt yhteisen salaisen arvon laskemalla𝑠=𝐵𝑎 mod 𝑝 =𝑔𝑏 𝑎 mod 𝑝. 6. Bob saa saman salaisen arvon laskemalla𝑠 =𝐴𝑏 mod 𝑝 =𝑔𝑎 𝑏 mod 𝑝.
Huomionarvoista menetelmässä on se, että luvut 𝑝, 𝑔, 𝐴ja𝐵ovat julkisesti saatavilla myös ulko- puolisille. Kuitenkaan ilman tietoa Alicen ja Bobin salaisista luvuista𝑎tai𝑏ei ulkopuolisella ole helposti mahdollisuutta selvittää salaista arvoa 𝑠. Itse asiassa edes Alice ja Bob eivät tiedä tois- tensa salaisia lukuja. Kuvassa 3.1 on kuvattu, kuinka tieto kulkee protokollan suorituksen aikana.
Havainnollistetaan protokollan kulkua seuraavaksi yksinkertaisen esimerkin avulla.
Esimerkki 3.1.Alice ja Bob haluavat sopia keskenään salausavaimen viestiäkseen turvallisesti keskenään julkista viestintäväylää pitkin. He käyttävät salausavaimen sopimiseen Diffie–Hellman- avaintenvaihtoprotokollaa. Eve puolestaan haluaa selvittää, mitä Alice ja Bob keskenään viestivät.
Hänellä on pääsy julkisen viestintäväylän viesteihin.
Kuva 3.1.Informaation kulku Diffie–Hellman-avaintenvaihtoprotokollassa.
1. Alice päättää, että salausavaimen sopimiseen käytetään joukkoaℤ31\{0} ja tämän joukon viritävää alkiota 3. Hän lähettää luvut 𝑝 = 31 ja𝑔 = 3 Bobille. Myös Eve saa nämä luvut tietoonsa, sillä sopimus tehdään julkista viestintäväylää pitkin.
2. Alice päättää käyttää omana salaisena lukunaan alkiota𝑎 =8∈ℤ31\{0}ja Bob puolestaan alkioita𝑏=21∈ℤ31\{0}. Näitä lukuja Alice ja Bob eivät välitä toisilleen, joten myöskään Eve ei saa näitä tietoonsa.
3. Alice laskee luvun 38 mod 31=6561 mod 31=20 ja lähettää tämän Bobille. Myös Eve tietää nyt luvun 3𝑎𝑚 𝑜 𝑑31=20.
4. Bob laskee luvun 321 mod 31 = (1,0460353203·1010) mod 31 = 15 ja lähettää tämän Alicelle. Eve tietää nyt myös luvun 3𝑏 mod 31=15.
5. Alice saa salausavaimen laskemalla 158 mod 31=(2,562890625·109) mod 31=4.
6. Bob saa saman lopputuloksen laskemalla 2021 mod 31= (2.097152·1027) mod 31=4.
Koska molemmat laskevat tämän saman tuloksen omilla tahoillaan, ei Eve saa salausavainta tietoonsa.
Mainittakoon vielä, että esimerkissä 3.1 käytetyt luvut ovat kokoluokaltaan niin pieniä, ettei niillä tietenkään saavuteta minkäänlaista tietoturvaa.
Jos Eve haluaisi selvittää salausavaimen, tulisi hänen saada selville joko Alicen tai Bobin salainen luku ratkaisemalla toinen yhtälöistä
𝐴=𝑔𝑎 mod 𝑝 𝐵=𝑔𝑏 mod 𝑝 .
Toisin sanoen Even on ratkaistava diskreetin logaritmin ongelma.
4. RATKAISUALGORITMEJA
Esimerkin 3.1 mukaisilla lukuarvoilla helpoin tapa ratkaista diskreetin logaritmin ongelma on yksinkertaisesti käydä läpi kaikki mahdolliset vaihtoehdot ratkaisuiksi. Tällaista lähestymistapaa kutsutaan raa’an voiman menetelmäksi (engl. brute force). Lukujoukossaℤ𝑝\{0}vaihtoehtoja on 𝑝−1 kappaletta. Jos ratkaisu on𝑥ja vaihtoehtoja käydään läpi alusta alkaen, vaaditaan𝑥kokeilua ongelman ratkaisemiseksi.
Jos𝑝ja𝑥ovat suuria, ei diskreetin logaritmin ongelman ratkaiseminen raa’an voiman menetelmällä ole enää tehokasta. Vaikka tehokasta algoritmia ongelman ratkaisuun hyvin suurilla luvuilla ei olekaan, niin on kuitenkin olemassa menetelmiä, joiden tehokkuus ei laske aivan yhtä radikaalisti kuin raa’an voiman menetelmän. Seuraavaksi esiteltävä Shankin algoritmi on yksi näistä.
4.1 Shankin algoritmi
Shankin algoritmissa ideana on luoda kaksi listaa, joita vertaillaan keskenään. Kun listoista löy- detään sama alkio, voidaan päätellä diskreetin logaritmin ongelman ratkaisu. Seuraava algoritmi perustuu viitteeseen [4].
Lause 4.1(Shankin algoritmi).Olkoon𝑔alkio, joka virittää joukonℤ𝑝\{0}, missä𝑝on alkuluku.
Seuraava algoritmi ratkaisee diskreetin logaritmin ongelman.
1. Olkoon𝑛=1+ ⌊√︁
𝑝−1⌋. Nyt 𝑛 >√︁
𝑝−1. 2. Lasketaan aputermi𝑢 =(𝑔−1)𝑛.
3. Luodaan kaksi listaa,
Lista 1: 1, 𝑔, 𝑔2, 𝑔3, . . . , 𝑔𝑛
Lista 2: ℎ, ℎ·𝑝𝑢, ℎ·𝑝𝑢2, ℎ·𝑝𝑢3, . . . , ℎ·𝑝𝑢𝑛.
4. Listoista etsitään alkio𝑔𝑖 =ℎ·𝑝𝑢𝑗 =ℎ·𝑝𝑔−𝑗 𝑛, joka esiintyy molemmissa listoissa.
5. Yhtälön𝑔𝑥 =ℎratkaisu on𝑥=𝑖+ 𝑗 𝑛.
Todistus. Näytetään ensin, että𝑥 =𝑖+ 𝑗 𝑛todella on yhtälön𝑔𝑥 =ℎratkaisu. Kerrotaan yhtälö 𝑔𝑖 =ℎ·𝑝𝑔−𝑗 𝑛
puolittain termillä𝑔𝑗 𝑛. Nyt saadaan
𝑔𝑖+𝑗 𝑛=ℎ·𝑝𝑔−𝑗 𝑛+𝑗 𝑛⇐⇒𝑔𝑖+𝑗 𝑛=ℎ·𝑝1⇐⇒𝑔𝑖+𝑗 𝑛=ℎ.
On vielä näytettävä, että listoissa on aina yksi sama alkio. Oletetaan, että 𝑥 = 𝑛𝑞 +𝑟, missä 0≤𝑟 < 𝑛, on ratkaisu. Tiedämme, että 0≤ 𝑥 < 𝑝−2. Voimme nyt arvioida lukua𝑞seuraavasti
𝑞 = 𝑥−𝑟 𝑛
<
𝑝−1 𝑛
< 𝑛, koska𝑛 >
√︁
𝑝−1. Niinpä yhtälö𝑔𝑥 =ℎvoidaan kirjoittaa uudelleen muodossa
𝑔𝑟 =ℎ𝑔−𝑞 𝑛,missä 0≤𝑟 < 𝑛 ja 0≤𝑞 < 𝑛.
Termi𝑔𝑟 löytyy listasta 1 ja termi ℎ𝑔−𝑞 𝑛 puolestaan on listassa 2. Nyt on näytetty, että listoista löytyy sama alkio, joka on myös ratkaisu diskreetin logaritmin ongelmaan.
Havainnollistetaan seuraavaksi protokollan etenemistä ratkaisemalla esimerkin 3.1 Bobin salainen luku𝑏niillä tiedoilla, jotka Evellä on käytettävissään.
Esimerkki 4.2.Käytetään esimerkin 3.1 arvoja: 𝑝=31, 𝑔 =3 ja 𝐵=15. Jotta Eve saisi selville Bobin salaisen luvun𝑏, on ratkaistava yhtälö
3𝑏 mod 31=15. Käytetään tämän ongelman ratkaisuun Shankin algoritmia.
1. 𝑛=1+ ⌊√
31−1⌋ =6.
2. Koska(3·21) mod 31=1, niin 3−1=21 ja edelleen𝑢=216 mod 31=2.
3. Luodaan kaksi listaa, kuten lauseessa 4.1.
Lista 1: 1,3,9,27,19,26,16 Lista 2: 15,30,29,27,23,15,30 4. Huomataan, että 33 mod 31=20·23 mod 31=27.
5. Yhtälön 3𝑏 mod 31=15 ratkaisu ja Bobin salainen luku on siis𝑏=3+3·6=21.
Pienillä𝑝:n arvoilla Shankin algoritmi voi vaikuttaa turhan monimutkaiselta ja näin pienillä arvoilla suora raa’an voiman menetelmä voikin olla helpompi tapa ongelman ratkaisuun. Seuraavaksi tarkastellaankin, kuinka Shankin algoritmin ja suoran raa’an voiman menetelmän tehokkuus ja aikavaativuudet muuttuvat, kun käytetään suurempia alkulukuja.
4.2 Algoritmin tehokkuus
Myös Shankin algoritmin voidaan tulkita olevan raa’an voiman menetelmä, sillä sekin perustuu yri- tyksen ja erehdykseen periaatteeseen kahta listaa vertailtaessa. Listojen muodostaminen kuitenkin vähentää varsinkin suurilla lukuarvoilla tehtävien vertailujen määrää merkittävästi. Seuraava esi- merkki havainnollistaa, kuinka tehokkaasti Shankin algoritmi toimii verrattuna perinteiseen raa’an voiman menetelmään.
Esimerkki 4.3.Ratkaistaan yhtälö𝑔𝑥𝑖
𝑖 mod 𝑝𝑖 =2021 ryhmässä(ℤ𝑝𝑖,·𝑝𝑖), missä𝑝𝑖on alkuluku ja𝑔𝑖on joukonℤ𝑝𝑖\{0}virittävä alkio. Ratkaistaan yhtälö eri𝑝𝑖:n arvolla sekä Shankin algoritmilla että suoralla raa’an voiman menetelmällä. Ratkaisu on toteutettu Python-koodilla, joka on viitteenä [7]. Tulokset on esitetty taulukossa 4.1. Suoritusajat on pyöristetty kahden merkitsevän numeron tarkkuudella.
𝑖 𝑝𝑖 𝑔𝑖 𝑥𝑖 Shankin algoritmin Raa’an voiman -menetelmän
suoritusaika (s) suoritusaika (s)
1 331777 5 89915 0,0 0,0380
2 16785407 5 4159559 0,0020 1,7
3 54018521 6 52814438 0,0080 22
4 214748357 2 90416415 0,016 39
5 342999977 3 288003140 0,026 120
6 788748341 2 609223441 0,045 280
7 988748323 3 541404917 0,051 260
8 2147483647 7 1286479102 0,11 790
9 4347483557 5 2268351673 0,16 1600
10 6547483043 2 2679532724 0,21 1800
11 8547483037 2 3486890432 0,26 2300
12 16148168401 22 12102700812 0,45 >7200
Taulukko 4.1.Shankin algoritmin ja raa’an voiman menetelmän vertailu.
Vertailusta huomataan, että Shankin algoritmin ja raa’an voiman menetelmän suoritusajat ovat lähellä toisiaan oikeastaan vain vertailun pienimmällä arvolla. Muuten Shankin algoritmi on monta kertaluokkaa tehokkaampi kuin raa’an voiman menetelmä. Huomionarvoista on myös se, että Shankin algoritmin suoritusaika ei kasva lineaarisesti kuten raa’an voiman menetelmän suoritusaika lukuarvojen kasvaessa.
Kun tarkastellaan algoritmien tehokkuutta, voidaan hyödyntää asymptoottista suoritusaikaa, joka kuvaa sitä, kuinka algoritmin suoritusaika muuttuu syötteen koon funktiona. Tarkastellaan erityi- sesti nyt algoritmin suoritusajan ylärajaa.[4]
Määritelmä 4.4.Olkoot 𝑓(𝑥)ja𝑔(𝑥)funktioita, jotka käsittelevät positiivisia lukuja. Merkitään 𝑓(𝑥) =O (𝑔(𝑥)),
jos on olemassa sellaiset positiiviset luvut𝑐ja𝐶, että
𝑓(𝑥) ≤𝑐𝑔(𝑥)aina, kun𝑥 ≥𝐶 .
O-notaatio merkitsee siis ylärajaa algoritmin suoritusajalle. Yksi mielekäs tapa tutkia algoritmien asymptoottista suoritusaikaa, on tarkastella vaadittavien laskutoimitusten lukumäärää.
Esimerkissä 4.3 todettiin, että raa’an voiman menetelmän suoritusaika vaikutti nousevan lineaari- sesti. Menetelmässä muodostetaan listaa arvoista𝑔𝑥 mod 𝑝, missä𝑥 =1,2,3, . . . , 𝑝−1. Listan alkiot voidaan muodostaa laskemalla edellisen alkion ja alkion 𝑔 modulaarinen tulo. Diskreetin logaritmin ongelman ratkaisu löytyy listasta, joten laskutoimituksia on tehtävä korkeintaan 𝑝−1 kappaletta. Raa’an voiman menetelmän aikavaativuus diskreetin logaritmin ongelman ratkaisuun ryhmässä(ℤ𝑝\{0},·𝑝)on siisO (𝑁), missä𝑁 = 𝑝−1.
Shankin algoritmin tehokkuudelle suurilla 𝑝:n arvoilla saadaan selitys, kun tarkastellaan sen asymptoottista suoritusaikaa. Shankin algoritmissa luodaan kaksi lukujoukkoa, joissa molem- missa on𝑛kappaletta alkioita, missä𝑛=1+ ⌊√︁
𝑝−1⌋. Joukkojen muodostamiseen vaaditaan 2𝑛 askelta. Muodostamisen aikavaativuus on siis O (√
𝑁), missä 𝑁 = 𝑝 −1. Todellisuudessa toista joukkoa ei tarvitse muodostaa kokonaan, vaan sen arvoja voidaan verrata ensimmäisen joukon arvoihin samaan aikaan, kun niitä lasketaan.
Alkion etsiminen lukujoukosta on vakioaikainen operaatio, kun valitaan sopiva tietorakenne. Va- kioaikaiselle algoritmille päteeO (1), eli suoritusaika ei muutu syötteen koon funktiona. Tällainen tietorakenne on esimerkiksi hajautustaulu (engl. hash table), jota on hyödynnetty myös viitteenä olevassa Shankin algoritmin toteutuksessa [7]. Tämä vaihe ei siis muuta algoritmin asymptoottis- ta suoritusaikaa. Niinpä koko algoritmin aikavaativuudeksi tuleeO (√
𝑁). Tämä on huomattavasti nopeampi kuin raa’an voiman menetelmän vastaava luku ja tämä ero selittää sen, miksi Shankin algoritmi on tehokkaampi.
Toinen kryptografiassa yleisesti käytetty tapa ilmoittaa algoritmin aikavaativuus on bittien avulla.
Tämä on varsin mielekäs tapa kuvata aikavaativuutta, sillä bitit ovat tietotekniikan perusyksikkö ja siten myös perusyksikkö kuvaamaan käytettyjen lukujen suuruutta. Raa’an voiman menetelmän aikavaativuusO (𝑁)on bitteinäO (2𝑘), missä𝑘on luvun𝑝koko bitteinä. Shankin algoritmin aika- vaativuus O (𝑁) on vastaavastiO (2𝑘/2).[1] Molempien ratkaisutapojen aikavaativuus siis kasvaa lopulta eksponentiaalisesti. Niinpä kun käytetään tarpeeksi suuria lukuja, ei Shankin algoritmikaan ole enää tehokas tapa diskreetin logaritmin ongelman ratkaisuun.
5. YHTEENVETO
Diffie–Hellman-avaintenvaihtoprotokolla on ratkaisu yhteen tietoturvallisuuden keskeisimmistä ongelmista, eli siihen kuinka käytettävä salausavain voidaan jakaa turvallisesti. Sen avulla salausa- vaimen vaihto ei vaadi omaa erillistä salattua kanavaansa, vaan jakaminen voidaan suorittaa julkista viestintäväylää pitkin. Menetelmän taustalla on rakenne, jonka muodostavat lukujoukkoℤ𝑝\{0}, eli kokonaisluvut modulo 𝑝 ja laskutoimitus, jota kutsutaan modulaariseksi tuloksi·𝑝. Tämä ra- kenne on esimerkki syklisestä ryhmästä, eli koko lukujoukko voidaan virittää yhden joukon alkion potenssien avulla.
Rakenteen syklisyys mahdollistaa diskreetin logaritmin määrittelemisen. Diskreetin logaritmin löy- täminen on hyvin vaikea ongelma, jonka ratkaisuun ei ole olemassa tehokasta keinoa, kun käytetään suuria lukuja. Tämä vaikeasti ratkaistava ongelma luo Diffie–Hellman-avaintenvaihtoprotokollan turvallisuuden. Kuitenkin diskreetin logaritmin käänteisen operaation suorittaminen on helppoa myös suurilla luvuilla. Diskreetti logaritmi soveltuu siis erittäin hyvin salaustarkoitukseen, sillä sa- laus on helppo toteuttaa, mutta salaukseen käytettyä arvoa on hyvin vaikea selvittää lopputuloksen perusteella.
Vaikka diskreetin logaritmin ongelman ratkaisuun ei olekaan olemassa tarpeeksi tehokasta me- netelmää, on kuitenkin olemassa tehokkaampia algoritmeja kuin puhdas yritykseen ja erehdyk- seen perustuva menetelmä, joka tunnetaan raa’an voiman menetelmänä. Yksi tällainen algoritmi on Shankin algoritmi. Shankin algoritmin asymptoottinen suoritusaika onO (√
𝑁)=O (2𝑘/2), kun taas perinteisen raa’an voiman menetelmän suoritusaika kasvaa lineaarisesti, kun salaukseen käytettävä alkuluku kasvaa. Raa’an voiman menetelmän asymptoottinen suoritusaika on siisO (𝑁)=O (2𝑘). Käytännössä tämä tarkoittaa sitä, että raa’an voiman menetelmää hidastuu huomattavasti nopeam- min kuin Shankin algoritmi, mutta molemmat hidastuvat lopulta eksponentiaalisesti käytettäessä suuria lukuja.
Esimerkissä 4.3 huomattiin, että sopivilla tietorakennevalinnoilla toteutettuna Shankin algoritmi on moninkertaisesti tehokkaampi tapa ratkaista diskreetin logaritmin ongelma. Algoritmi ratkaisi itse asiassa kaikki 12 testitapausta nopeammin kuin raa’an voiman menetelmä ratkaisi vain kaksi ensimmäistä tapausta.
Diffie–Hellman-avaintenvaihtoprotokolla on tehokas tapa salausavaimen vaihtoon niin kauan, kun- nes mahdollisesti kehitetään tehokkaampi ratkaisukeino diskreetin logaritmin ongelmaan. Toistai- seksi ei ole varmuutta siitä, kuinka vaikea diskreetin logaritmin ongelma lopulta on ja onko edes mahdollista muodostaa algoritmia, joka ei hidastuisi eksponentiaalisesti.
LÄHTEET
[1] W. Diffie ja M. Hellman. New directions in cryptography. eng.IEEE transactions on infor- mation theory22.6 (1976), 644–654. issn: 0018-9448.
[2] M. R. Dixon, M. R. Dixon, L. A. Kurdachenko ja I. Y. Subbotin.An introduction to essential algebraic structures. eng. Somerset: WILEY, 2014. isbn: 1118497767.
[3] G. W. Effinger.An elementary transition to abstract mathematics. eng. Textbooks in mathe- matics. Boca Raton: CRC Press, Taylor Francis Group. isbn: 9781000701814.
[4] J. Hoffstein, J. Pipher ja J. H. Silverman.An Introduction to Mathematical Cryptography. eng. Undergraduate texts in mathematics. New York, NY: Springer New York, 2014. isbn:
9780387779935.
[5] R. Merkle. Secure communications over insecure channels. eng.Communications of the ACM 21.4 (1978), 294–299. issn: 0001-0782.
[6] D. J. S. Robinson.Abstract Algebra: An Introduction with Applications. eng. De Gruyter Textbook. Berlin/Boston: De Gruyter, Inc, 2015. isbn: 9783110340860.
[7] Shankin algoritmin ja raa’an voiman menetelmän toteutus. 2021. url: https://github.
com/jrmcinnen/discrete_logarithm_problem(viitattu 24. 03. 2021).
[8] D. Shanks.Solved and unsolved problems in number theory. eng. 4. ed. Providence (R.I.):
AMS Chelsea, 2001. isbn: 0-8218-2824-X.
