1. CS-EJ4404
  2. 8. Julkisen avaimen menetelmät
  3. 8.3 Diffie–Hellman

Diffie–Hellman

Tämä osio ei ole kovin pitkä, mutta asia vaatii keskittymistä. Saamme hyvän annoksen matematiikkaa ja mikä tärkeintä, ymmärrämme miten matematiikkaa voi suoraan käyttää jaetun salaisuuden luomisessa.

Diffie–Hellman-protokollan tavoite on neuvotella osapuolille A ja B sama jaettu salaisuus. Käytännössä jaettu salaisuus on yleensä käytännössä salainen bittikuvio eli luku.

Tavoitteena on, että osapuolten A ja B välistä kommunikaatiota salakuunteleva C ei pysty selvittämään tätä salaista bittikuviota. Käytetään osapuolista A, B ja C nimiä Alice, Bob ja Carol, kuten tähänkin asti.

Osapuolet eivät oikeassa maailmassa ole välttämättä henkilöitä. A, B ja C voivat olla myös esimerkiksi yrityksiä, instituutioita tai valtioita. Tällöin käyttämiemme nimien Alicen, Bobin ja Carolin sijasta osapuolet voisivat olla esimerkiksi valtio A, valtio B ja valtio C.

Diffie–Hellman-protokollassa hyödynnämme edelleen aiemmin oppimiamme potenssiin korotuksia ja moduloaritmetiikkaa.

Parametrit ja syklinen ryhmä

Epäsymmetrisissä menetelmissä käytetään usein parametreja, jotka määrittävät matemaattisen avaruuden toimintaehdot. Käytettävät parametrit eivät ole salaisuus, toisin kuin salaiset avaimet tai jaettu salaisuus.

Aluksi Alice ja Bob neuvottelevat yhteiset parametrit: alkuluvun \(p\) ja generaattori-luvun \(g\), jonka potenssit \(g^1, g^2, \ldots, g^{p-1}\) modulo \(p\) antavat kaikki luvut väliltä \([1,p-1]\). Tällöin \(g\) on ns. syklisen ryhmän generoiva alkio. Esimerkiksi jos \(p=11\), voidaan valita \(g=2\), sillä

\[\begin{split}\begin{align*} g^{1} \pmod{11} &= 2 \\ g^{2} \pmod{11} &= 4 \\ g^{3} \pmod{11} &= 8 \\ g^{4} \pmod{11} &= 5 \\ g^{5} \pmod{11} &= 10 \\ g^{6} \pmod{11} &= 9 \\ g^{7} \pmod{11} &= 7 \\ g^{8} \pmod{11} &= 3 \\ g^{9} \pmod{11} &= 6 \\ g^{10} \pmod{11} &= 1 \end{align*}\end{split}\]

Käytännössä parametereinä käytetään huomattavasti suurempia lukuja (esim. 3072-bittisiä lukuja). Käytämme esimerkeissä pieniä lukuja, jotta esimerkit on helpompi hahmottaa.

Yllä on selitetty DH-protokollan osapuolia ja parametrejä.

Jaettu salaisuus on:

Valitse oikea vaihtoehto.

Diffie–Hellman-avainten luominen

Kun luomme Diffie–Hellman-avaimia, valitsemme ensin parametrit, jotka eivät ole salaisia. Valitaan parametreiksi alkuluku \(p=211\) ja generaattori \(g=2\). Nämä \(p\) ja \(g\) ovat siis menetelmämme parametreja, eivät avaimia.

dhsalainen

  • Alice valitsee satunnaisesti luvun, joka on hänen salainen avain \(X_A\) .

  • Tämä luku on väliltä \([1,p-1]\).

  • Olkoon tämä salainen avain nyt \(X_A = 174\).

dhjulkinen

  • Seuraavaksi Alice laskee julkisen avaimen \(Y_A\).

  • Julkinen avain lasketaan salaisesta avaimesta \(X_A\) parametreilla \(p\) ja \(g\).

  • Julkisen avaimen laskenta toteutetaan yhtälöllä \(Y_A = g^{X_A} \pmod{p}\).

  • Yhtälöön sijoittamalla valitsemamme salaisen avaimen \(X_A = 174\) saamme julkisen avaimen laskemalla \(Y_A = 2^{174} \pmod{211} = 113\).

  • Tämä on Alicen salaisesta avaimesta \(X_A = 174\) laskettu julkinen avain \(Y_A = 113\).

Nyt Alice on laskenut itselleen avainparin \((X_A,Y_A)\), jossa \(X_A\) on salainen avain ja \(Y_A\) on julkinen avain.

Tehdään sama laskenta vielä Pythonilla. Käytämme laskennassa aiemmin esiteltyä modulo_potenssiin funktiota.

Inactive
# Tuodaan sama funktio joka tehtiin edellisellä kerralla
# Funktion modulo_potenssiin argumentit (kanta, eksponentti, modulus)
from xip import modulo_potenssiin

# Sovitut parametrit, jotka eivät ole salaisuuksia
p = 211
g = 2

# Alice luo DH avainparin salaisen avaimen
x_a = 174

# Alice laskee DH avainparin julkisen avaimen (g**x_a) % p
y_a = modulo_potenssiin(kanta=g, eksponentti=x_a, modulus=p)

print("Alice on luonut Diffie-Hellman avainparin parametreilla p={} ja g={}".format(p,g))
print("Alice on valinnut SALAISEKSI avaimeksi:", x_a)
print("Alice on laskenut JULKISEKSI avaimeksi:", y_a)

Tämän tehtävän tekemiseen joudut muokkaamaan edellistä koodisolua.

Bob käyttää parametreja \(p=211\) ja \(g=2\) luodessaan avainparin. Hän valitsee salaiseksi avaimekseen \(X_B\) luvun 1313. Valitse oikeat vaihtoehdot.

Bob vaihtaa parametrin \(p\) arvoon \(p=883\). Valitse oikeat väittämät.

Diskreetin logaritmin ongelma

Esimerkissämme käytimme pieniä lukuja, joten valituilla arvoilla salainen avain \(X_A\) olisi tietysti helppo selvittää, jos tiedetään \(Y_A\), \(g\) ja \(p\).

Yleisesti salaisen avaimen selvittäminen on hyvin vaikea laskentaongelma ratkaistavaksi, kun salainen avain on suuri luku.

Tätä laskentaongelmaa kutsutaan nimellä diskreetin logaritmin ongelma (DL).

Tällä hetkellä DL-ongelma on onnistuttu ratkaisemaan 240-numeroisilla (eli 795-bittisillä) luvuilla.

Klassiseen DL-ongelmaan nojautuvassa kryptografiassa suositellaan käytettävän vähintään 3072-bittisiä parametrejä, joilla uskotaan saavutettavan 128 bitin turvataso.

Jaettu salaisuus Diffie–Hellman-protokollalla

Nyt esittelemme Diffie–Hellman-protokollan suolan, eli jaetun salaisuuden muodostamisen.

Katsomme sekä numeroilla että kaavoilla, kuinka Alice ja Bob voivat luoda jaetun salaisuuden. Alice ja Bob jakavat toisilleen julkiset avaimet sähköpostitse. Tämän jälkeen Alice ja Bob aloittavat tahoillaan jaetun salaisuuden laskemisen.

DH-protokolla etenee seuraavasti:

  1. Alicella on avainpari (\(X_A = 174\), \(Y_A = 113\)).

  2. Alice ja Bob käyttävät samoja parametreja \(p = 211\) ja \(g = 2\).

  3. Bob laskee itselleen avainparin (\(X_B\), \(Y_B\)). Olkoon nämä nyt salainen avain \(X_B = 199\) ja siitä laskettu julkinen avain \(Y_B = 17\).

  4. Alice ja Bob pitävät omat salaiset avaimet (\(X_A\) ja \(X_B\)) itsellään ja lähettävät julkiset avaimet (\(Y_A\) ja \(Y_B\)) toisilleen.

  5. Seuraavaksi Alice yhdistää oman salaisen avaimensa \(X_A\) ja Bobin julkisen avaimen \(Y_B\) laskemalla \(K_A = Y_B^{X_A} \pmod{p}\) eli \(K_A = 17^{174} \pmod{211} = 125\).

  6. Bob toimii vastaavasti ja laskee \(K_B = Y_A^{X_B} \pmod{p}\) ja saa \(K_B = 113^{199} \pmod{211} = 125\).

  7. Huomataan, että \(K_A = K_B = 125\) !!!

Alice ja Bob ovat saaneet tulokseksi saman salaisen jaetun luvun, jota muut eivät tiedä. Tämä luku on heidän jaettu salaisuus.

Miten kumpikin osapuoli päätyi samaan lukuun? Tarkistetaan laskenta matemaattisesti. Kirjoitetaan osapuolten A ja B suorittamat laskut auki:

\[\begin{split}\begin{align*} K_A &= Y_B^{X_A} = (g^{X_B})^{X_A} = g^{X_A X_B} \\ K_B &= Y_A^{X_B} = (g^{X_A})^{X_B} = g^{X_A X_B} \end{align*}\end{split}\]

Yhtälöistä nähdään, kuinka protokolla tuottaa molemmille osapuolille saman arvon. Tämä on jaettu salaisuus.

Tarkastellaan toimintaa Python-koodilla.

Inactive
from xip import modulo_potenssiin

# Sovitut parametrit, jotka eivät ole salaisuuksia
p = 211
g = 2

# Alicen salainen avain x_a
x_a = 174
# Bobin salainen afvain x_b
x_b = 199

# Alice laskee DH avainparin julkisen avaimen (g**x_a) % p
y_a = modulo_potenssiin(kanta=g, eksponentti=x_a, modulus=p)
print("Alice on luonut Diffie-Hellman avainparin parametreilla p={} ja g={}".format(p,g))
print("Alice on valinnut SALAISEKSI avaimeksi:", x_a)
print("Alice on laskenut JULKISEKSI avaimeksi:", y_a)

# Bob laskee DH avainparin julkisen avaimen
y_b = modulo_potenssiin(kanta=g, eksponentti=x_b, modulus=p)
print("Bob on luonut Diffie-Hellman avainparin parametreilla p={} ja g={}".format(p,g))
print("Bob on valinnut SALAISEKSI avaimeksi:", x_b)
print("Bob on laskenut JULKISEKSI avaimeksi:", y_b)

# Tässä välissä Alice lähettää Bobille julkisen avaimen y_a
print("Alice ja Bob lähettävät toisilleen julkiset avaimensa")

# Alice laskee jaetun salaisuuden käyttämällä bobin julkista avainta ja omaa salista avainta
k_a = modulo_potenssiin(kanta=y_b, eksponentti=x_a, modulus=p)

# Bob laskee tahollaan jaetun salaisuden samalla tavalla
k_b = modulo_potenssiin(kanta=y_a, eksponentti=x_b, modulus=p)

print("Alicen laskema jaettu salaisuus on:", k_a)
print("Bobin  laskema jaettu salaisuus on:", k_b)

if k_a == k_b:
    print("Jaetun salaisuuden laskeminen onnistui")
else:
    print("Nyt on jotain pielessä, joko Alice tai Bob voi ollakin Carol?")

Voiko joku selvittää Alicen ja Bobin yhteisen salaisuuden?

Kuvitellaan, että taho C, tässä tapauksessa siis Carol, haluaa selvittää Alicen ja Bobin jaetun salaisuuden eli salaisen luvun. Tarkastellaan, miksi Carol ei pysty selvittämään Alicen ja Bobin salaista lukua?

  • Oletetaan, että Carol on saanut tietoonsa parametrit \(p\) ja \(g\). Nämähän eivät ole salaisuuksia.

  • Oletetaan Carolin saaneet haltuunsa lisäksi myös molempien osapuolten julkiset avaimet \(Y_A\) ja \(Y_B\).

  • Carol voi yrittää selvittää julkisilla avaimilla salaisen luvun laskemalla \(K_A\) ja \(K_B\).

  • Jos luvut kerrotaan keskenään, saadaan \(Y_A \cdot Y_B = g^{X_A} \cdot g^{X_B} = g^{X_A + X_B}\). Tämä ei ole haluttu arvo \(g^{X_A \cdot X_B}\).

  • Jotta Carol voisi laskemalla selvittää Alicen ja Bobin salaisen luvun, jossa \(K_A=K_B\), hänen pitäisi selvittää joko salainen avain \(X_A\) julkisesta avaimesta \(Y_A\) tai salainen avain \(X_B\) julkisesta avaimesta \(Y_B\). Tämä on käytännössä mahdotonta, jos parametrit on valittu oikein ja käytetään suuria lukuja.

Englannin termi man-in-the-middle (MITM) kuvaa hyökkäystapaa, jossa kolmas osapuoli pyrkii kahden viestivän tahon väliin. MITM olisi esimerkkimme yhteydessä Carol. Tällöin Carol näyttelee Alicen roolia Bobille ja Bobin roolia Alicelle, eli on viestintäkanavan välissä aktiivisena toimijana.

Testataan Python-koodilla käytännössä, onnistuuko yhteisen salaisuuden \(g^{X_A \cdot X_B}\) selvittäminen, jos sekä julkiset avaimet \(Y_A\) ja \(Y_B\) että käytetyt parametrit on selvitetty.

Inactive
from xip import modulo_potenssiin

# Asetetaan sovitut parametrit, jotka eivät ole salaisuuksia
p = 211
g = 2

# Valitaan salaiset avaimet (Alicen x_a, Bobin x_b)
x_a = 174
x_b = 199

# Lasketaan julkiset avaimet (Alicen y_a, Bobin y_b)
y_a = modulo_potenssiin(kanta=g, eksponentti=x_a, modulus=p)
y_b = modulo_potenssiin(kanta=g, eksponentti=x_b, modulus=p)

# Lasketaan oikea jaettu salaisuus k
k = modulo_potenssiin(kanta=y_b, eksponentti=x_a, modulus=p)
print("Oikea jaettu salaisuus:", k)

# Carol yrittää selvittää salaisen luvun laskemalla kolmella tavalla.

# Carol yrittää kertoa julkiset avaimet keskenään (modulo p)
k_julkisista = (y_a*y_b) % p
# Carol yrittää laskea salaisen luvun Alicen julkisesta avaimesta
k_dh_julkisista_a = modulo_potenssiin(kanta=y_b, eksponentti=y_a, modulus=p)
# Carol yrittää laskea salaisen luvun Bobin julkisesta avaimesta
k_dh_julkisista_b = modulo_potenssiin(kanta=y_a, eksponentti=y_b, modulus=p)

print("Carolin julkisista avaimista laskemat jaetut salaisuudet:")
print("Kertolasku:", k_julkisista)
print("Potenssi a:", k_dh_julkisista_a)
print("Potenssi b:", k_dh_julkisista_b)

# Jos jokin laskentatavoista tuottaa oikean tuloksen, on salaisuus murtunut
salaisuus_murrettu = (k == k_julkisista) or (k == k_dh_julkisista_a) or (k == k_dh_julkisista_a)

if not salaisuus_murrettu:
    print("Jaetun salaisuuden säilyttäminen onnistui")
else:
    print("Nyt on jotain pielessä, salaisuus paljastui!")

Mitä Diffie–Hellman-protokollalla saavutetaan?

On huomionarvoista, että yllä olevassa protokollassa ei varsinaisesti salattu mitään, eikä kumpikaan osapuoli myöskään valinnut käytettävää jaettua salaisuutta vaan jaettu salaisuus mudostui matemaattisen operaation tuloksena. Diffie–Hellman-protokollaa ei siis voi käyttää sellaisenaan tiedon salaamiseen, vaan ainoastaan jaetun salaisen arvon määrittämiseen.

Vaikka tämä saattaa tuntua suurelta rajoitteelta, on Diffie–Hellman-protokolla erittäin yleisesti käytössä ja jokainen meistä käyttää (todennäköisesti tietämättään) kyseistä protokollaa päivittäin nettiselailussa. Jokin Diffie–Hellman-protokollan variantti on nimittäin yleensä käytössä osana yhteyden muodostusta, kun käytetään HTTPS-yhteyttä (eli kun nettiosoiteen alussa on https://).

Voit käyttää seuraavien tehtävien vastaamiseen joko annettuja koodeja tai kynää ja paperia. Kummallakin tavalla tehtävän tekeminen onnistuu.

Mikä on yhteinen arvo eli salaisuus, jos parametreiksi on valittu \(p=211\) ja \(g=2\), mutta \(X_A = 100\) ja \(X_B = 200\)?

Aiemmin oletettiin, että Carol pystyy vain salakuuntelemaan Alicen ja Bobin välistä liikennettä. Mitä tapahtuu, jos Carol pääsee viestittelyn väliin siten, että hän pystyy sieppaamaan viestejä ja lähettämään omia viestejään molemmille osapuolille?

Yhteenveto

Tässä osiossa olemme käyttäneet yhtä julkisen avaimen menetelmää.

  • Osaamme luoda Diffie–Hellman-protokollalla jaetun salaisuuden.

  • Ymmärrämme, mikä ero on parametreilla ja avaimilla.

  • Ymmärrämme, mistä diskreetin logaritmin haasteellisuus syntyy.

Seuraavaksi katsomme, miten tiedon salaus onnistuu julkisen avaimen järjestelmillä.

Palautusta lähetetään...