Problém Diffie – Hellman - Diffie–Hellman problem

The Problém Diffie – Hellman (DHP) je matematický problém, který poprvé navrhl Whitfield Diffie a Martin Hellman v kontextu kryptografie. Motivací tohoto problému je, že mnoho bezpečnostních systémů používá jednosměrné funkce: matematické operace, které se rychle počítají, ale je těžké je zvrátit. Například umožňují šifrování zprávy, ale obrácení šifrování je obtížné. Pokud by řešení DHP bylo snadné, tyto systémy by se snadno rozbily.

Popis problému

Problém Diffie – Hellman je uveden neformálně takto:

Vzhledem k prvku G a hodnoty GX a Gy, jaká je hodnota Gxy?

Formálně, G je generátor některých skupina (obvykle multiplikativní skupina a konečné pole nebo eliptická křivka skupina) a X a y jsou náhodně vybraná celá čísla.

Například v Výměna klíčů Diffie – Hellman, pozoruje odposlech GX a Gy vyměněny jako součást protokolu a obě strany vypočítají sdílený klíč Gxy. Rychlý způsob řešení DHP by umožnil odposlechu narušit soukromí výměny klíčů Diffie – Hellman a mnoha jeho variant, včetně Šifrování ElGamal.

Výpočetní složitost

v kryptografie pro určité skupiny ano předpokládaný že DHP je tvrdý a tomu se často říká Předpoklad Diffie – Hellman. Problém přežil zkoumání několik desetiletí a dosud nebylo zveřejněno žádné „snadné“ řešení.

Od roku 2006 je nejúčinnějším známým způsobem řešení DHP řešení řešení problém diskrétního logaritmu (DLP), který je k nalezení X daný G a GX. Ve skutečnosti významný pokrok (den Boer, Maurer Vlk, Boneh a Lipton ) bylo prokázáno, že u mnoha skupin je DHP téměř stejně tvrdý jako DLP. Dosud neexistuje žádný důkaz, že DHP nebo DLP je těžký problém, kromě obecných skupin (Nechaev a Shoup).

Další varianty

Bylo zváženo mnoho variant problému Diffie – Hellman. Nejvýznamnější variantou je rozhodující problém Diffie – Hellman (DDHP), což je rozlišení Gxy z daného prvku náhodné skupiny G, GX, a Gy. Někdy se DHP nazývá výpočetní problém Diffie – Hellman (CDHP) k jasnějšímu odlišení od DDHP. Nedávno seskupeny s párování se staly populární a v těchto skupinách je DDHP snadné, přesto se DHP stále považuje za tvrdý. Méně významné varianty DHP viz odkazy.

Reference

  • B. den Boer, Diffie – Hellman je pro určité prvočísla stejně silný jako diskrétní log v Pokroky v kryptologii - CRYPTO 88, Přednášky z informatiky 403, Springer, str. 530, 1988.
  • U. M. Maurer a S. Wolf, Diffie – Hellman věštec in Advances in Cryptology - CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, str. 268–282, 1996.
  • Maurer, Ueli M .; Vlk, Stefan (2000). „Protokol Diffie – Hellman“. Designy, kódy a kryptografie. 19 (2/3): 147–171. doi:10.1023 / A: 1008302122286.
  • D. Boneh a R. J. Lipton, Algoritmy pro pole černé skříňky a jejich aplikace na kryptotografii in Advances in Cryptology - CRYPTO 96, (N. Koblitz, ed.), Lecture Notes in Computer Science 1070, Springer, pp. 283–297, 1996.
  • A. Muzereau, N. P. Smart a F. Vercauteran, Ekvivalence mezi DHP a DLP pro eliptické křivky používané v praktických aplikacích, LMS J. Comput. Matematika., 7, s. 50–72, 2004. Viz [www.lms.ac.uk].
  • D. R. L. Brown a R. P. Gallant, Problém Static Diffie – Hellman, IACR ePrint 2004/306.
  • V. I. Nechaev, Složitost určitého algoritmu pro diskrétní logaritmusMatematické poznámky, 55 (2), str. 165–172, 1994.
  • V. Shoup, Dolní hranice pro diskrétní logaritmy a související problémy v Pokroky v kryptologii - EUROCRYPT 97, (W. Fumy, ed.), Lecture Notes in Computer Science 1233, Springer, str. 256–266, 1997.
  • Bao, Feng; Deng, Robert H .; Zhu, Huafei (2003). "Variace problému Diffie-Hellman". ICICS 2003: Informační a komunikační bezpečnost. Přednášky z informatiky. 2836. Springer. 301–312. CiteSeerX  10.1.1.104.3007. doi:10.1007/978-3-540-39927-8_28. ISBN  978-3-540-20150-2.
  • Boneh, Dan (1998). „Problém Rozhodnutí Diffie-Hellman“. ANTS 1998: Algoritmická teorie čísel. Přednášky z informatiky. 1423. Springer. str. 48–63. CiteSeerX  10.1.1.461.9971. doi:10.1007 / bfb0054851. ISBN  978-3-540-64657-0.
  • Bresson, Emmanuel; Chevassut, Olivier; Pointcheval, David (2003). „Problémy skupiny Diffie-Hellman“ (PDF). SAC 2002: Vybrané oblasti v kryptografii. Přednášky z informatiky. 2595. Springer. 325–338. doi:10.1007/3-540-36492-7_21. ISBN  978-3-540-00622-0.
  • Biham, Eli; Boneh, Dan; Reingold, Omer (1999). „Rozbití generalizovaného Diffie – Hellmanova modulo kompozitu není o nic jednodušší než factoring“. Dopisy o zpracování informací. 70 (2): 83–87. CiteSeerX  10.1.1.39.110. doi:10.1016 / S0020-0190 (99) 00047-2.
  • Steiner, Michael; Tsudik, Gene; Waidner, Michael (1996). „Distribuce klíčů Diffie-Hellman rozšířena na skupinovou komunikaci“. Sborník příspěvků ze 3. konference ACM o počítačové a komunikační bezpečnosti - CCS '96. ACM. str.31–37. CiteSeerX  10.1.1.35.9717. doi:10.1145/238168.238182. ISBN  978-0897918299.
  • Diffie, W .; Hellman, M. (1976). "Nové směry v kryptografii". Transakce IEEE na teorii informací. 22 (6): 644–654. CiteSeerX  10.1.1.37.9720. doi:10.1109 / tit.1976.1055638.