Проблема Диффи–Хеллмана

Проблема Диффи–Хеллмана ( DHP ) — математическая задача, впервые предложенная Уитфилдом Диффи и Мартином Хеллманом ^[1] в контексте криптографии , и служит теоретической основой обмена ключами Диффи–Хеллмана и его производных. Мотивация этой задачи заключается в том, что многие системы безопасности используют односторонние функции : математические операции, которые быстро вычисляются, но трудно обращаются. Например, они позволяют шифровать сообщение, но обращение шифрования затруднено. Если бы решение DHP было простым, эти системы можно было бы легко взломать.

Описание проблемы

Проблема Диффи–Хеллмана неформально формулируется следующим образом:

Если задан элемент и значения и , каково значение ? ${\displaystyle g}$ ${\displaystyle g^{x}}$ ${\displaystyle g^{y}}$ ${\displaystyle g^{xy}}$

Формально является генератором некоторой группы (обычно мультипликативной группы конечного поля или группы эллиптических кривых ), а и являются случайно выбранными целыми числами. ${\displaystyle g}$ ${\displaystyle x}$ ${\displaystyle y}$

Например, в обмене ключами Диффи-Хеллмана подслушиватель наблюдает и обменивается как часть протокола, и обе стороны вычисляют общий ключ . Быстрый способ решения DHP позволил бы подслушивателю нарушить конфиденциальность обмена ключами Диффи-Хеллмана и многих его вариантов, включая шифрование Эль-Гамаля . ${\displaystyle g^{x}}$ ${\displaystyle g^{y}}$ ${\displaystyle g^{xy}}$

Сложность вычислений

В криптографии , для некоторых групп, предполагается , что DHP является сложным, и это часто называют предположением Диффи-Хеллмана . Проблема выдержала проверку в течение нескольких десятилетий, и ни одно «легкое» решение до сих пор не было опубликовано.

По состоянию на 2006 год наиболее эффективным известным способом решения DHP является решение задачи дискретного логарифмирования (DLP), которая заключается в нахождении x по заданным g и g ^x . Фактически, значительный прогресс (ден Бур, Маурер , Вольф, Боне и Липтон ) был достигнут в демонстрации того, что для многих групп DHP почти так же сложна, как DLP. На сегодняшний день нет доказательств того, что DHP или DLP являются сложными задачами, за исключением общих групп (Нечаев и Шуп). Доказательство того, что любая из задач сложна, подразумевает, что P  ≠  NP .

Другие варианты

Было рассмотрено много вариантов задачи Диффи–Хеллмана. Наиболее значимым вариантом является задача принятия решений Диффи–Хеллмана (DDHP), которая заключается в различении g ^xy от случайного элемента группы, заданного g , g ^x , и g ^y . Иногда DHP называют вычислительной задачей Диффи–Хеллмана (CDHP), чтобы более четко отличать ее от DDHP. В последнее время стали популярны группы с парами , и в этих группах DDHP проста, но CDHP по-прежнему считается сложной. Для менее значимых вариантов DHP см. ссылки.

Смотрите также

• Задача дискретного логарифмирования
• Криптография на основе эллиптических кривых

Ссылки

1. Диффи, В.; Хеллман, М. (1976-11-01). «Новые направления в криптографии». Труды IEEE по теории информации . 22 (6): 644–654. doi :10.1109/TIT.1976.1055638. ISSN  0018-9448 – через IEEE.

• Б. ден Бур, Диффи–Хеллман столь же силён, как дискретный логарифм для некоторых простых чисел в Advances in Cryptology – CRYPTO 88, Lecture Notes in Computer Science 403, Springer, стр. 530, 1988.
• UM Maurer и S. Wolf, Оракул Диффи–Хеллмана в Advances in Cryptology – CRYPTO 96, (ред. Н. Коблиц), Lecture Notes in Computer Science 1070, Springer, стр. 268–282, 1996.
• Маурер, Ули М.; Вольф, Стефан (2000). «Протокол Диффи–Хеллмана». Проекты, коды и криптография . 19 (2/3): 147–171. doi :10.1023/A:1008302122286. S2CID  42734334.
• Д. Боне и Р. Дж. Липтон, Алгоритмы для полей черного ящика и их применение в криптографии в Advances in Cryptology – CRYPTO 96, (ред. Н. Коблиц), Lecture Notes in Computer Science 1070, Springer, стр. 283–297, 1996.
• A. Muzereau, NP Smart и F. Vercauteran, Эквивалентность DHP и DLP для эллиптических кривых, используемых в практических приложениях , LMS J. Comput. Math., 7 , стр. 50–72, 2004. См. [www.lms.ac.uk].
• DRL Brown и RP Gallant, Статическая задача Диффи–Хеллмана, IACR ePrint 2004/306.
• В.И. Нечаев, Сложность детерминированного алгоритма дискретного логарифма , Математические заметки, 55 (2), с. 165–172, 1994.
• В. Шуп, Нижние границы для дискретных логарифмов и связанные с ними проблемы в Advances in Cryptology – EUROCRYPT 97, (ред. В. Фьюми), Lecture Notes in Computer Science 1233, Springer, стр. 256–266, 1997.
• Бао, Фэн; Дэн, Роберт Х.; Чжу, Хуафэй (2003). «Вариации проблемы Диффи-Хеллмана». ICICS 2003: Информационная и коммуникационная безопасность . Конспект лекций по информатике. Том 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.
• Боне, Дэн (1998). "Решение проблемы Диффи-Хеллмана". ANTS 1998: Алгоритмическая теория чисел . Конспект лекций по информатике. Том 1423. Springer. С. 48–63. CiteSeerX  10.1.1.461.9971 . doi :10.1007/bfb0054851. ISBN 978-3-540-64657-0.
• Брессон, Эммануэль; Шевасю, Оливье; Пуаншеваль, Дэвид (2003). "Групповые проблемы Диффи-Хеллмана" (PDF) . SAC 2002: Избранные области криптографии . Конспект лекций по информатике. Том 2595. Springer. С. 325–338. doi :10.1007/3-540-36492-7_21. ISBN 978-3-540-00622-0. S2CID  14425909.
• Бихам, Эли; Бонех, Дэн; Рейнгольд, Омер (1999). «Разрушение обобщенного уравнения Диффи–Хеллмана по модулю составного числа не проще, чем факторизация». Information Processing Letters . 70 (2): 83–87. CiteSeerX  10.1.1.39.110 . doi :10.1016/S0020-0190(99)00047-2.
• Штайнер, Майкл; Цудик, Джин; Вайднер, Майкл (1996). "Распределение ключей Диффи-Хеллмана, распространенное на групповую коммуникацию" . Труды 3-й конференции ACM по компьютерной и коммуникационной безопасности - CCS '96. ACM. стр. 31–37. CiteSeerX  10.1.1.35.9717 . doi :10.1145/238168.238182. ISBN 978-0897918299. S2CID  13919278.