Diffie–Hellman

Syyskuussa 1974 kun ARPANET oli vielä alkutekijöissään Whitfield Diffie ja Martin Hellman tapasivat keskustellakseen avaintenvaihtomenetelmästä. Avaintenvaihto oli pulma, josta ei näyttänyt pääsevän ympäri ilman avaimen paljastamista jossakin vaiheessa. Ralph Merkle liittyi mukaan työhön. He keskittyivät tutkimaan yksisuuntaisia matemaattisia funktioita. Kahden vuoden työn jälkeen keväällä 1976 Hellman sai läpimurron. Diffie-Hellman-Merkle avaintenvaihto esiteltiin kesäkuussa 1976 National Computer Conferencessa ja seuraavana vuonna he hakivat patenttia.^[1][2][3] Samaan aikaan Diffie sai ajatuksen epäsymmetrisen avaimen käytöstä, joka johti julkisen avaimen salaukseen.^[1]

Alkuperäisessä ja yksinkertaisimmassa muodossaan protokolla käyttää kokonaislukujen jäännösluokkarenkaan multiplikatiivista ryhmää modulo jokin alkuluku p ja sen primitiivistä alkiota g.

Esimerkki protokollasta:

1. Liisa ja Roope sopivat käyttävänsä alkulukua p=23 ja primitiivistä alkiota g=5.
2. Liisa valitsee salaisen kokonaisluvun a=6, ja lähettää Roopelle luvun (g^a mod p)
   • 5⁶ mod 23 = 8.
3. Roope valitsee salaisen kokonaisluvun b=15 ja lähettää Liisalle luvun (g^b mod p)
   • 5¹⁵ mod 23 = 19.
4. Liisa laskee luvun (g^b mod p)^a mod p
   • 19⁶ mod 23 = 2.
5. Roope laskee luvun (g^a mod p)^b mod p
   • 8¹⁵ mod 23 = 2.

Liisa ja Roope ovat nyt saaneet saman luvun, koska g^ab ja g^ba ovat yhtäsuuret. Huomattakoon, että ainoastaan luvut a, b, g^ab ja g^ba ovat salassa pidettäviä. Kaikki muut luvut voidaan lähettää selväkielisinä. Kun Liisa ja Roope ovat saaneet näin vaihdettua salaiset avaimet, he voivat käyttää niitä avoimessa tietoliikennekanavassa tapahtuvan keskinäisen viestintänsä salaamiseen.

Todellisessa tilanteessa tulisi tietysti valita luvut a, b ja p huomattavasti suuremmiksi. Jos alkuluku p olisi yli 300 numeroinen ja luvut a ja b vähintään 100 numeroisia lukuja, parhailtakin tunnetuilta (diskreetin logaritmin) algoritmeilta kuluisi vähintään tunnetun maailmankaikkeuden iän verran aikaa lukujen a ja b laskemiseen tunnettujen lukujen g, p, g^a mod p ja g^b mod p perusteella. Luvun g ei välttämättä tarvitse olla kovin suuri. Itse asiassa luvut 2 tai 5 ovat tavallisia valintoja.

1. Liisa ja Roope sopivat käytettävästä äärellisestä syklisestä ryhmästä G ja sen generoivasta alkiosta g. (Tämä tehdään yleensä paljon ennen protokollan käyttötapahtumaa; Alkion g oletetaan olevan mahdollisten hyökkääjien tiedossa.) Käytämme ryhmän G laskutoimitukselle multiplikatiivista merkintätapaa (ts. kertomerkkiä).
2. Liisa valitsee satunnaisen luonnollisen luvun a ja laskee ryhmän G alkion g^a, jonka hän lähettää Roopelle.
3. Roope valitsee satunnaisen luonnollisen luvun b ja laskee ryhmän G alkion g^b, jonka hän lähettää Liisalle.
4. Liisa laskee ryhmän G alkion (g^b)^a.
5. Roope laskee ryhmän G alkion (g^a)^b.

Sekä Liisa, että Roope tietävät nyt ryhmän alkion g^ab, joka toimii heidän salaisena avaimenaan. Ryhmän G alkiot (g^b)^a ja (g^a)^b ovat keskenään yhtäsuuret, koska ryhmät ovat potenssiassosiatiivisia.

Operaatiot tehdään oikeasti hyvin valituilla äärellisiin eli Galois’n kuntiin kuuluvilla arvoilla ja operaatioilla, jolloin saadaan erityisen helposti laskettavat eksponenttioperaatiot ja vaikeasti laskettavat diskreetit logaritmioperaatiot. Yksinkertaistaen tämä tarkoittaa vain sitä, että luvut katkaistaan tiettyyn pituuteen. Ollakseen turvallinen, Diffie–Hellman-algoritmissa käytettävien lukujen pitää olla hyvin pitkiä, tuhansia bittejä eli satoja numeroita.

Kukaan ei ole todistanut sitä, ettei ole olemassa keinoa laskea logaritmeja paljon nykyistä tehokkaammin. Jonain päivänä nyt varmana pidetty Diffie–Hellman-avain voikin murtua helposti.

Diffie–Hellman-algoritmin suuri ongelma on se, ettei vastapuolta todenneta. Tämä mahdollistaa jonkun toimimisen Roopen ja Liisan välissä. Sen sijaan, että Roope on sopinut salaisuuden Liisan kanssa, hän onkin sopinut sen Villen kanssa. Ville tekee myös tämän saman Liisalle. Kun Roope ja Liisa kuvittelevat sopineensa salaisuuden keskenään ja alkavat salatun tiedonsiirron, kaikki kulkeekin selväkielisenä Villen kautta. Tätä kutsutaan mies välissä -hyökkäykseksi (engl. man-in-the-middle attack).

Algoritmi edellyttää myös ulkopuoliselle täysin arvaamattomien satunnaislukujen käyttöä. Tällaisten tekeminen on usein yllättävän vaikeaa pelkän tietokoneen avulla.

Vuonna 2015 raportoitiin Logjam-hyökkäyksestä, joka hyödyntää Diffie–Hellmanissa olevaa haavoittuvuutta.^[4][5]

• RFC 2631 Diffie–Hellman Key Agreement Method
• RFC 3526 More Modular Exponential (MODP) Diffie–Hellman groups for Internet Key Exchange (IKE)

• "Public Key Cryptography: Diffie-Hellman Key Exchange" – Khan Academy (englanniksi)
• U.S. Patent #4,200,770^{[vanhentunut linkki]} , Alkuperäinen patentti (Diffie, Hellman ja Merkle), ei enää voimassa
• Summary of ANSI X9.42: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography^{[vanhentunut linkki]} ANSI X9.42 standardi (PDF)