Обмен ключами Диффи-Хеллмана

Метод обмена криптографическими ключами

При обмене ключами Диффи-Хеллмана две стороны приходят к общему секретному ключу, не передавая общий секретный ключ по общедоступному каналу.

Обмен ключами Диффи–Хеллмана ( DH ) ^{[nb 1]} — это математический метод безопасной генерации симметричного криптографического ключа по открытому каналу, один из первых протоколов с открытым ключом , задуманный Ральфом Мерклем и названный в честь Уитфилда Диффи и Мартина Хеллмана . ^{[1] [2]} DH — один из самых ранних практических примеров обмена открытыми ключами, реализованных в области криптографии. Опубликованная в 1976 году Диффи и Хеллманом, это самая ранняя публично известная работа, в которой была предложена идея закрытого ключа и соответствующего открытого ключа.

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

Алгоритм Диффи-Хеллмана используется для защиты различных интернет- сервисов. Однако исследование, опубликованное в октябре 2015 года, показывает, что параметры, используемые для многих приложений DH Internet в то время, недостаточно сильны, чтобы предотвратить взлом со стороны очень хорошо финансируемых злоумышленников, таких как службы безопасности некоторых стран. ^[3]

Схема была опубликована Уитфилдом Диффи и Мартином Хеллманом в 1976 году ^[2] , но в 1997 году выяснилось, что Джеймс Х. Эллис , ^[4] Клиффорд Кокс и Малкольм Дж. Уильямсон из GCHQ , британского агентства радиотехнической разведки, ранее, в 1969 году ^[5], показали , как можно реализовать криптографию с открытым ключом. ^[6]

Хотя обмен ключами Диффи-Хеллмана сам по себе является неаутентифицированным протоколом согласования ключей , он обеспечивает основу для множества аутентифицированных протоколов и используется для обеспечения прямой секретности в эфемерных режимах TLS ( называемых EDH или DHE в зависимости от набора шифров ).

Вскоре за этим методом последовал RSA — реализация криптографии с открытым ключом, использующая асимметричные алгоритмы.

Истекший патент США 4,200,770 ^[7] от 1977 года описывает алгоритм, который теперь является общественным достоянием . Он приписывает Хеллману, Диффи и Мерклу звание изобретателей.

Имя

В 2006 году Хеллман предложил назвать алгоритм обмена ключами Диффи–Хеллмана–Меркла в знак признания вклада Ральфа Меркла в изобретение криптографии с открытым ключом (Хеллман, 2006), написав:

Система... с тех пор стала известна как обмен ключами Диффи–Хеллмана. Хотя эта система была впервые описана в статье Диффи и мной, это система распределения открытых ключей, концепция, разработанная Мерклем, и, следовательно, ее следует называть «обмен ключами Диффи–Хеллмана–Мерклем», если с ней нужно ассоциировать имена. Я надеюсь, что эта небольшая кафедра может помочь в этом стремлении признать равный вклад Мерклемма в изобретение криптографии с открытым ключом. ^[8]

Описание

Общий обзор

Иллюстрация концепции обмена ключами Диффи-Хеллмана

Обмен ключами Диффи–Хеллмана устанавливает общий секрет между двумя сторонами, который может использоваться для секретной связи для обмена данными через публичную сеть. Аналогия иллюстрирует концепцию обмена открытыми ключами с использованием цветов вместо очень больших чисел:

Процесс начинается с того, что две стороны, Алиса и Боб , публично договариваются о произвольном начальном цвете, который не нужно держать в секрете. В этом примере цвет — желтый. Каждый человек также выбирает секретный цвет, который они держат при себе — в данном случае красный и голубой. Важнейшей частью процесса является то, что Алиса и Боб каждый смешивают свой собственный секретный цвет вместе с их общим цветом, в результате чего получаются оранжево-коричневые и светло-голубые смеси соответственно, а затем публично обмениваются двумя смешанными цветами. Наконец, каждый из них смешивает цвет, полученный от партнера, со своим собственным личным цветом. Результатом является конечная цветовая смесь (в данном случае желто-коричневая), которая идентична конечной цветовой смеси их партнера.

Если бы третья сторона прослушала обмен, она бы знала только общий цвет (желтый) и первые смешанные цвета (оранжево-коричневый и светло-голубой), но ей было бы очень трудно узнать окончательный секретный цвет (желто-коричневый). Возвращаясь к аналогии с реальным обменом, использующим большие числа, а не цвета, это определение является вычислительно дорогим. Это невозможно вычислить за практическое количество времени даже для современных суперкомпьютеров .

Криптографическое объяснение

Простейшая и оригинальная реализация ^[2] , позже формализованная как конечное поле Диффи–Хеллмана в RFC 7919 ^[9] , протокола использует мультипликативную группу целых чисел по модулю p , где p — простое число , а g — примитивный корень по модулю p . Эти два значения выбраны таким образом, чтобы гарантировать, что результирующий общий секрет может принимать любое значение от 1 до p –1. Вот пример протокола, где несекретные значения показаны синим цветом , а секретные — красным .

1. Алиса и Боб публично соглашаются использовать модуль p = 23 и основание g = 5 (что является примитивным корнем по модулю 23).
2. Алиса выбирает секретное целое число a = 4, затем отправляет Бобу A = g ^a mod p
   • A = 5 ⁴ mod 23 = 4 (в этом примере и A , и a имеют одинаковое значение 4, но обычно это не так)
3. Боб выбирает секретное целое число b = 3, затем отправляет Алисе B = g ^b mod p
   • В = 5 ³ мод 23 = 10
4. Алиса вычисляет s = B ^a mod p
   • с =10 ⁴ мод23=18
5. Боб вычисляет s = A ^b mod p
   • с =4 ³ мод23=18
6. Теперь у Алисы и Боба есть общий секрет (число 18).

И Алиса, и Боб пришли к одинаковым значениям, потому что по модулю p,

${\displaystyle {\color {Blue}A}^{\color {Red}b}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}ab}{\bmod {\color {Blue}p}}={\color {Blue}g}^{\color {Red}ba}{\bmod {\color {Blue}p}}={\color {Blue}B}^{\color {Red}a}{\bmod {\color {Blue}p}}}$

А точнее,

${\displaystyle ({\color {Blue}g}^{\color {Red}a}{\bmod {\color {Blue}p}})^{\color {Red}b}{\bmod {\color {Blue}p}}=({\color {Blue}g}^{\color {Red}b}{\bmod {\color {Blue}p}})^{\color {Red}a}{\bmod {\color {Blue}p}}}$

Только a и b хранятся в секрете. Все остальные значения – p , g , g ^a mod p и g ^b mod p – отправляются в открытом виде. Сила схемы заключается в том, что g ^ab mod p = g ^ba mod p требует чрезвычайно много времени для вычисления любым известным алгоритмом только на основе знания p , g , g ^a mod p и g ^b mod p . Такая функция, которую легко вычислить, но трудно инвертировать, называется односторонней функцией . Как только Алиса и Боб вычислят общий секрет, они могут использовать его в качестве ключа шифрования, известного только им, для отправки сообщений по одному и тому же открытому каналу связи.

Конечно, для того, чтобы сделать этот пример безопасным, понадобятся гораздо большие значения a , b , и p , поскольку существует только 23 возможных результата n mod 23. Однако, если p является простым числом, состоящим по крайней мере из 600 цифр, то даже самые быстрые современные компьютеры, использующие самый быстрый известный алгоритм, не смогут найти заданные только g , p и g ^a mod p . Такая задача называется задачей дискретного логарифма . ^[3] Вычисление g ^a mod p известно как модульное возведение в степень и может быть выполнено эффективно даже для больших чисел. Обратите внимание, что g совсем не обязательно должно быть большим, и на практике обычно является небольшим целым числом (например, 2, 3, ...).

График секретности

На диаграмме ниже изображено, кто знает что, опять же, несекретные значения синим цветом , а секретные — красным . Здесь Ева — подслушиватель — она наблюдает за тем, что передается между Алисой и Бобом, но она не меняет содержание их сообщений.

• g , общедоступная (примитивная корневая) база, известная Алисе, Бобу и Еве. g = 5
• p , открытый (простой) модуль, известный Алисе, Бобу и Еве. p = 23
• a , закрытый ключ Алисы, известный только Алисе. a = 6
• b , закрытый ключ Боба, известный только Бобу. b = 15
• A — открытый ключ Алисы, известный Алисе, Бобу и Еве. A = g ^a mod p = 8
• B — открытый ключ Боба, известный Алисе, Бобу и Еве. B = g ^b mod p = 19

Теперь s — это общий секретный ключ, и он известен как Алисе, так и Бобу, но не Еве. Обратите внимание, что Еве не нужно вычислять AB , который равен g ^{a + b} mod p .

Примечание: Алисе должно быть сложно найти закрытый ключ Боба, а Бобу — закрытый ключ Алисы. Если Алисе несложно найти закрытый ключ Боба (или наоборот), то подслушиватель, Ева , может просто подставить свою собственную пару закрытый/открытый ключ, вставить открытый ключ Боба в свой закрытый ключ, создать поддельный общий секретный ключ и найти закрытый ключ Боба (и использовать его для поиска общего секретного ключа). Ева может попытаться выбрать пару открытый/закрытый ключ, которая облегчит ей задачу найти закрытый ключ Боба.

Обобщение на конечные циклические группы

Вот более общее описание протокола: ^[10]

1. Алиса и Боб договариваются о натуральном числе n и порождающем элементе g в конечной циклической группе G порядка n . (Обычно это делается задолго до остальной части протокола; предполагается, что g и n известны всем злоумышленникам.) Группа G записывается мультипликативно.
2. Алиса выбирает случайное натуральное число a, где 1 < a < n , и отправляет элемент g ^a из G Бобу.
3. Боб выбирает случайное натуральное число b, где 1 < b < n , и отправляет элемент g ^b из G Алисе.
4. Алиса вычисляет элемент ( g ^b ) ^a = g ^ba из G.
5. Боб вычисляет элемент ( g ^a ) ^b = g ^ab из G.

Теперь и Алиса, и Боб владеют элементом группы g ^ab = g ^ba , который может служить общим секретным ключом. Группа G удовлетворяет требуемому условию для безопасной связи , пока не существует эффективного алгоритма для определения g ^ab по данным g , g ^a и g ^b .

Например, протокол Диффи–Хеллмана на эллиптической кривой — это вариант, который представляет элемент G как точку на эллиптической кривой, а не как целое число по модулю n. Также были предложены варианты, использующие гиперэллиптические кривые . Обмен ключами суперсингулярной изогении — это вариант Диффи–Хеллмана, который был разработан для защиты от квантовых компьютеров , но был взломан в июле 2022 года. ^[11]

Эфемерные и/или статические ключи

Используемые ключи могут быть либо эфемерными, либо статическими (долгосрочными), но могут быть даже смешанными, так называемыми полустатическими DH. Эти варианты имеют разные свойства и, следовательно, разные варианты использования. Обзор многих вариантов, а также некоторые обсуждения можно найти, например, в NIST SP 800-56A. ^[12] Базовый список:

1. эфемерный, эфемерный: Обычно используется для согласования ключей. Обеспечивает прямую секретность , но не подлинность .
2. static, static: Генерирует долгосрочный общий секрет. Не обеспечивает прямой секретности, но неявную аутентичность. Поскольку ключи статичны, это, например, не защитит от атак повторного воспроизведения .
3. эфемерный, статический: например, используется в шифровании ElGamal или Integrated Encryption Scheme (IES) . При использовании в соглашении о ключах он может обеспечить неявную одностороннюю аутентичность (эфемерная сторона может проверить подлинность статической стороны). Прямая секретность не обеспечивается.

Можно использовать эфемерные и статические ключи в одном соглашении о ключах для обеспечения большей безопасности, как, например, показано в NIST SP 800-56A, но их также можно объединить в одном обмене ключами DH, который тогда называется тройным DH (3-DH).

Тройной Диффи-Хеллман (3-DH)

В 1997 году Саймон Блейк-Уилсон, Дон Джонсон и Альфред Менезес предложили своего рода тройной DH ^[13] , который был улучшен К. Кудлой и К. Г. Патерсоном в 2005 году ^[14] и показал свою безопасность.

Долгосрочные секретные ключи Алисы и Боба обозначаются как a и b соответственно, с открытыми ключами A и B , а также парами эфемерных ключей x, X и y, Y. Тогда протокол будет следующим:

Долгосрочные открытые ключи должны быть каким-то образом переданы. Это можно сделать заранее в отдельном, доверенном канале, или открытые ключи можно зашифровать с использованием некоторого частичного соглашения о ключах для сохранения анонимности. Для получения дополнительных подробностей, а также других улучшений, таких как защита сторонних каналов или явное подтверждение ключа , а также ранние сообщения и дополнительная аутентификация пароля, см., например, патент США «Расширенное модульное рукопожатие для соглашения о ключах и необязательной аутентификации». ^[15]

Расширенный тройной алгоритм Диффи-Хеллмана (X3DH)

X3DH изначально был предложен как часть алгоритма Double Ratchet, используемого в Signal Protocol . Протокол обеспечивает прямую секретность и криптографическую отрицаемость. Он работает на эллиптической кривой. ^[16]

Протокол использует пять открытых ключей. У Алисы есть идентификационный ключ IK _A и эфемерный ключ EK _A . У Боба есть идентификационный ключ IK _B , подписанный предварительный ключ SPK _B и одноразовый предварительный ключ OPK _B . ^[16] Боб сначала публикует свои три ключа на сервере, который Алиса загружает и проверяет подпись. Затем Алиса инициирует обмен с Бобом. ^[16] OPK необязателен. ^[16]

Операция с более чем двумя сторонами

Соглашение о ключах Диффи–Хеллмана не ограничивается согласованием ключа, совместно используемого только двумя участниками. Любое количество пользователей может принять участие в соглашении, выполняя итерации протокола соглашения и обмениваясь промежуточными данными (которые сами по себе не должны храниться в секрете). Например, Алиса, Боб и Кэрол могут участвовать в соглашении Диффи–Хеллмана следующим образом, при этом все операции считаются по модулю p :

1. Стороны договариваются о параметрах алгоритма p и g .
2. Стороны генерируют свои закрытые ключи, называемые a , b и c .
3. Алиса вычисляет g ^mod p и отправляет его Бобу.
4. Боб вычисляет ( g ^a ) ^b mod p = g ^ab mod p и отправляет его Кэрол.
5. Кэрол вычисляет ( g ^ab ) ^c mod p = g ^abc mod p и использует это как свой секрет.
6. Боб вычисляет g ^b mod p и отправляет его Кэрол.
7. Кэрол вычисляет ( g ^b ) ^c mod p = g ^bc mod p и отправляет его Алисе.
8. Алиса вычисляет ( g ^bc ) ^a mod p = g ^bca mod p = g ^abc mod p и использует это как свой секрет.
9. Кэрол вычисляет g ^c mod p и отправляет его Алисе.
10. Алиса вычисляет ( g ^c ) ^a mod p = g ^ca mod p и отправляет его Бобу.
11. Боб вычисляет ( g ^ca ) ^b mod p = g ^cab mod p = g ^abc mod p и использует это как свой секрет.

Подслушиватель смог увидеть g ^a mod p , g ^b mod p , g ^c mod p , g ^ab mod p , g ^ac mod p и g ^bc mod p , но не может использовать ни одну из этих комбинаций для эффективного воспроизведения g ^abc mod p .

Чтобы распространить этот механизм на более крупные группы, необходимо соблюдать два основных принципа:

• Начиная с «пустого» ключа, состоящего только из g , секрет создается путем возведения текущего значения в степень каждого участника один раз в любом порядке (первое такое возведение в степень дает собственный открытый ключ участника).
• Любое промежуточное значение (имеющее до N −1 примененных экспонент, где N — число участников в группе) может быть раскрыто публично, но окончательное значение (имеющее все N примененных экспонент) составляет общий секрет и, следовательно, никогда не должно раскрываться публично. Таким образом, каждый пользователь должен получить свою копию секрета, применив свой собственный закрытый ключ последним (в противном случае не было бы возможности для последнего участника сообщить окончательный ключ его получателю, поскольку этот последний участник превратил бы ключ в тот самый секрет, который группа хотела защитить).

Эти принципы оставляют открытыми различные варианты выбора порядка, в котором участники вносят вклад в ключи. Самое простое и очевидное решение — расположить N участников по кругу и заставить N ключей вращаться по кругу, пока в конечном итоге каждый ключ не будет внесен всеми N участниками (заканчивающимися его владельцем) и каждый участник не внесет вклад в N ключей (заканчивающимися своим собственным). Однако для этого требуется, чтобы каждый участник выполнил N модульных возведений в степень.

Выбрав более желательный порядок и полагаясь на тот факт, что ключи могут дублироваться, можно сократить количество модульных возведений в степень, выполняемых каждым участником, до log ₂ ( N ) + 1 , используя подход в стиле «разделяй и властвуй» , приведенный здесь для восьми участников:

1. Участники A, B, C и D выполняют по одному возведению в степень, получая g ^abcd ; это значение отправляется E, F, G и H. Взамен участники A, B, C и D получают g ^efgh .
2. Участники A и B выполняют по одному возведению в степень, получая g ^efghab , который они отправляют C и D, в то время как C и D делают то же самое, получая g ^efghcd , который они отправляют A и B.
3. Участник A выполняет возведение в степень, получая g ^efghcda , который он отправляет B; аналогично, B отправляет g ^efghcdb A. C и D делают то же самое.
4. Участник A выполняет одно последнее возведение в степень, получая секрет g ^efghcdba = g ^abcdefgh , в то время как B делает то же самое, чтобы получить g ^efghcdab = g ^abcdefgh ; снова C и D делают то же самое.
5. Участники E–H одновременно выполняют одни и те же операции, используя g ^abcd в качестве отправной точки.

После завершения этой операции все участники будут обладать секретом g ^abcdefgh , но каждый участник выполнит только четыре модульных возведения в степень, а не восемь, как подразумевает простая круговая структура.

Безопасность и практические соображения

Протокол считается защищенным от подслушивания, если G и g выбраны правильно. В частности, порядок группы G должен быть большим, особенно если одна и та же группа используется для больших объемов трафика. Подслушивающему необходимо решить задачу Диффи–Хеллмана, чтобы получить g ^ab . В настоящее время это считается сложным для групп, порядок которых достаточно велик. Эффективный алгоритм для решения задачи дискретного логарифма облегчил бы вычисление a или b и решение задачи Диффи–Хеллмана, что делает эту и многие другие криптосистемы с открытым ключом небезопасными. Поля с малой характеристикой могут быть менее защищенными. ^[17]

Порядок G должен иметь большой простой множитель , чтобы предотвратить использование алгоритма Полига–Хеллмана для получения a или b . По этой причине простое число Софи Жермен q иногда используется для вычисления p = 2 q + 1 , называемое безопасным простым числом , поскольку тогда порядок G делится только на 2 и q . Иногда для генерации подгруппы порядка q группы G выбирается g , а не G , так что символ Лежандра g a никогда не раскрывает младший бит ^a . Протокол, использующий такой выбор, — это, например, IKEv2 . [ ^18]

Генератор g часто представляет собой небольшое целое число, например 2. Из-за случайной самоприводимости задачи дискретного логарифмирования небольшое число g столь же безопасно, как и любой другой генератор той же группы.

Если Алиса и Боб используют генераторы случайных чисел , выходные данные которых не являются полностью случайными и могут быть в некоторой степени предсказаны, то подслушать их становится гораздо проще.

В оригинальном описании обмен Диффи-Хеллмана сам по себе не обеспечивает аутентификацию взаимодействующих сторон и может быть уязвим для атаки «человек посередине» . Мэллори (активный злоумышленник, выполняющий атаку «человек посередине») может установить два отдельных обмена ключами, один с Алисой, а другой с Бобом, эффективно маскируясь под Алису для Боба, и наоборот, что позволяет ей расшифровывать, а затем повторно шифровать сообщения, передаваемые между ними. Обратите внимание, что Мэллори должна быть в середине с самого начала и продолжать быть таковой, активно расшифровывая и повторно шифруя сообщения каждый раз, когда Алиса и Боб общаются. Если она прибудет после того, как ключи были сгенерированы, а зашифрованный разговор между Алисой и Бобом уже начался, атака не будет успешной. Если она когда-либо отсутствует, ее предыдущее присутствие тогда раскрывается Алисе и Бобу. Они будут знать, что все их личные разговоры были перехвачены и декодированы кем-то в канале. В большинстве случаев это не поможет им получить закрытый ключ Мэллори, даже если она использовала один и тот же ключ для обоих обменов.

Метод аутентификации общающихся сторон друг с другом обычно необходим для предотвращения этого типа атак. Варианты протокола Диффи-Хеллмана, такие как протокол STS , могут использоваться вместо этого, чтобы избежать этих типов атак.

Атака типа «отказ в обслуживании»

В CVE , выпущенном в 2021 году ( CVE-2002-20001 ), раскрыта атака типа «отказ в обслуживании» (DoS) против вариантов протокола, использующих эфемерные ключи, называемая атакой D(HE)at. ^[19] Атака использует то, что обмен ключами Диффи–Хеллмана позволяет злоумышленникам отправлять произвольные числа, которые на самом деле не являются открытыми ключами, что запускает дорогостоящие вычисления модульного возведения в степень на стороне жертвы. В другом выпущенном CVE раскрыто, что реализации обмена ключами Диффи–Хеллмана могут использовать длинные закрытые экспоненты ( CVE-2022-40735 ), которые, как утверждается, делают вычисления модульного возведения в степень неоправданно дорогими ^[20] или могут излишне проверять открытый ключ партнера ( CVE-2024-41996 ), что имеет такие же требования к ресурсам, как и вычисление ключа с использованием длинной экспоненты. ^[21] Злоумышленник может использовать обе уязвимости одновременно.

Практические атаки на интернет-трафик

Алгоритм решета числового поля , который, как правило, является наиболее эффективным при решении задачи дискретного логарифма , состоит из четырех вычислительных шагов. Первые три шага зависят только от порядка группы G, а не от конкретного числа, конечный логарифм которого требуется. ^[22] Оказывается, что большая часть интернет-трафика использует одну из нескольких групп, имеющих порядок 1024 бит или меньше. ^[3] Предварительно вычисляя первые три шага решета числового поля для наиболее распространенных групп, злоумышленнику нужно выполнить только последний шаг, который намного менее затратен в вычислительном отношении, чем первые три шага, чтобы получить определенный логарифм. Атака Logjam использовала эту уязвимость для компрометации различных интернет-сервисов, которые позволяли использовать группы, порядок которых был 512-битным простым числом, так называемым экспортным классом . Авторам потребовалось несколько тысяч ядер ЦП в течение недели для предварительного вычисления данных для одного 512-битного простого числа. После этого отдельные логарифмы можно было решать примерно за минуту, используя два 18-ядерных процессора Intel Xeon. ^[3]

По оценкам авторов атаки Logjam, гораздо более сложные предварительные вычисления, необходимые для решения задачи дискретного логарифма для 1024-битного простого числа, обойдутся примерно в 100 миллионов долларов, что вполне соответствует бюджету крупного национального разведывательного агентства, такого как Агентство национальной безопасности США (АНБ). Авторы Logjam предполагают, что предварительные вычисления для широко используемых 1024-битных простых чисел DH стоят за утверждениями в просочившихся документах АНБ о том, что АНБ способно взломать большую часть современной криптографии. ^[3]

Чтобы избежать этих уязвимостей, авторы Logjam рекомендуют использовать криптографию на основе эллиптических кривых , для которой не известно ни одной похожей атаки. В противном случае они рекомендуют, чтобы порядок p группы Диффи–Хеллмана был не менее 2048 бит. Они оценивают, что предварительные вычисления, необходимые для 2048-битного простого числа, в 10 ⁹ раз сложнее, чем для 1024-битных простых чисел. ^[3]

Другие применения

Шифрование

Были предложены схемы шифрования с открытым ключом, основанные на обмене ключами Диффи–Хеллмана. Первой такой схемой является шифрование Эль-Гамаля . Более современный вариант — Интегрированная схема шифрования .

Прямая секретность

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

Соглашение о ключе с аутентификацией по паролю

Когда Алиса и Боб делятся паролем, они могут использовать форму соглашения о ключах с аутентификацией паролем (PK) Диффи-Хеллмана для предотвращения атак типа «человек посередине». Одна из простых схем заключается в сравнении хеша s, объединенного с паролем, вычисленным независимо на обоих концах канала. Особенностью этих схем является то, что злоумышленник может проверить только один конкретный пароль на каждой итерации с другой стороной, и поэтому система обеспечивает хорошую безопасность с относительно слабыми паролями. Этот подход описан в Рекомендации МСЭ-Т X.1035 , которая используется стандартом домашних сетей G.hn.

Примером такого протокола является протокол Secure Remote Password .

Открытый ключ

Также возможно использовать Диффи-Хеллмана как часть инфраструктуры открытого ключа , позволяя Бобу шифровать сообщение так, что только Алиса сможет его расшифровать, без какой-либо предварительной коммуникации между ними, кроме как Боб, имеющий доверенное знание открытого ключа Алисы. Открытый ключ Алисы — . Чтобы отправить ей сообщение, Боб выбирает случайное b , а затем отправляет Алисе (незашифрованное) вместе с сообщением, зашифрованным симметричным ключом . Только Алиса может определить симметричный ключ и, следовательно, расшифровать сообщение, поскольку только у нее есть a (закрытый ключ). Предварительно общий открытый ключ также предотвращает атаки типа «человек посередине». ${\displaystyle (g^{a}{\bmod {p}},g,p)}$ ${\displaystyle g^{b}{\bmod {p}}}$ ${\displaystyle (g^{a})^{b}{\bmod {p}}}$

На практике Диффи-Хеллмана таким образом не используется, поскольку RSA является доминирующим алгоритмом открытого ключа. Это в значительной степени обусловлено историческими и коммерческими причинами, ^{[ требуется ссылка ]} а именно тем, что RSA Security создала центр сертификации для подписи ключей, который стал Verisign . Диффи-Хеллмана, как было подробно описано выше, нельзя напрямую использовать для подписи сертификатов. Однако алгоритмы подписи Эль-Гамаля и DSA математически связаны с ним, как и MQV , STS и компонент IKE набора протоколов IPsec для защиты коммуникаций по протоколу Интернета .

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

• Обмен ключами Диффи-Хеллмана на эллиптических кривых
• Суперсингулярный изогенический обмен ключами
• Прямая секретность
• Проблема Диффи–Хеллмана
• Модульное возведение в степень
• Атака типа «отказ в обслуживании»
• Постквантовый расширенный алгоритм Диффи–Хеллмана

Примечания

1. Синонимы обмена ключами Диффи–Хеллмана включают:
   • Обмен ключами Диффи-Хеллмана-Меркла
   • Соглашение о ключах Диффи-Хеллмана
   • Установление ключа Диффи-Хеллмана
   • Согласование ключей Диффи-Хеллмана
   • Экспоненциальный обмен ключами
   • Протокол Диффи–Хеллмана
   • Рукопожатие Диффи–Хеллмана

Ссылки

1. Merkle, Ralph C. (апрель 1978 г.). «Безопасные коммуникации по незащищенным каналам». Communications of the ACM . 21 (4): 294–299. CiteSeerX  10.1.1.364.5157 . doi :10.1145/359460.359473. S2CID  6967714. Получено в августе 1975 г.; пересмотрено в сентябре 1977 г.
2. Диффи, Уитфилд ; Хеллман, Мартин Э. (ноябрь 1976 г.). «Новые направления в криптографии» (PDF) . Труды IEEE по теории информации . 22 (6): 644–654. CiteSeerX 10.1.1.37.9720 . doi :10.1109/TIT.1976.1055638. Архивировано (PDF) из оригинала 29.11.2014. 
3. Адриан, Дэвид и др. (октябрь 2015 г.). «Несовершенная прямая секретность: как протокол Диффи–Хеллмана терпит неудачу на практике» (PDF) . Архивировано (PDF) из оригинала 2015-09-06.
4. Эллис, Дж. Х. (январь 1970 г.). «Возможность несекретного цифрового шифрования» (PDF) . Исследовательский отчет CESG . Архивировано из оригинала (PDF) 2014-10-30 . Получено 2015-08-28 .
5. "Возможность безопасного секретного цифрового шифрования" (PDF) . Архивировано (PDF) из оригинала 2017-02-16 . Получено 2017-07-08 .
6. "GCHQ trio recognize for key to secure shopping online". BBC News . 5 октября 2010 г. Архивировано из оригинала 10 августа 2014 г. Получено 5 августа 2014 г.
7. Патент США 4200770 
8. Хеллман, Мартин Э. (май 2002 г.), «Обзор криптографии с открытым ключом» (PDF) , IEEE Communications Magazine , 40 (5): 42–49, CiteSeerX 10.1.1.127.2652 , doi :10.1109/MCOM.2002.1006971, S2CID  9504647, архивировано (PDF) из оригинала 2016-04-02 
9. Вонг, Дэвид (2021). «Стандарты обмена ключами». Real World Cryptography. Мэннинг. ISBN 9781617296710– через Google Книги.
10. Бухманн, Йоханнес А. (2013). Введение в криптографию (второе изд.). Springer Science+Business Media. стр. 190–191. ISBN 978-1-4419-9003-7.
11. Кастрик, Воутер; Декру, Томас (апрель 2023 г.). «Эффективная атака восстановления ключа на SIDH» (PDF) . Ежегодная международная конференция по теории и применению криптографических методов : 423–447. Архивировано из оригинала (PDF) 2024-09-26.
12. Баркер, Элейн; Чен, Лили; Рогинский, Аллен; Василев, Апостол; Дэвис, Ричард (2018-04-16). Рекомендации по схемам установления парных ключей с использованием дискретной логарифмической криптографии (отчет). Национальный институт стандартов и технологий.
13. Блейк-Уилсон, Саймон; Джонсон, Дон; Менезес, Альфред (1997), Протоколы согласования ключей и анализ их безопасности , CiteSeerX 10.1.1.25.387 , doi :10.1007/BFb0024447 
14. Кудла, Кэролайн; Патерсон, Кеннет Г. (2005). «Доказательства модульной безопасности для протоколов согласования ключей». В Рой, Бимал (ред.). Достижения в криптологии - ASIACRYPT 2005 (PDF) . Конспект лекций по информатике. Том 3788. Берлин, Гейдельберг: Springer. стр. 549–565. doi : 10.1007/11593447_30 . ISBN 978-3-540-32267-2.
15. US11025421B2, Фэй, Бьорн, «Расширенное модульное рукопожатие для согласования ключей и дополнительной аутентификации», выпущено 01.06.2021 
16. "Спецификации >> Протокол согласования ключей X3DH". Signal Messenger .
17. Barbulescu, Razvan; Gaudry, Pierrick; Joux, Antoine; Thomé, Emmanuel (2014). "Эвристический квазиполиномиальный алгоритм для дискретного логарифма в конечных полях малой характеристики" (PDF) . Advances in Cryptology – EUROCRYPT 2014 . Труды 33-й ежегодной международной конференции по теории и применению криптографических методов. Lecture Notes in Computer Science. Vol. 8441. Копенгаген, Дания. стр. 1–16. doi :10.1007/978-3-642-55220-5_1. ISBN 978-3-642-55220-5. Архивировано (PDF) из оригинала 2020-03-22.
18. «Протокол обмена ключами в Интернете (IKEv2) RFC 4306». Internet Engineeringrg/web/20150107073645/http://www.ietf.org/rfc/rfc4306.txt.
19. Пфайффер, Силард; Тихани, Норберт (25 декабря 2023 г.). «D(HE)at: Практическая атака отказа в обслуживании на конечно-полевый обмен ключами Диффи-Хеллмана». IEEE Access . 12 : 957–980. doi : 10.1109/ACCESS.2023.3347422 . Архивировано из оригинала 22.04.2024.
20. van Oorschot, PC; Wiener, MJ (1996). «О соглашении о ключах Диффи-Хеллмана с короткими экспонентами». Advances in Cryptology — EUROCRYPT '96 . Springer, Berlin, Heidelberg (опубликовано в 2001 г.). стр. 332–343. doi :10.1007/3-540-68339-9_29. Архивировано из оригинала 2023-02-19.
21. Элейн, Баркер; Лили, Чен; Аллен, Рогинский; Апостол, Василев; Ричард, Дэвис (2018). «Рекомендации по схемам установления парных ключей с использованием дискретной логарифмической криптографии». Национальный институт стандартов и технологий. doi : 10.6028/NIST.SP.800-56Ar3 .{{cite web}}: CS1 maint: url-status (link)
22. Уитфилд Диффи, Пол К. Ван Ооршот и Майкл Дж. Винер «Аутентификация и обмен аутентифицированными ключами», в Designs, Codes and Cryptography, 2, 107–125 (1992), Раздел 5.2, доступно как Приложение B к патенту США 5,724,425

Общие ссылки

• Gollman, Dieter (2011). Computer Security (2nd ed.). Западный Сассекс, Англия: John Wiley & Sons, Ltd. ISBN 978-0470741153.
• Уильямсон, Малкольм Дж. (21 января 1974 г.). Несекретное шифрование с использованием конечного поля (PDF) (Технический отчет). Communications Electronics Security Group. Архивировано (PDF) из оригинала 2017-03-23 . Получено 2017-03-22 .
• Уильямсон, Малкольм Дж. (10 августа 1976 г.). Размышления о более дешевом несекретном шифровании (PDF) (технический отчет). Communications Electronics Security Group. Архивировано (PDF) из оригинала 2004-07-19 . Получено 2015-08-25 .
• История несекретного шифрования Дж. Х. Эллис 1987 (файл PDF 28K) (версия HTML)
• Первые десять лет криптографии с открытым ключом Уитфилд Диффи, Труды IEEE, т. 76, № 5, май 1988 г., стр. 560–577 (файл PDF объемом 1,9 МБ)
• Менезес, Альфред ; ван Ооршот, Пол ; Ванстоун, Скотт (1997). Справочник по прикладной криптографии Бока-Ратон, Флорида: CRC Press. ISBN 0-8493-8523-7 . (Доступно онлайн) 
• Сингх, Саймон (1999) Книга кодов: эволюция секретности от Марии Стюарт до квантовой криптографии Нью-Йорк: Doubleday ISBN 0-385-49531-5 
• Обзор криптографии с открытым ключом Мартин Э. Хеллман, IEEE Communications Magazine, май 2002 г., стр. 42–49. (PDF-файл объемом 123 КБ)

Внешние ссылки

• Устное интервью с Мартином Хеллманом, Институт Чарльза Бэббиджа , Университет Миннесоты. Ведущий ученый-криптограф Мартин Хеллман обсуждает обстоятельства и фундаментальные идеи своего изобретения криптографии с открытым ключом с соавторами Уитфилдом Диффи и Ральфом Мерклем в Стэнфордском университете в середине 1970-х годов.
• RFC 2631 – Метод согласования ключей Диффи–Хеллмана . Э. Рескорла. Июнь 1999 г.
• RFC 3526 – Более модульные экспоненциальные (MODP) группы Диффи–Хеллмана для обмена ключами в Интернете (IKE) . Т. Кивинен, М. Коджо, Безопасность коммуникаций SSH. Май 2003 г.
• Краткое изложение ANSI X9.42: Соглашение о симметричных ключах с использованием дискретной логарифмической криптографии (файл PDF размером 64 КБ) (Описание стандартов ANSI 9)
• Выступление Мартина Хеллмана в 2007 году, видео на YouTube
• Команда мечты в области криптовалют Диффи и Хеллман выиграла премию Тьюринга 2015 года в размере 1 миллиона долларов (она же «Нобелевская премия по вычислительной технике»)
• Демонстрация Диффи-Хеллмана, написанная на Python3. Эта демонстрация должным образом поддерживает очень большие ключевые данные и при необходимости принудительно использует простые числа.