Diffie–Hellman-avaintenvaihtoprotokolla ja diskreetin logaritmin ongelma

Abstract

Diffie–Hellman-avaintenvaihtoprotokolla on menetelmä, jolla kaksi viestinnän osapuolta voivat sopia yhteisestä salausavaimesta julkista viestintäväylää pitkin. Salausavaimen sopiminen ja jakaminen viestinnän osapuolten välillä on yksi keskeisistä tietoturvallisuuden ongelmista ja Diffie–Hellman-avaintenvaihtoprotokolla tarjoaa tähän ratkaisun. Työssä tarkastellaan matemaattisia rakenteita protokollan taustalla ja erityisesti diskreetin logaritmin ongelmaa, joka on menetelmän tietoturvallisuuden 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älle voidaan löytää virittävä alkio, jonka potenssien avulla voidaan esittää kaikki ryhmän lukujoukon alkiot. 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 tehokkaampi kuin suoraviivainen yritykseen ja erehdykseen perustuva raa’an voiman menetelmä. Shankin algoritmin aikavaativuus on O (sqrt(N)), kun taas raa’an voiman menetelmälle pätee O (N). 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 algoritmin aikavaativuus O (2^k/2) ja raa’an voiman menetelmän O (2^k). Molemmat menetelmät hidastuvat siis lopulta eksponentiaalisesti. Diffie–Hellman-avaintenvaihtoprotokolla on turvallinen, kunnes kehitetään algoritmi, joka ei hidastu näin jyrkästi.