Diffie-Hellman-protokolla

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 27. heinäkuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Diffie -Hellman-protokolla ( eng.  Diffie-Hellman key exchange protocol, DH ) on salausprotokolla, jonka avulla kaksi tai useampi osapuoli voi saada jaetun salaisen avaimen käyttämällä viestintäkanavaa, jota ei ole suojattu kuuntelemiselta. Saatua avainta käytetään lisätietojen salaamiseen symmetristen salausalgoritmien avulla .

Diffien ja Hellmanin ehdottama julkisen avaimen jakelujärjestelmä teki todellisen vallankumouksen salauksen maailmassa, koska se poisti klassisen kryptografian pääongelman - avainten jakeluongelman.

Puhtaassa muodossaan Diffie-Hellman-algoritmi on alttiina tietoliikennekanavan tiedonmuokkauksille, mukaan lukien " Man-in-the-middle (mies keskellä) " -hyökkäykselle, joten sitä käyttävät järjestelmät käyttävät ylimääräistä yksi- tai kaksisuuntaista. -tapa todennusmenetelmät .

Historia

Avaimen välittäminen avoimia kanavia pitkin oli suuri ongelma 1900-luvun kryptografiassa. Mutta tämä ongelma ratkesi Diffie-Hellman-algoritmin tulon jälkeen. Tämä algoritmi mahdollisti vastauksen pääkysymykseen: "Kuinka salattuja viestejä vaihdettaessa vältetään tarve lähettää salainen salauksenpurkukoodi, joka ei yleensä ole pienempi kuin itse viesti?" Diffie-Hellman-avainten julkinen jakelu antaa järjestelmän käyttäjäparille mahdollisuuden kehittää jaetun salaisen avaimen vaihtamatta salaisia ​​tietoja.

Julkisen avaimen salauksen perusteet kehittivät Whitfield Diffie ja Martin Hellman sekä itsenäisesti Ralph Merkle .

Heidän panoksensa kryptografiaan oli väite, että avaimia voidaan käyttää pareittain - salausavain ja salauksenpurkuavain - edellyttäen, että on mahdotonta määrittää salauksenpurkuavaimen sisältöä julkisesti lähetetyn salausavaimen sisällöstä. Diffie ja Hellman esittelivät tämän idean ensimmäisen kerran kansallisessa tietokonekonferenssissa vuonna 1976, ja muutamaa kuukautta myöhemmin julkaistiin heidän tärkeä paperinsa New Directions in Cryptography [1] .

Vuotta myöhemmin keksittiin ensimmäinen epäsymmetrinen salausalgoritmi RSA , joka ratkaisi epävarman kanavan kautta tapahtuvan viestinnän ongelman.

Martin Hellman kirjoitti vuonna 2002 :

Tämä järjestelmä ... on sittemmin tunnettu Diffie-Hellman-algoritmina. Kuitenkin, kun Diffie ja minä kuvailimme järjestelmää paperille ensimmäisen kerran, se oli julkisen avaimen jakelujärjestelmä, jonka Merkle suunnitteli, ja siksi sitä pitäisi kutsua "Diffie-Hellman-Merkle-algoritmiksi", jos se liittyy nimiin. Toivon, että tämä pieni muutos auttaa tunnustamaan Merklen yhtäläisen panoksen julkisen avaimen salauksen keksimiseen.

Nyt päättyneessä US-patentissa 4 200 770 kolme kirjoittajaa on lueteltu tämän algoritmin luojina: Hellman, Diffie ja Merkle.

Vasta joulukuussa 1997 ilmestyi päivitettyä tietoa, että Malcolm Williamson keksi jo vuonna 1974 matemaattisen algoritmin, joka perustuu eksponentien kommutatiivisuuteen peräkkäin eksponentioituna ( ). Tätä menetelmää voidaan kutsua Diffie-Hellman-algoritmin analogiksi.

Algoritmin kuvaus [2]

Oletetaan, että tilaajia on kaksi: Alice ja Bob. Molemmat tilaajat tietävät pari numeroa ja , jotka eivät ole salaisia ​​ja voivat olla myös muiden kiinnostuneiden tiedossa. Kenellekään muulle tuntemattoman salaisen avaimen luomiseksi molemmat tilaajat luovat suuria satunnaislukuja: Alice - numero , Bob - numero . Alice laskee sitten jaosta [3] (1):

(yksi)

ja lähettää sen Bobille, ja Bob laskee jaon loppuosan (2):

(2)

ja antaa sen Alicelle. Oletetaan, että hyökkääjä voi saada molemmat näistä arvoista, mutta ei muokata niitä (eli hän ei voi puuttua siirtoprosessiin).

Toisessa vaiheessa Alice laskee arvon (3) sen perusteella, mitä hänellä on ja mitä hän on saanut verkon kautta :

(3)

Bob laskee arvon (4) sen perusteella, mitä hänellä on ja mitä hän on saanut verkon kautta :

(neljä)

Kuten näet, Alice ja Bob saivat saman numeron (5):

(5)

He voivat käyttää sitä salaisena avaimena, koska tässä hyökkääjä kohtaa käytännössä ratkaisemattoman (kohtuullisen ajan sisällä) ongelman laskea (3) tai (4) siepatuista ja jos numerot , , valitaan riittävän suuriksi. Algoritmin toiminta on esitetty kuvassa [4] .

Kun algoritmi on käynnissä, kumpikin puoli:

  1. luo satunnaisen luonnollisen luvun a  - yksityisen avaimen
  2. yhdessä etäpuolen kanssa asetetaan julkiset parametrit p ja g (yleensä p- ja g -arvot luodaan toiselle puolelle ja välitetään toiselle), missä p on satunnainen alkuluku (p-1)/2 tulisi myös olla satunnainen alkuluku (paremman turvallisuuden vuoksi) [5] g on primitiivinen juuri modulo p (myös alkuluku)
  3. laskee A : n julkisen avaimen käyttämällä yksityisen avaimen muunnosa A = g a mod p
  4. vaihtaa julkisia avaimia etäosapuolen kanssa
  5. laskee jaetun salaisen avaimen K käyttämällä etäosapuolen B julkista avainta ja sen yksityistä avainta a K = B a mod p K on yhtä suuri molemmilla puolilla, koska: B a mod p = (g b mod p) a mod p = g ab mod p = (g a mod p) b mod p = A b mod p

Käytännön toteutuksissa a:lle ja b :lle käytetään suuruusluokkaa 10100 olevia lukuja ja 10300 :n suuruisia p . Numeron g ei tarvitse olla suuri, ja sen arvo on yleensä kymmenen ensimmäisen sisällä.

Esimerkki

Eva on kryptanalyytikko. Se lukee Bobin ja Alicen edelleenlähetyksen, mutta ei muuta heidän viestiensä sisältöä [6] .

Alice
Tietää ei tiedä
p = 23 b = ?
g = 5
a = 6
A = 5 6 mod 23 = 8
B = 5 b mod 23 = 19
s = 19 6 mod 23 = 2
s = 8 b mod 23 = 2
s = 19 6 mod 23 = 8 b mod 23
s = 2
Bob
Tietää ei tiedä
p = 23 a = ?
g = 5
b = 15
B = 5 15 mod 23 = 19
A = 5 a mod 23 = 8
s = 8 15 mod 23 = 2
s = 19 a mod 23 = 2
s = 8 15 mod 23 = 19 a mod 23
s = 2
Koskaan
Tietää ei tiedä
p = 23 a = ?
g = 5 b = ?
s = ?
A = 5 a mod 23 = 8
B = 5 b mod 23 = 19
s = 19 a mod 23
s = 8 b mod 23
s = 19 a mod 23 = 8 b mod 23

Diffie-Hellman-algoritmi kolmella tai useammalla osallistujalla

Diffie-Hellman-algoritmin käyttö ei rajoitu kahteen osallistujaan. Sitä voidaan soveltaa rajoittamattomaan määrään käyttäjiä. Harkitse tilannetta, jossa Alice, Bob ja Carol luovat alkuavaimen yhdessä. Tässä tapauksessa toimintojen järjestys on seuraava [7] :

Kaikki laskelmat tehdään modulo p

  1. Osapuolet sopivat algoritmiparametreista p ja g
  2. Osapuolet, Alice, Bob ja Carol luovat avaimensa - a , b ja c vastaavasti.
  3. Alice laskee g a mod p :n ja lähettää sen Bobille
  4. Bob laskee (g a ) b mod p = g ab mod p ja lähettää sen Carolille
  5. Carol laskee (g ab ) c mod p = g abc mod p ja saa siten jaetun salaisen avaimen
  6. Bob laskee g b mod p ja lähettää sen Carolille
  7. Carol laskee (g b ) c mod p = g bc mod p ja lähettää sen Alicelle
  8. Alice laskee (g bc ) a mod p = g bca mod p = g abc mod p  on jaettu salaisuus
  9. Carol laskee g c mod p ja lähettää sen Alicelle
  10. Alice laskee (g c ) a mod p = g ca mod p ja lähettää sen Bobille
  11. Bob laskee (g ca ) b mod p = g cab mod p = g abc mod p ja saa myös jaetun salaisuuden

Jos joku kuuntelee viestintäkanavaa, hän voi nähdä g a mod p , g b mod p , g c mod p , g ab mod p , g ac mod p ja g bc mod p , mutta hän ei näe pystyä toistamaan g abc mod p käyttämällä mitä tahansa näiden numeroiden yhdistelmää.

Jotta tätä algoritmia voitaisiin soveltaa tehokkaasti suureen ihmisryhmään, on noudatettava kahta perusperiaatetta:

Julkisen avaimen salaus

Diffie-Hellman-algoritmia voidaan käyttää myös julkisen avaimen salauksessa. Tässä tapauksessa yleinen kaavio pysyy samanlaisena kuin yllä oleva, mutta pienin eroin. Alice ei välitä p:n, g:n ja A:n arvoja suoraan Bobille, vaan julkaisee ne etukäteen julkisena avaimenaan. Bob suorittaa oman osuutensa laskutoimituksesta, salaa sitten viestin symmetrisellä algoritmilla käyttämällä K:tä avaimena ja lähettää salatekstin Alicelle yhdessä B:n arvon kanssa.

Käytännössä Diffie-Hellman-algoritmia ei käytetä tällä tavalla. Tällä alueella hallitseva julkisen avaimen algoritmi on RSA. Tämä johtuu enemmän kaupallisista syistä, koska RSA Data Security loi varmenneviranomaisen. Lisäksi Diffie-Hellman-algoritmia ei voida käyttää varmenteita allekirjoitettaessa [4] .

Avaimen saaminen ilman avaimen lähettämistä

Jos käyttäjäyhteisö on olemassa, kukin käyttäjistä voi julkaista julkisen avaimen X= mod n yhteisessä tietokannassa. Jos Alice haluaa kommunikoida Bobin kanssa, hänen on hankittava Bobin julkinen avain ja luotava heidän yhteinen salaisuutensa. Alice voi salata viestin luodulla yksityisellä avaimella ja lähettää sen Bobille. Bob purkaa Alicen julkisen avaimen ja löytää jaetun salaisuuden.

Jokainen käyttäjäpari voi käyttää omaa ainutlaatuista salaista avaimeansa ilman, että käyttäjien välillä tarvitsee vaihtaa tietoja. Tässä tapauksessa kaikki julkiset avaimet on todennettu, jotta "mies keskellä" suljetaan pois [4] .

Kryptografinen vahvuus

Diffie-Hellman-algoritmin kryptografinen vahvuus (eli annettujen p:n, g: n ja :n laskemisen monimutkaisuus ) perustuu diskreetin logaritmiongelman odotettuun monimutkaisuuteen.

Diffie-Hellman-protokolla vastustaa erinomaisesti passiivista hyökkäystä, mutta jos mies-in-the-middle-hyökkäys toteutetaan, se ei vastusta. Itse asiassa pöytäkirjassa Alice tai Bob eivät voi luotettavasti määrittää, kuka heidän keskustelukumppaninsa on, joten on täysin mahdollista kuvitella tapaus, jossa Bob ja Alice loivat suhteen Malloryn kanssa, joka teeskentelee olevansa Bob Alicelle, ja Alice esittelee itsensä. Bobille. Ja sitten Diffie-Hellman-protokollan sijasta saamme jotain seuraavanlaista:

Vaihe Alice Mallory Papu
yksi g a → g a
2 g n ← gn_ _
g an g an
3 g m → g m
neljä g b ← gb_ _
g mb g mb

Eli Mallory saa yhden jaetun avaimen Alicen kanssa (joka luulee sen olevan Bob) ja yhden jaetun avaimen Bobin kanssa (joka luulee sen olevan Alice). Ja siksi hän voi vastaanottaa Alicelta minkä tahansa viestin Bobille, purkaa sen salauksen avaimella, lukea sen, salata sen avaimella ja lähettää sen Bobille. Siten väärennös voi jäädä huomaamatta hyvin pitkään [3] .

Diffie-Hellman-tehtävä ja diskreetti logaritmiongelma

Jaetun avaimen vahvuus Diffie-Hellman-protokollassa varmistetaan laskemalla arvo annetuista luvuista ja . Tätä ongelmaa kutsutaan laskennalliseksi Diffie-Hellmanin ongelmaksi [8] .

Laskennallinen Diffie-Hellman-tehtävä (ääreisessä kentässä)

ALKUTIEDOT : desq : kohdekentän  kuvaus  ; g∈ on ryhmän generoiva elementti  ; , ∈ , missä 0 < a, b < q. TULOS:

Tällainen muotoilu on ongelman yleinen muotoilu äärellisessä kentässä ; se edustaa yleistä tapausta; Diffie-Hellmanille käytetään erikoistapausta. Jos Diffie-Hellmanin ongelma olisi helppo ratkaista, niin arvo voitaisiin löytää tietämällä numerot , , ja , jotka ovat osa protokollaa. Olettaen, että vihollisella on kyky siepata tietoa, on oletettava, että nämä numerot eivät ole hänelle salaisuus. Diffie-Hellmanin ongelma perustuu diskreetin logaritmin laskennan monimutkaisuuteen [1] .

Diskreetti logaritmiongelma (ääreellisessä kentässä)

ALKUTIEDOT : desq : kohdekentän  kuvaus  ; g∈ on ryhmän generoiva elementti  ; h ∈ TULOS: Yksilöllinen luku a < q, joka täyttää ehdon h = . Kokonaislukua a merkitään h:lla.

Diskreetti logaritmi on samanlainen kuin tavallinen logaritmi reaalilukujen alalla. Toisin kuin viimeisessä tehtävässä, jossa ratkaisu on likimääräinen, diskreetin logaritmin laskentaongelmalla on tarkka ratkaisu.

Kuten on jo käynyt selväksi, laskennallisen monimutkaisuuden teoria on modernin kryptografian ytimessä. Tämä tarkoittaa, että julkisen avaimen salausjärjestelmien vahvuus on ehdollinen ja riippuu tiettyjen ongelmien ratkaisemisen monimutkaisuudesta. Kaikki tämä johtaa siihen, että Diffie-Hellmanin ongelmaa ja diskreetti logaritmiongelmaa pidetään ratkaisemattomina.

On intuitiivisesti selvää, että näiden ongelmien ratkaisemisen monimutkaisuus riippuu sekä kentän Fq koosta että parametrien valinnasta (julkinen parametri g ja salaiset numerot a ja b). On selvää, että pienet versiot näistä ongelmista ovat ratkaistavissa. Saatujen tietojen avulla voimme muotoilla tarkkoja oletuksia Diffie-Hellmanin ongelman ja diskreetin logaritmiongelman ratkaisemattomuudesta.

Oletus 1 - Diffie-Hellman-ongelman ratkaisemattomuuden ehdot

Algoritmi Diffie-Hellman-ongelman ratkaisemiseksi on todennäköisyyspohjainen polynomialgoritmi A, jonka etu on ε > 0:

ε = Prob[ A(desc( ), g, , )].

jossa syötetieto A on määritelty määritelmässä (Computational Diffie-Hellman -tehtävä) (lopullisessa kentässä).

Olkoon IG varianttigeneraattori, joka saa syötteenä luvun , jonka ajoaika on polynomi parametrissa k ja tuloksena on 1) desq( ), missä |q| = k, ja 2) generoiva alkio g ∈ .

Sanotaan, että generaattori IG täyttää Diffie-Hellman-ongelman ratkaisemattomuuden ehdot, jos IG( ) -muunnelmille ei ole olemassa ratkaisualgoritmia, jonka etu ε > 0 ei ole vähäpätöinen verrattuna kaikkiin riittävän suuriin lukuihin k.

Oletus 2 - Diskreetin logaritmiongelman ratkaisemattomuuden ehdot

Eräs algoritmi diskreetin logaritmiongelman ratkaisemiseksi on todennäköisyyspohjainen polynomialgoritmi A, jonka etu on ε > 0:

ε = Prob[ A(desc( ), g, h)]

jossa syötetieto A on määritelty määritelmässä (Computational Diffie-Hellman -tehtävä) (lopullisessa kentässä).

Olkoon IG varianttigeneraattori, joka saa syötteenä luvun , jonka ajoaika on polynomi parametrissa k ja tuloksena on 1) desq( ), missä |q| = k, ja 2) generoiva alkio g ∈ ja 3) alkio h ∈

Sanotaan, että generaattori IG täyttää Diffie-Hellman-ongelman ratkaisemattomuuden ehdot, jos IG( ) -muunnelmille ei ole olemassa ratkaisualgoritmia, jonka etu ε > 0 ei ole vähäpätöinen verrattuna kaikkiin riittävän suuriin lukuihin k.

Toisin sanoen tässä oletetaan, että lähes kaikilla näiden ongelmien riittävän suurilla varianteilla äärellisissä kentissä ei ole tehokasta ratkaisualgoritmia. Näiden ongelmien heikkojen ratkaisujen osuus on mitätön.

Kritiikki

Parametrien valinta on tärkeää protokollan turvallisuuden kannalta. Monet toteutukset käyttävät pientä määrää suosittuja algoritmiparametrijoukkoja. Vuonna 2016 esiteltiin työ, joka osoitti mahdollisuuden valmistaa erityisiä äärellisiä kenttiä Diffie-Hellman (DH) -algoritmia varten. Tutkijoiden valitseman erikoismuodon alkuluku p (kooltaan 1024 bittiä) näyttää käyttäjille normaalilta, mutta se yksinkertaistaa diskreetin logaritmiongelman ratkaisemiseen SNFS-menetelmää käyttävien laskelmien monimutkaisuutta useilla suuruusluokilla. Hyökkäyksen torjumiseksi ehdotetaan moduulin koon kasvattamista 2048 bittiin [9] [10] .

Katso myös

Muistiinpanot

  1. ↑ 1 2 Diffie W. , Hellman M.E. Uudet suunnat kryptografiassa  // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1976. - Voi. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
  2. ↑ Älykkyys. Kuinka epäsymmetrinen salaus toimii selkeällä kielellä Arkistoitu 4. helmikuuta 2018 Wayback Machinessa . 20. toukokuuta 2012.
  3. ↑ 1 2 Bruce Schneier "Soveltava kryptografia"
  4. ↑ 1 2 3 Salauksen epäsymmetriset menetelmät Luku 8 ("Julkisen avaimen salaus", "Avainten vaihto ilman avainten vaihtoa", "Salausturvallisuus", "Diffie-Hellman-ongelma ja diskreetti logaritmiongelma")
  5. ↑ Bruce Schneier "Sovellettu kryptografia" luvun 22 kappale 22.1
  6. ↑ Kryptografiset laitteet ja menetelmät Martin E. Hellman, Bailey W. Diffie ja Ralph C. Merkle, US-patentti nro 4 200 770, 29. huhtikuuta 1980)
  7. ↑ Yhteenveto ANSI X9.42:sta: Diskreetin logaritmin kryptografiaa käyttävien symmetristen avainten sopimus[kuollut linkki] (64K PDF-tiedosto) (ANSI 9 -standardien kuvaus)
  8. ↑ Diffie-Hellman Key Exchange - Ei-matemaatikon selitys Keith Palmgren
  9. ↑ NSA voisi laittaa havaitsemattomia "luukkuja" miljooniin salausavaimiin. Tekniikan avulla hyökkääjät voivat passiivisesti purkaa Diffie-Hellmanin suojattujen tietojen salauksen.  (Englanti) , ARS Technica (11. lokakuuta 2016). Arkistoitu alkuperäisestä 13. lokakuuta 2016. Haettu 13. lokakuuta 2016.
  10. ↑ Joshua Fried; Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. Kilobitin piilotettu SNFS diskreetti  logaritmilaskenta . Eprint IACR (2016). Haettu 13. lokakuuta 2016. Arkistoitu alkuperäisestä 13. lokakuuta 2016.

Lähteet

 Julkisen avaimen salausjärjestelmät
Algoritmit
Kokonaislukujen faktorointi
Diskreetti logaritmi
Kryptografia ristikoilla
muu
Teoria
Standardit
Aiheet