Diffie-Hellman -avaintenvaihto (2-A)

Salakirjoituksen keskeinen periaate on, että siihen tarvitaan jokin osapuolten tuntema yhteinen salaisuus, avain, jota ei kukaan muu tiedä. Avain on tyypillisesti bittijono, jolla voi olla pituutta esim. 64 tai 128, ja sen voi yhtä hyvin tulkita kokonaisluvuksi. Avaimesta sopiminen on hankalaa: sitä ei voi lähettää suojattomassa tietoliikennekanavassa eikä sitä toisaalta voi salata, koska ei ole vielä salausavainta.

Nerokas ratkaisu tarjoutuu potenssiin korottamisen laskusäännöistä ja siitä, että logaritmin laskeminen modulaarisessa eli kokonaislukuaritmetiikassa on erittäin vaikeaa, kun luvut ovat suuria. Unohdetaan tässä vaiheessa aritmetiikan modulaarisuus ja keskitytään vain perusideaan:

Kun osapuolet A ja B haluavat generoida yhteisen avaimen:

1) he sopivat kantaluvusta g=5 ja primitiivisestä alkiosta p=21, joiden ei tarvitse olla salaisia.

2) Kumpikin valitsee sitten satunnaisen luvun; olkoon A:n luku x=4 ja B:n luku y=7. Kumpikin pitää oman lukunsa salassa

3) A lähettää B:lle luvun AA = (g^x mod p) = ( 5^4 mod 21 ) = 16

4) B lähettää A:lle luvun BB = (g^y mod p) = ( 5^7 mod 21 ) = 5.

5) A laskee salaisen avaimen käyttäen saamaansa lukua B:ltä kaavalla s = BB^x mod p = 5^4mod 21 = 16

6) B laskee salaisen avaimen käyttäen saamaansa lukua A:ltä kaavalla s = AA^y mod p = 16^7mod 21 = 16

Yhteisenä avaimena A:lla ja B:llä on nyt luku 16

Miksi tulos on sama?

Koska g^xy mod p = g^yx mod p

Todellisuudessa luvut valitaan hyvin suuriksi esim p 300 numeroa ja x ja y 100 numeroa, jolloin nykyisillä algoritmeilla ei salaisia numeroita x ja y pystytä ratkaisemaan.

Sama asia kaaviona:
diffie-hellmann.jpg

Jotta joku muu saisi selville saman luvun, hänen pitäisi siis luvuista gx ja gy laskea luku gxy. Tätä varten hyökkääjäkin tarvitsisi jomman kumman luvuista x ja y, eli hän joutuisi laskemaan logaritmin luvusta gx tai gy. Koska kyseessä on todellisuudessa diskreetti logaritmi kokonaislukuaritmetiikassa (moduulina eli jakajana yhteisesti sovittu suuri eli monisatabittinen alkuluku), ei tämä käy päinsä missään kohtuullisessa ajassa. Diskreetti eksponenttifunktio on yksi kryptografiassa hyödyllisistä yksisuuntaisista funktioista.

Oletetaan, että hyökkääjä C kaappaa A:n ja B:n toisilleen lähettämät viestit (esim. tietoverkon reitittimessä) ja vaihtaa kummankin tilalle luvun gz, missä z on C:n keksimä luku. Nyt A laskee itselleen avaimen gxz ja B avaimen gyz eivätkä ne ole samat. Tämäpä ei haittaa C:tä, sillä C tuntee molemmat nämä avaimet ja pystyy A:n ja B:n "välimiehenä" jatkossa purkamaan A:n viestistä salauksen avaimella gxz ja lähettämään sen edelleen B:lle avaimella gyz salattuna - ja vastaavasti B:ltä A:n suuntaan. Tämän "palvelun" avulla C saa siis selville kaikki luottamukselliseksi tarkoitetut viestit A:n ja B:n välillä ja voi halutessaan tietysti muuttaakin niitä, eivätkä A ja B osaa epäillä mitään.

Tällainen välimies- eli "man-in-the-middle"-hyökkäys pitää ottaa huomioon kaikessa tietoliikenteen turvaamisessa. Yleisesti siinä on kyse tilanteesta, jossa osapuoli C näyttäytyy A:lle B:nä ja B:lle A:na eivätkä nämä pysty edes periaatteessa havaitsemaan asiaa.

Tässä luonnosteltu Diffie-Hellmanin avaintenvaihtoprotokolla (vuodelta 1976) tarvitsee siis lisäksi osapuolten autentikoinnin, jotta C ei pääse väliin. Kun se on hoidossa, järjestelmä onkin erittäin hyvä ja se on ollut yksi yleisimmistä rakennuspalikoista tietoturvaprotokollissa.

-- JukkaKoskinen?

SivuTiedotLaajennettu edit

Vaativuus Perus
Valmius Valmisteilla
Tyyppi Ydin
Luokitus Uhkat
Mitä Luottamuksellisuus
Miltä Ihmisetön uhka
Missä Organisaatio
Kuka Tite-ammattilainen
Milloin Ennakolta
Miksi Hyvä tapa
Print version |  PDF  | History: r3 < r2 < r1 | 
Topic revision: r3 - 18 Nov 2010 - 00:20:41 - MikkoKoivisto?
 

TUTWiki

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TUTWiki? Send feedback