Protokol Diffie-Hellman

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 27. července 2022; kontroly vyžadují 2 úpravy .

Protokol Diffie -Hellman ( anglicky  Diffie-Hellman key exchange protocol, DH ) je kryptografický protokol , který umožňuje dvěma nebo více stranám získat sdílený tajný klíč pomocí komunikačního kanálu, který není chráněn před nasloucháním. Výsledný klíč se používá k šifrování dalších výměn pomocí symetrických šifrovacích algoritmů .

Schéma distribuce veřejného klíče navržené Diffiem a Hellmanem způsobilo skutečnou revoluci ve světě šifrování, protože odstranilo hlavní problém klasické kryptografie – problém distribuce klíčů.

Ve své čisté podobě je algoritmus Diffie-Hellman zranitelný vůči změnám dat v komunikačním kanálu, včetně útoku „ Man-in-the-middle (man in the middle) “, takže schémata, která jej používají, používají další jednosměrné nebo dvě cesty. -way autentizační metody .

Historie

Přenos klíče otevřenými kanály byl velkým problémem v kryptografii 20. století. Tento problém byl ale vyřešen po příchodu Diffie-Hellmanova algoritmu. Tento algoritmus umožnil odpovědět na hlavní otázku: „Jak se při výměně šifrovaných zpráv vyhnout nutnosti přenášet tajný dešifrovací kód, který zpravidla není menší než samotná zpráva? Veřejná distribuce klíčů Diffie-Hellman umožňuje dvojici uživatelů systému vyvinout sdílený tajný klíč bez výměny tajných dat.

Základy kryptografie s veřejným klíčem rozšířili Whitfield Diffie a Martin Hellman a nezávisle Ralph Merkle .

Jejich přínosem pro kryptografii bylo tvrzení, že klíče lze používat ve dvojicích - šifrovací klíč a dešifrovací klíč - za předpokladu, že z obsahu veřejně přenášeného šifrovacího klíče nelze určit obsah dešifrovacího klíče. Diffie a Hellman poprvé představili tuto myšlenku na National Computer Conference v roce 1976 a o několik měsíců později byla publikována jejich klíčová práce New Directions in Cryptography [1] .

O rok později byl vynalezen první asymetrický šifrovací algoritmus RSA , který vyřešil problém komunikace přes nezabezpečený kanál.

V roce 2002 napsal Martin Hellman :

Tento systém... je od té doby známý jako Diffie-Hellmanův algoritmus. Když však Diffie a já systém poprvé popsali na papíře, byl to systém distribuce veřejného klíče, který byl konceptualizován Merklem, a proto by se měl nazývat „algoritmus Diffie-Hellman-Merkle“, pokud je spojen se jmény. Doufám, že tato malá změna pomůže rozpoznat Merkleův stejný příspěvek k vynálezu kryptografie s veřejným klíčem.

V nyní prošlém patentu USA 4 200 770 jsou jako tvůrci tohoto algoritmu uvedeni tři autoři: Hellman, Diffie a Merkle.

Teprve v prosinci 1997 se objevily aktualizované informace, že Malcolm Williamson již v roce 1974 vynalezl matematický algoritmus založený na komutativitě exponentů při postupném umocňování ( ). Tuto metodu lze nazvat analogií Diffie-Hellmanova algoritmu.

Popis algoritmu [2]

Předpokládejme, že existují dva předplatitelé: Alice a Bob. Oba předplatitelé znají nějaká dvě čísla a , která nejsou tajná a mohou je znát i další zájemci. Aby bylo možné vytvořit tajný klíč neznámý nikomu jinému, oba předplatitelé generují velká náhodná čísla: Alice - číslo , Bob - číslo . Alice pak vypočítá zbytek dělení [3] (1):

(jeden)

a pošle to Bobovi a Bob vypočítá zbytek dělení (2):

(2)

a dá to Alici. Předpokládá se, že útočník může získat obě tyto hodnoty, ale ne je upravit (to znamená, že nemá jak zasahovat do procesu přenosu).

Ve druhé fázi Alice na základě toho, co má a přijala přes síť , vypočítá hodnotu (3):

(3)

Bob na základě toho, co má a přijal přes síť , vypočítá hodnotu (4):

(čtyři)

Jak můžete vidět, Alice a Bob dostali stejné číslo (5):

(5)

Mohou jej použít jako tajný klíč, protože zde bude útočník čelit prakticky neřešitelnému (v rozumném čase) problému výpočtu (3) nebo (4) ze zachyceného a , pokud jsou čísla , zvolena dostatečně velká. Činnost algoritmu je znázorněna na obrázku [4] .

Když je algoritmus spuštěn, každá strana:

  1. generuje náhodné přirozené číslo a  - soukromý klíč
  2. spolu se vzdálenou stranou nastavuje veřejné parametry p a g (obvykle se hodnoty p a g generují na jedné straně a předávají na druhou), kde p je náhodné prvočíslo (p-1)/2 by také mělo být náhodné prvočíslo (pro lepší bezpečnost) [5] g je primitivní kořen modulo p (také prvočíslo)
  3. vypočítá veřejný klíč A pomocí transformace na soukromý klíč A = g a mod p
  4. vyměňuje veřejné klíče se vzdálenou stranou
  5. vypočítá sdílený tajný klíč K pomocí veřejného klíče vzdálené strany B a jejího soukromého klíče a K = B a mod p K je na obou stranách stejné, protože: 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

V praktických implementacích se pro a a b používají čísla řádu 10100 ap řádu 10300 . Číslo g nemusí být velké a obvykle má hodnotu do první desítky.

Příklad

Eva je kryptoanalytik. Čte přeposílání Boba a Alice, ale nemění obsah jejich zpráv [6] .

Alice
Ví Neví
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
Bobe
Ví Neví
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
Vůbec
Ví Neví
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ův algoritmus se třemi nebo více účastníky

Použití Diffie-Hellmanova algoritmu není omezeno na dva účastníky. Lze jej aplikovat na neomezený počet uživatelů. Zvažte situaci, kdy Alice, Bob a Carol společně vygenerují počáteční klíč. V tomto případě bude sled akcí následující [7] :

Všechny výpočty jsou prováděny modulo p

  1. Strany se dohodnou na parametrech algoritmu p a g
  2. Strany, Alice, Bob a Carol vygenerují své klíče - a , b a c v tomto pořadí.
  3. Alice vypočítá g a mod p a pošle ho Bobovi
  4. Bob vypočítá (g a ) b mod p = g ab mod p a pošle to Carol
  5. Carol vypočítá (g ab ) c mod p = g abc mod p a tak získá sdílený tajný klíč
  6. Bob vypočítá g b mod p a pošle ho Carol
  7. Carol vypočítá (g b ) c mod p = g bc mod p a pošle ho Alici
  8. Alice vypočítá (g bc ) a mod p = g bca mod p = g abc mod p  je sdílené tajemství
  9. Carol vypočítá g c mod p a pošle ho Alici
  10. Alice vypočítá (g c ) a mod p = g ca mod p a pošle ho Bobovi
  11. Bob vypočítá (g ca ) b mod p = g cab mod p = g abc mod p a také získá sdílené tajemství

Pokud někdo poslouchá komunikační kanál, bude moci vidět g ​​a mod p , g b mod p , g c mod p , g ab mod p , g ac mod p a g bc mod p , ale neuvidí být schopen reprodukovat g abc mod p pomocí libovolné kombinace těchto čísel.

Aby bylo možné tento algoritmus efektivně aplikovat na velkou skupinu lidí, je třeba dodržovat dva základní principy:

Šifrování veřejným klíčem

Algoritmus Diffie-Hellman lze také použít při šifrování veřejným klíčem. V tomto případě zůstává obecné schéma podobné výše uvedenému, ale s malými rozdíly. Alice nepředává přímo hodnoty p, g a A Bobovi, ale zveřejňuje je předem jako svůj veřejný klíč. Bob provede svou část výpočtu, poté zašifruje zprávu symetrickým algoritmem pomocí klíče K a pošle šifrovaný text Alici spolu s hodnotou B.

V praxi se Diffie-Hellmanův algoritmus tímto způsobem nepoužívá. V této oblasti je dominantním algoritmem veřejného klíče RSA. Důvodem jsou spíše komerční úvahy, protože certifikační autoritu vytvořila společnost RSA Data Security. Při podepisování certifikátů navíc nelze použít algoritmus Diffie-Hellman [4] .

Získání klíče bez přenosu klíče

Pokud existuje komunita uživatelů, může každý z uživatelů publikovat veřejný klíč X= mod n ve společné databázi. Pokud chce Alice komunikovat s Bobem, potřebuje získat Bobův veřejný klíč a vygenerovat jejich sdílené tajemství. Alice může zprávu zašifrovat pomocí vygenerovaného soukromého klíče a odeslat ji Bobovi. Bob vytáhne Alicin veřejný klíč a najde sdílené tajemství.

Každá dvojice uživatelů může používat svůj vlastní jedinečný tajný klíč, aniž by vyžadovala výměnu dat mezi uživateli. V tomto případě musí být všechny veřejné klíče ověřeny, aby se vyloučil „muž uprostřed“ [4] .

Kryptografická síla

Kryptografická síla Diffie-Hellmanova algoritmu (tj. složitost výpočtu daných p, g a ) je založena na očekávané složitosti problému diskrétního logaritmu.

Protokol Diffie-Hellman je vynikající v odolávání pasivnímu útoku, ale pokud je implementován útok typu man-in-the-middle, neodolá. V protokolu totiž ani Alice, ani Bob nemohou spolehlivě určit, kdo je jejich partnerem, takže si lze docela dobře představit případ, kdy Bob a Alice navázali vztah s Mallory, která se Alice vydává za Boba, a Alice se představí. k Bobovi. A pak místo protokolu Diffie-Hellman dostaneme něco podobného následujícímu:

Krok Alice Mallory Fazole
jeden g a → g a
2 g n ← gn _
g an g an
3 g m → g m
čtyři g b ← gb _
g mb g mb

To znamená, že Mallory dostane jeden sdílený klíč s Alicí (která si myslí, že je to Bob) a jeden sdílený klíč s Bobem (který si myslí, že je to Alice). A proto může od Alice přijmout jakoukoli zprávu pro Boba, dešifrovat ji klíčem, přečíst, zašifrovat klíčem a poslat Bobovi. Padělek tak může zůstat velmi dlouhou dobu bez povšimnutí [3] .

Problém Diffie-Hellmana a problém diskrétního logaritmu

Síla sdíleného klíče v protokolu Diffie-Hellman je zajištěna výpočtem hodnoty z daných čísel a . Tento problém se nazývá výpočetní Diffie-Hellmanův problém [8] .

Výpočetní Diffie-Hellmanův problém (v konečném poli)

VÝCHOZÍ DATA: desq  : popis cílového pole  ; g∈ je generujícím prvkem grupy  ; , ∈ , kde 0 < a, b < q. VÝSLEDEK:

Taková formulace je obecnou formulací problému v konečném poli , představuje obecný případ, pro Diffieho-Hellmana se používá speciální případ. Pokud by byl problém Diffie-Hellman snadno řešitelný, pak by se hodnota dala zjistit znalostmi čísel , , a , která jsou součástí protokolu. Za předpokladu, že nepřítel má schopnost zachytit informace, mělo by se předpokládat, že tato čísla pro něj nejsou tajemstvím. Diffie-Hellmanův problém se opírá o složitost výpočtu diskrétního logaritmu [1] .

Problém diskrétního logaritmu (v konečném poli)

VÝCHOZÍ DATA: desq  : popis cílového pole  ; g∈ je generujícím prvkem grupy  ; h ∈ VÝSLEDEK: Jedinečné číslo a < q splňující podmínku h = . Celé číslo a je označeno jako h.

Diskrétní logaritmus je podobný obvyklému logaritmu v oboru reálných čísel. Avšak na rozdíl od poslední úlohy, ve které je řešení přibližné, má problém výpočtu diskrétního logaritmu přesné řešení.

Jak již bylo jasné, teorie výpočetní složitosti je jádrem moderní kryptografie. To znamená, že síla kryptosystémů s veřejným klíčem je podmíněná a závisí na složitosti řešení určitých problémů. To vše vede k tomu, že problém Diffie-Hellman a problém diskrétního logaritmu jsou považovány za neřešitelné.

Intuitivně je jasné, že složitost řešení těchto úloh závisí jak na velikosti pole Fq, tak na volbě parametrů (veřejný parametr g a tajná čísla a a b). Je zřejmé, že malé verze těchto problémů jsou řešitelné. Získané informace nám umožňují formulovat přesné předpoklady o neřešitelnosti Diffieho-Hellmanova problému a problému diskrétního logaritmu.

Předpoklad 1 - Podmínky neřešitelnosti Diffieho-Hellmanova problému

Algoritmus pro řešení Diffieho-Hellmanova problému je pravděpodobnostní polynomiální algoritmus A s výhodou ε > 0:

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

kde vstupní data A jsou specifikována v definici (Computational Diffie-Hellman problem) (v posledním poli).

Nechť IG je generátor variant, který přijímá jako vstup číslo , jehož doba běhu je polynom v parametru k a výsledkem je 1) desq( ), kde |q| = k a 2) generující prvek g ∈ .

Řekneme, že generátor IG splňuje podmínky pro neřešitelnost Diffie-Hellmanovy úlohy, pokud pro varianty IG( ) neexistuje algoritmus řešení s výhodou ε > 0, který by nebyl zanedbatelný ve srovnání se všemi dostatečně velkými čísly k.

Předpoklad 2 - Podmínky neřešitelnosti úlohy diskrétního logaritmu

Algoritmus pro řešení úlohy diskrétního logaritmu je pravděpodobnostní polynomiální algoritmus A s výhodou ε > 0:

ε = Pravděpodobnost[ A(desc( ), g, h)]

kde vstupní data A jsou specifikována v definici (Computational Diffie-Hellman problem) (v posledním poli).

Nechť IG je generátor variant, který přijímá jako vstup číslo , jehož doba běhu je polynom v parametru k a výsledkem je 1) desq( ), kde |q| = k a 2) tvořící prvek g ∈ a 3) prvek h ∈

Řekneme, že generátor IG splňuje podmínky pro neřešitelnost Diffie-Hellmanovy úlohy, pokud pro varianty IG( ) neexistuje algoritmus řešení s výhodou ε > 0, který by nebyl zanedbatelný ve srovnání se všemi dostatečně velkými čísly k.

Jinými slovy se zde předpokládá, že téměř všechny dostatečně velké varianty těchto úloh v konečných polích nemají účinný algoritmus řešení. Podíl slabých variant těchto problémů, které lze řešit, je zanedbatelný.

Kritika

Volba parametrů je důležitá pro zabezpečení protokolu. Mnoho implementací používá malý počet oblíbených sad parametrů algoritmu. V roce 2016 byla prezentována práce, která ukázala možnost přípravy speciálních konečných polí pro algoritmus Diffie-Hellman (DH). Prvočíslo p speciálního tvaru zvoleného výzkumníky (velikost 1024 bitů) vypadá uživatelům normálně, ale zjednodušuje složitost výpočtů pomocí metody SNFS pro řešení problému diskrétního logaritmu o několik řádů. Pro boj s útokem se navrhuje zvětšit velikost modulu na 2048 bitů [9] [10] .

Viz také

Poznámky

  1. ↑ 1 2 Diffie W. , Hellman M. E. New Directions in Cryptography  // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1976. - Sv. 22, Iss. 6. - S. 644-654. — ISSN 0018-9448 ; 1557-9654 – doi:10.1109/TIT.1976.1055638
  2. ↑ Intelekt. Jak funguje asymetrické šifrování v prostém jazyce Archivováno 4. února 2018 na Wayback Machine . 20. května 2012.
  3. ↑ 1 2 Bruce Schneier "Aplikovaná kryptografie"
  4. ↑ 1 2 3 Šifrovací asymetrické metody Kapitola 8 ("Šifrování veřejného klíče", "Výměna klíčů bez výměny klíčů", "Kryptografické zabezpečení", "Diffie-Hellmanův problém a problém diskrétního logaritmu")
  5. ↑ Bruce Schneier "Aplikovaná kryptografie" Kapitola 22, odstavec 22.1
  6. ↑ Kryptografický přístroj a metoda Martin E. Hellman, Bailey W. Diffie a Ralph C. Merkle, patent USA č. 4 200 770, 29. dubna 1980)
  7. ↑ Shrnutí ANSI X9.42: Shoda symetrických klíčů pomocí diskrétní logaritmické kryptografie[mrtvý odkaz] (64K soubor PDF) (Popis standardů ANSI 9)
  8. ↑ Výměna klíčů Diffie-Hellman – Nematematické vysvětlení od Keitha Palmgrena
  9. ↑ NSA by mohla do milionů krypto klíčů vložit nezjistitelné „lapače“. Tato technika umožňuje útočníkům pasivně dešifrovat data chráněná systémem Diffie-Hellman.  (anglicky) , ARS Technica (11. října 2016). Archivováno z originálu 13. října 2016. Staženo 13. října 2016.
  10. ↑ Joshua Fried; Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. Kilobitový skrytý SNFS výpočet diskrétního logaritmu  . Eprint IACR (2016). Získáno 13. října 2016. Archivováno z originálu 13. října 2016.

Zdroje

 Kryptosystémy s veřejným klíčem
Algoritmy
Faktorizace celých čísel
Diskrétní logaritmus
Kryptografie na mřížkách
jiný
Teorie
Normy
Témata