Обмен ключами Диффи – Хеллмана [nb 1] - это метод безопасного обмена криптографическими ключами по общедоступному каналу, который был одним из первых протоколов с открытым ключом, созданных Ральфом Мерклом и названных в честь Уитфилда Диффи и Мартина Хеллмана . [1] [2] DH - один из первых практических примеров обмена открытыми ключами, реализованных в области криптографии . Опубликованная в 1976 году Диффи и Хеллманом, это самая ранняя публично известная работа, в которой была предложена идея закрытого ключа и соответствующего открытого ключа.
Традиционно для безопасной зашифрованной связи между двумя сторонами требовалось, чтобы они сначала обменялись ключами с помощью некоторых безопасных физических средств, таких как бумажные списки ключей, доставленные доверенным курьером . Метод обмена ключами Диффи-Хеллмана позволяет двум сторонам, которые не знают друг друга заранее, совместно установить общий секретный ключ по незащищенному каналу . Затем этот ключ можно использовать для шифрования последующих сообщений с использованием шифра с симметричным ключом .
Диффи – Хеллмана используется для защиты множества Интернет- сервисов. Однако исследование, опубликованное в октябре 2015 года, показывает, что параметры, используемые в то время для многих Интернет-приложений ЦТ, недостаточно сильны, чтобы предотвратить взлом со стороны злоумышленников с очень хорошим финансированием, таких как службы безопасности некоторых стран. [3]
Схема была опубликована Уитфилдом Диффи и Мартином Хеллманом в 1976 г. [2], но в 1997 г. выяснилось, что Джеймс Эллис , [4] Клиффорд Кокс и Малкольм Дж. Уильямсон из GCHQ , британского агентства радиоэлектронной разведки, ранее имели в 1969 г. [5] было показано, как может быть достигнута криптография с открытым ключом. [6]
Хотя соглашение ключа Диффи-Хеллмана само по себе не является проверкой подлинности протокола ключ-соглашение , оно обеспечивает основу для различных аутентифицированных протоколов, а также используется для обеспечения прямой секретности в Transport Layer Security «ы временных режимов (называемых EDH или ДНЕ в зависимости от набора шифров ).
Вскоре за этим методом последовала RSA , реализация криптографии с открытым ключом с использованием асимметричных алгоритмов.
Истекло патент США 4200770 от 1977 г. описывает теперь государственно-домен алгоритма. Он считает изобретателями Хеллмана, Диффи и Меркла.
В 2002 году Хеллман предложил назвать алгоритм обмена ключами Диффи-Хеллмана-Меркла в знак признания вклада Ральфа Меркла в изобретение криптографии с открытым ключом (Hellman, 2002), написав:
Система ... с тех пор стала известна как обмен ключами Диффи-Хеллмана. Хотя эта система была впервые описана в статье Диффи и меня, это система распределения открытых ключей, концепция, разработанная Мерклом, и, следовательно, ее следует называть «обмен ключами Диффи-Хеллмана-Меркла», если с ней должны быть связаны имена. . Я надеюсь, что эта небольшая кафедра может помочь в этом стремлении признать равный вклад Меркла в изобретение криптографии с открытым ключом. [7]
Обмен ключами Диффи-Хеллмана устанавливает общий секрет между двумя сторонами, который может использоваться для секретной связи для обмена данными по общедоступной сети. Аналогия иллюстрирует концепцию обмена открытым ключом с использованием цветов вместо очень больших чисел:
Процесс начинается с того, что две стороны, Алиса и Боб , публично договариваются о произвольном начальном цвете, который не нужно держать в секрете (но каждый раз должен быть другим [3] ). В этом примере цвет желтый. Каждый человек также выбирает секретный цвет, который он держит при себе - в данном случае красный и сине-зеленый. Важнейшей частью процесса является то, что Алиса и Боб каждый смешивают свой секретный цвет вместе со своим совместно используемым цветом, в результате чего получаются оранжево-коричневые и светло-голубые смеси соответственно, а затем публично обмениваются двумя смешанными цветами. Наконец, каждый из них смешивает цвет, полученный от партнера, со своим собственным цветом. В результате получается окончательная цветовая смесь (в данном случае желто-коричневая), идентичная окончательной цветовой смеси партнера.
Если третья сторона прислушивается к обмену, она будет знать только общий цвет (желтый) и первые смешанные цвета (оранжево-коричневый и голубой), но этой стороне будет сложно определить окончательный секретный цвет (желтый). -коричневый). Возвращаясь к аналогии с реальным обменом, использующим большие числа, а не цвета, это определение требует больших вычислительных ресурсов. Невозможно произвести вычисления за практическое время даже для современных суперкомпьютеров .
Самая простая и оригинальная реализация [2] протокола использует мультипликативную группу целых чисел по модулю p , где p - простое число , а g - примитивный корень по модулю p . Эти два значения выбраны таким образом, чтобы гарантировать, что результирующий общий секрет может принимать любое значение от 1 до p –1. Вот пример протокола с несекретными значениями синим цветом и секретными значениями красным .
И Алиса, и Боб пришли к одним и тем же значениям, потому что по модулю 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 по модулю 23. Однако, если p является простым числом не менее 600 цифр, то даже самые быстрые современные компьютеры , использующие самый быстрый известный алгоритм не может найти в данную только г , р и г мод р . Такая проблема называется проблемой дискретного логарифмирования . [3] Вычисление g a mod p известно как модульное возведение в степень.и может быть эффективно выполнено даже для большого количества. Обратите внимание, что g совсем не обязательно должно быть большим и на практике обычно является небольшим целым числом (например, 2, 3, ...).
На приведенной ниже диаграмме показано неизвестно что, опять же с несекретными значениями синим цветом и секретными значениями красным . Здесь Ева является перехватчиком - она смотрит , что пересылается между Алисой и Бобом, но она не изменяет содержимое своих сообщений.
|
|
|
Теперь s - это общий секретный ключ, известный как Алисе, так и Бобу, но не Еве. Обратите внимание, что Еве бесполезно вычислять AB , которое равно g a + b mod p .
Примечание: Алисе должно быть сложно найти закрытый ключ Боба или Бобу - найти закрытый ключ Алисы. Если Алисе нетрудно найти закрытый ключ Боба (или наоборот), Ева может просто подставить свою пару закрытый / открытый ключ, вставить открытый ключ Боба в свой закрытый ключ, создать поддельный общий секретный ключ и решить Закрытый ключ Боба (и используйте его для нахождения общего секретного ключа. Ева может попытаться выбрать пару открытый / закрытый ключ, которая упростит для нее поиск закрытого ключа Боба).
Здесь дается еще одна демонстрация Диффи – Хеллмана (также использующая слишком маленькие для практического использования числа) . [8]
Вот более общее описание протокола: [9]
И Алиса, и Боб теперь владеют элементом группы g ab , который может служить общим секретным ключом. Группа G удовлетворяет необходимому условию безопасной связи, если нет эффективного алгоритма для определения g ab с учетом g , g a и g b .
Например, протокол Диффи – Хеллмана для эллиптических кривых - это вариант, в котором вместо мультипликативной группы целых чисел по модулю n используются эллиптические кривые. Также были предложены варианты с использованием гиперэллиптических кривых . Обмен суперсингулярен ключ изогенности вариант Диффи-Хеллмана , который был разработан , чтобы быть защищенным от квантовых компьютеров .
Соглашение о ключах Диффи – Хеллмана не ограничивается согласованием ключа, совместно используемого только двумя участниками. Любое количество пользователей может принять участие в соглашении, выполняя итерации протокола соглашения и обмениваясь промежуточными данными (которые сами по себе не должны храниться в секрете). Например, Алиса, Боб и Кэрол могут участвовать в соглашении Диффи-Хеллмана следующим образом, со всеми операциями, взятыми по модулю p :
Злоумышленник может видеть g a , g b , g c , g ab , g ac и g bc , но не может использовать любую их комбинацию для эффективного воспроизведения g abc .
Чтобы распространить этот механизм на более крупные группы, необходимо соблюдать два основных принципа:
Эти принципы оставляют открытыми различные варианты выбора того, в каком порядке участники вносят вклад в ключи. Самое простое и очевидное решение - расположить N участников в круг и заставить N ключей вращаться по кругу, пока в конечном итоге каждый ключ не будет добавлен всеми N участниками (заканчивая его владельцем), и каждый участник внесет свой вклад в N ключей. (заканчивая своими). Однако для этого требуется, чтобы каждый участник выполнил N модульных возведений в степень.
Выбирая более оптимальный порядок, опираясь на то , что ключи могут быть продублированы, то можно уменьшить количество модульных возведения в степень , выполняемых каждым участником входа 2 ( N ) + 1 , используя разделяй и властвуй стиле подход , данные здесь для восьми участников:
Как только эта операция будет завершена, все участники будут обладать секретом g abcdefgh , но каждый участник выполнил только четыре модульных возведения в степень, а не восемь, подразумеваемых простой круговой схемой.
Протокол считается защищенным от перехватчиков, если G и g выбраны правильно. В частности, порядок группы G должен быть большим, особенно если одна и та же группа используется для больших объемов трафика. Чтобы получить g ab, перехватчик должен решить проблему Диффи – Хеллмана . В настоящее время это считается трудным для групп, порядок которых достаточно велик. Эффективный алгоритм для решения проблемы дискретного логарифмирования упростил бы вычисление a или b и решение проблемы Диффи-Хеллмана, что сделало бы эту и многие другие криптосистемы с открытым ключом небезопасными. Поля с малыми характеристиками могут быть менее безопасными. [10]
Порядка из G должен иметь большой простой множитель , чтобы предотвратить использование алгоритма Pohlig-Hellman для получения или б . По этой причине простое число Софи Жермен q иногда используется для вычисления p = 2 q + 1 , называемого безопасным простым числом , поскольку в этом случае порядок G делится только на 2 и q . g затем иногда выбирают для генерации подгруппы порядка q группы G , а не G , так что символ Лежандра группы g никогда не показывает немного низкий порядок. Протокол, использующий такой выбор, - это, например, IKEv2 . [11]
g часто является малым целым числом, например 2. Из-за случайной самосокращаемости задачи дискретного логарифмирования малый g так же безопасен, как и любой другой генератор той же группы.
Если Алиса и Боб используют генераторы случайных чисел , выходные данные которых не являются полностью случайными и могут быть в некоторой степени предсказаны, то подслушивать будет намного проще.
В исходном описании обмен Диффи-Хеллмана сам по себе не обеспечивает аутентификацию взаимодействующих сторон и, таким образом, уязвим для атаки типа "злоумышленник посередине".. Мэллори (активный злоумышленник, выполняющий атаку «человек посередине») может установить два разных обмена ключами, один с Алисой, а другой с Бобом, эффективно маскируясь под Алису для Боба, и наоборот, позволяя ей расшифровать, а затем повторно -encrypt, сообщения передавались между ними. Обратите внимание, что Мэллори должен оставаться посередине, активно расшифровывая и повторно шифруя сообщения каждый раз, когда Алиса и Боб общаются. Если она когда-либо отсутствует, то ее предыдущее присутствие раскрывается Алисе и Бобу. Они будут знать, что все их личные разговоры были перехвачены и расшифрованы кем-то на канале. В большинстве случаев это не поможет им получить закрытый ключ Мэллори, даже если она использовала один и тот же ключ для обоих обменов.
Как правило, для предотвращения атак этого типа требуется метод аутентификации взаимодействующих сторон друг с другом. Вместо этого можно использовать варианты Диффи – Хеллмана, такие как протокол STS , чтобы избежать подобных атак.
Сито номера поле алгоритм, который , как правило , является наиболее эффективным при решении задачи дискретного логарифмирования , состоит из четырех вычислительных шагов. Первые три шага зависят только от порядка группы G, а не от конкретного числа, конечный журнал которого требуется. [12] Оказывается, большая часть интернет-трафика использует одну из нескольких групп, размер которых не превышает 1024 бит. [3] По предварительному вычислению первых три шага решета числового поля для наиболее распространенных групп, группа необходимо злоумышленник выполнить только последний шаг, который намного меньше , чем в вычислительном отношении дорого первые трех шагов, чтобы получить конкретный логарифм. заторАтака использовала эту уязвимость для компрометации различных интернет-сервисов, которые позволяли использовать группы, порядок которых был 512-битным простым числом, так называемая степень экспорта . Авторам потребовалось несколько тысяч ядер ЦП на неделю, чтобы предварительно вычислить данные для одного 512-битного простого числа. После этого отдельные логарифмы могут быть решены примерно за минуту с использованием двух 18-ядерных процессоров Intel Xeon. [3]
По оценкам авторов атаки Logjam, гораздо более сложное предварительное вычисление, необходимое для решения проблемы дискретного журнала для 1024-битного простого числа, будет стоить порядка 100 миллионов долларов, что вполне укладывается в бюджет крупного национального разведывательного агентства, такого как США Агентство национальной безопасности (NSA). Авторы Logjam предполагают, что предварительные вычисления против широко используемых 1024-битных простых чисел DH лежат в основе утверждений в просочившихся документах NSA о том, что NSA способно взломать большую часть текущей криптографии. [3]
Чтобы избежать этих уязвимостей, авторы Logjam рекомендуют использовать криптографию на основе эллиптических кривых , для которой не известно ни одной подобной атаки. В противном случае они рекомендуют, чтобы порядок p группы Диффи-Хеллмана составлял не менее 2048 бит. По их оценке, предварительные вычисления, необходимые для 2048-битных простых чисел, в 10 9 раз сложнее, чем для 1024-битных простых чисел. [3]
Были предложены схемы шифрования с открытым ключом, основанные на обмене ключами Диффи – Хеллмана. Первая такая схема - это шифрование Эль-Гамаля . Более современный вариант - это интегрированная схема шифрования .
Протоколы, обеспечивающие прямую секретность, генерируют новые пары ключей для каждого сеанса и отбрасывают их в конце сеанса. Обмен ключами Диффи-Хеллмана - частый выбор для таких протоколов из-за быстрого создания ключей.
Когда Алиса и Боб используют общий пароль, они могут использовать форму соглашения о ключах с аутентификацией паролем (PK) Диффи – Хеллмана для предотвращения атак типа «злоумышленник в середине». Одна простая схема для сравнения хэш из с сцепленных с паролем вычисленной самостоятельно на обоих концах канала. Особенностью этих схем является то, что злоумышленник может проверять только один конкретный пароль на каждой итерации с другой стороной, и поэтому система обеспечивает хорошую безопасность с относительно слабыми паролями. Этот подход описан в Рекомендации МСЭ-Т Рекомендация X.1035 , которая используется в G.hn домашних сетей стандарта.
Примером такого протокола является протокол Secure Remote Password .
Также возможно использовать Диффи – Хеллмана как часть инфраструктуры открытого ключа , что позволяет Бобу зашифровать сообщение так, чтобы только Алиса могла его расшифровать, без предварительной связи между ними, кроме Боба, который доверял знанию открытого ключа Алисы. . Открытый ключ Алисы - . Чтобы отправить ей сообщение, Боб выбирает случайную букву b, а затем отправляет Алисе (незашифрованной) вместе с сообщением, зашифрованным с помощью симметричного ключа . Только Алиса может определить , симметричный ключ и , следовательно , расшифровать сообщение , потому что только она имеет в (секретный ключ). Предварительно общий открытый ключ также предотвращает атаки типа «злоумышленник в середине».
На практике алгоритм Диффи – Хеллмана таким образом не используется, поскольку RSA является доминирующим алгоритмом открытого ключа. Это в значительной степени по историческим и коммерческим причинам, [ править ] , а именно , что RSA Security создан орган сертификата для подписи ключей , который стал Verisign . Диффи-Хеллмана, как описано выше, нельзя напрямую использовать для подписания сертификатов. Однако с ним математически связаны алгоритмы подписи Эль-Гамаля и DSA , а также MQV , STS и компонент IKE из набора протоколов IPsec для защиты интернет-протокола. коммуникации.
Поступило в августе 1975 г .; пересмотрено в сентябре 1977 г.
Использование внешних ссылок в этой статье может не соответствовать политикам или рекомендациям Википедии . ( Март 2016 г. ) |