Задача Диффи – Хеллмана

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

• 1 Описание проблемы
• 2 Вычислительная сложность
• 3 Другие варианты
• 4 Ссылки

Неформально проблема Диффи – Хеллмана сформулирована следующим образом:

Учитывая элемент g и значения g и g, каково значение g?

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

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

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

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

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