Vuonna kryptografia , Diffie-Hellman , joka on nimetty tekijöille Whitfield Diffie ja Martin Hellman , on menetelmä, joka julkaistiin vuonna 1976, jonka kaksi aineita , tavallisesti nimeltään Alice ja Bob voivat sopia useista (joita he voivat käyttää sitä avain on salata seuraavaan keskusteluun) ilman kolmatta ainetta nimeltä Eve on pysty havaitsemaan määrän, vaikka kuunnellut kaikki vaihdot. Tämä idea voitti kaksi kirjoittajaa Turing-palkinnon vuonna 2015 .
Annetaan ensin intuitiivinen selitys tekemällä analogia väreihin. Tavoitteena on, että Alice ja Bob sopivat salaisesta väristä ilman, että Eve voisi tietää sitä. Tämä selitys on kuvallinen eikä sillä ole mitään käytännön merkitystä, mutta se auttaa ymmärtämään Diffie-Hellman-avaimenvaihdon olemuksen. Oletamme, että aineet voivat sekoittaa värejä, mutta seoksen valmistamiseksi käytettyjen värien uuttaminen on vaikeaa (varsinkin Eevalle!) Periaate on seuraava.
Protokollan lopussa Alicella ja Bobilla on sama ruskea väri, joka edustaa jaettua salaista väriä. Olettaen, että Eevan on vaikea poimia värejä, joita käytetään julkisten oranssin ja sinisen värin saamiseen, Eve ei tiedä lopullista ruskeaa väriä.
Alla kuvatussa alkuperäisessä periaatteessa valitaan alkuluku p . ”Värit” ovat modulo p numeroita. Kahden värin sekoittaminen koostuu luvun nostamisesta tiettyyn modulo p -tehoon. Seoksessa käytettyjen värien löytäminen vastaa eksponention kääntämistä, mikä on vaikea algoritminen ongelma.
Kuvailemme alkuperäistä periaatetta.
Protokollan lopussa Alice ja Bob tietävät molemmat numeron g ab [mod p ], mutta eivät Eevaa. Koska eksponentiaalia on vaikea kääntää äärellisessä kentässä (tai elliptisellä käyrällä), ts. Diskreetin logaritmin laskemiseksi , Eve ei voi selvittää sitä, joten se ei voi laskea g ab [mod p ].
Yllä olevassa kuvauksessa Alice ja Bob työskentelevät äärellisessä kentässä Z / p Z , he vaihtavat modulo p- numerot . Yleisesti ottaen Diffie-Hellman-avaimenvaihto yleistyy mihin tahansa äärelliseen sykliseen ryhmään (sen sijaan, että sovitaan alkuluvusta p, ne sopivat rajallisesta ryhmästä). Tämä äärellinen ryhmä voi olla rajallinen kenttä , josta he käyttävät vain kertolaskua tai elliptistä käyrää .
Käytännössä voimme ottaa suurikokoisen Sophie Germain -elementin p (siten, että q = 2p + 1-prime myös) ja generaattorin g Z: ssä / pZ: ssä (g on siis ensisijainen p-1: n kanssa).
Menetelmässä käytetään käsitettä ryhmä , esimerkiksi multiplikatiivisessa ryhmän kokonaisluvut modulo p , jossa p on alkuluku: tässä tapauksessa, matemaattiset operaatiot (kertominen, teho, divisioona) suoritetaan modulo p, joka on - Say pitäen vain loppuosa euklidisesta jaosta p: llä. Koska ryhmillä on assosiatiivisuuden ominaisuus , yhtälö ( g b ) a = ( g a ) b on pätevä ja molemmat osapuolet saavat todellakin saman salaisen avaimen.
Turvallisuuden, protokollan piilee vaikeus diskreetin logaritmin ongelma: Eve löytää g ab kohteesta g ja g b , hänen täytyy nostaa yksi tai toinen valta b tai valtaa vastaavasti.. Mutta päätellään (vast. B ) alkaen g (vast. G b ) on ongelma, että emme osaa ratkaista tehokkaasti yleisessä tapauksessa. Siksi Eve ei pysty (laskennallisesti) johtamaan tiedoista g a , g b , g ja p g ab: n arvoa .
Lähtöryhmä on kuitenkin valittava hyvin ja käytettyjen numeroiden on oltava riittävän suuria, esimerkiksi tyhjentävän hakuhyökkäyksen välttämiseksi . Tällä hetkellä käytetään yleensä 2048 bitin alkulukuja p (suuruusluokkaa 600 numeroa desimaalikirjoituksella), joille erillisen logaritmin resoluutiota ei katsota mahdolliseksi. Jos käytännön ratkaisu erillisen logaritmin ratkaisemiseen ilmenisi, muut salausjärjestelmät voivat pudota, etenkin samaan periaatteeseen perustuva ElGamal-järjestelmä .
Tämä protokolla on haavoittuva " ihminen keskellä " -hyökkäykselle , johon liittyy hyökkääjä, joka kykenee lukemaan ja muokkaamaan kaikkia Alice ja Bobin välillä vaihdettuja viestejä.
Tämä hyökkäys on perustuu kuuntelu g ja g b , joka on helppoa, koska ne vaihdetaan selvä; elementin g oletetaan olevan kaikkien hyökkääjien tiedossa. Löytää numerot ja b ja siten täysin rikkoa vaihto, olisi tarpeen laskea diskreetti logaritmi g ja g b , joka on käytännössä mahdotonta.
Mutta hyökkääjä voi asettua välillä Alice ja Bob, siepata avain g lähettämän Alice ja lähettää Bob toinen avain g A ' , joka teeskentelee olevansa Alice. Samoin hän voi korvata avaimen g b, jonka Bob lähetti Alicelle, avaimella g b ' , esittäen olevansa Bob. Hyökkääjä kommunikoi siten Alicen kanssa jaetulla avaimella g ab ' ja kommunikoi Bobin kanssa jaetulla avaimella g a'b , Alice ja Bob uskovat kommunikoivansa suoraan. Tätä kutsutaan "ihminen keskellä -hyökkäykseksi".
Alice ja Bob uskovat vaihtaneensa salaisen avaimen, kun todellisuudessa he ovat vaihtaneet salaisen avaimen hyökkääjän, keskellä olevan miehen, kanssa.
Tämän hyökkäyksen klassinen kiertotapa on allekirjoittaa arvonvaihto epäsymmetrisen avainparin avulla , jonka luotettava kolmas osapuoli on varmentanut tai jonka molemmat osallistujat ovat aiemmin vaihtaneet julkiset puolikkaat.
Alice voi siis olla varma, että avaimen, jonka hän saa, tulee todella Bob ja päinvastoin Bobille.