Войти
Иллюстрация концепции обмена ключами Диффи-Хеллмана Диффи-Хеллмана обмен ключами - это метод безопасного обмена криптографическими ключами по общедоступному каналу, который был одним из первых протоколов с открытым ключом по замыслу Ральфа Меркла и назван в честь Уитфилда Диффи и Мартина Хеллмана. DH является одним из первых практических примеров обмена общедоступными ключами, реализованных в области криптографии. Опубликованная в 1976 году Диффи и Хеллманом, это самая ранняя публично известная работа, в которой была предложена идея личного и соответствующего открытого ключей.
Традиционно для безопасной зашифрованной связи между двумя сторонами требовалось, чтобы они сначала обменялись ключами с помощью некоторых безопасных физических средств, таких как бумажные списки ключей, доставленные надежным курьером. Метод обмена ключами Диффи – Хеллмана позволяет двум сторонам, не имеющим предварительных сведений друг о друге, совместно установить общий секретный ключ по незащищенному каналу. Затем этот ключ можно использовать для шифрования последующих сообщений с помощью симметричного ключа . шифр.
Диффи – Хеллмана используется для защиты различных Интернет сервисов. Однако исследование, опубликованное в октябре 2015 года, показывает, что параметры, используемые в то время для многих Интернет-приложений ЦТ, недостаточно сильны, чтобы предотвратить взлом со стороны очень хорошо финансируемых злоумышленников, таких как службы безопасности некоторых стран.
Схема была опубликована Уитфилдом Диффи и Мартином Хеллманом в 1976 году, но в 1997 году выяснилось, что Джеймс Х. Эллис, Клиффорд Кокс и Малкольм Дж. Уильямсон из GCHQ, британского агентства по разведке сигналов, ранее в 1969 году показало, как может быть достигнута криптография с открытым ключом.
Хотя само соглашение о ключах Диффи-Хеллмана не аутентифицировано протокол согласования ключей, он обеспечивает основу для множества аутентифицированных протоколов и используется для обеспечения прямой секретности в Transport Layer Security эфемерных (называемых EDH или DHE в зависимости от набора шифров ).
Вскоре после этого этому методу последовал RSA, реализация криптографии с открытым ключом с использованием асимметричных алгоритмов.
Срок действия истек США Патент 4200770 от 1977 описывает теперь алгоритм общественного достояния. Он считает изобретателями Хеллмана, Диффи и Меркла.
В 2002 году Хеллман предложил назвать алгоритм Диффи – Хеллмана –Merkle key exchange в знак признания вклада Ральфа Меркла в изобретение криптографии с открытым ключом (Hellman, 2002), запись:
Система... с тех пор стала известна как Diffie-Hellman обмен ключами. Хотя эта система была впервые описана в статье Диффи и меня, это система распределения открытых ключей, концепция, разработанная Мерклом, и, следовательно, ее следует называть «обмен ключами Диффи – Хеллмана – Меркла», если с ней должны быть связаны имена.. Я надеюсь, что эта небольшая кафедра может помочь в этом стремлении признать равный вклад Меркла в изобретение криптографии с открытым ключом.
Обмен ключами Диффи-Хеллмана устанавливает общий секрет между двумя сторонами, которые могут использоваться для секретной связи для обмена данными в общедоступной сети. Аналогия иллюстрирует концепцию обмена открытыми ключами с использованием цветов вместо очень больших чисел:
Процесс начинается с того, что две стороны, Алиса и Боб, публично соглашаются на произвольный начальный цвет. это не нужно держать в секрете (но каждый раз должно быть разным). В этом примере цвет желтый. Каждый человек также выбирает секретный цвет, который он держит при себе - в данном случае красный и сине-зеленый. Важнейшей частью процесса является то, что Алиса и Боб каждый смешивают свой секретный цвет вместе со своим совместно используемым цветом, в результате чего получаются оранжево-коричневые и светло-голубые смеси соответственно, а затем публично обмениваются двумя смешанными цветами. Наконец, каждый из них смешивает цвет, полученный от партнера, со своим собственным цветом. В результате получается окончательная цветовая смесь (в данном случае желто-коричневая), идентичная окончательной цветовой смеси партнера.
Если третья сторона прислушивается к обмену, она будет знать только общий цвет (желтый) и первые смешанные цвета (оранжево-коричневый и голубой), но этой стороне будет сложно определить окончательный секретный цвет (желто-коричневый). Если вернуться к аналогии с реальным обменом с использованием больших чисел, а не цветов, такое определение требует больших вычислительных ресурсов. Невозможно выполнить вычисления за практическое время даже для современных суперкомпьютеров.
В самой простой и исходной реализации протокола используется мультипликативная группа целых чисел по модулю p, где p - простое число, а g - первообразный корень по модулю p. Эти два значения выбраны таким образом, чтобы гарантировать, что результирующий общий секрет может принимать любое значение от 1 до p – 1. Вот пример протокола с несекретными значениями синим цветом и секретными значениями красным .
И Алиса, и Боб пришли к одним и тем же значениям, потому что согласно модулю p,
Точнее,
Только a и b хранятся в секрете. Все остальные значения - p, g, g mod p и g mod p - отправляются в открытом виде. Сила схемы заключается в том, что для вычисления g mod p = g mod p требуется очень много времени, исходя только из знания p, g, g mod p и g mod p. После того, как Алиса и Боб вычислили общий секрет, они могут использовать его как ключ шифрования, известный только им, для отправки сообщений по одному и тому же открытому каналу связи.
Конечно, для обеспечения безопасности этого примера потребуются гораздо большие значения a, b и p, поскольку существует только 23 возможных результата n по модулю 23. Однако, если p является простым числом не менее 600 цифр, то даже самые быстрые современные компьютеры не могут найти данные только g, p и g mod p. Такая проблема называется проблемой дискретного логарифмирования. Вычисление g mod p известно как модульное возведение в степень и может быть выполнено эффективно даже для больших чисел. Обратите внимание, что g совсем не обязательно должно быть большим и на практике обычно является небольшим целым числом (например, 2, 3,...).
В таблице ниже показано, кто знает что, опять же с несекретными значениями синим цветом и секретными значениями красным . Здесь Ева - подслушивающая - она наблюдает за тем, что передается между Алисой и Бобом, но не изменяет содержание их сообщений.
|
|
|
Теперь s - это общий секретный ключ, и он известен как Алисе, так и Бобу, но не Еве. Обратите внимание, что Еве бесполезно вычислять AB, которое равно g mod p.
Примечание: Алисе должно быть сложно найти закрытый ключ Боба или Бобу найти закрытый ключ Алисы. Если Алисе нетрудно найти закрытый ключ Боба (или наоборот), Ева может просто подставить свою пару закрытый / открытый ключ, вставить открытый ключ Боба в свой закрытый ключ, создать поддельный общий секретный ключ и решить Закрытый ключ Боба (и используйте его для решения общего секретного ключа. Ева может попытаться выбрать пару открытого / закрытого ключей, которая упростит для нее поиск закрытого ключа Боба).
Другая демонстрация Диффи – Хеллмана (также использующая слишком маленькие для практического использования числа) дается здесь.
Вот более общее описание протокол:
И Алиса, и Боб теперь владеют элементом группы g, который может служить общим секретным ключом. Группа G удовлетворяет обязательному условию для защищенной связи, если нет эффективного алгоритма для определения g с учетом g, g и g.
Например, протокол эллиптической кривой Диффи – Хеллмана - это вариант, в котором вместо мультипликативной группы целых чисел по модулю p используются эллиптические кривые. Также были предложены варианты с использованием гиперэллиптических кривых. суперсингулярный обмен ключами изогении - это вариант Диффи-Хеллмана, разработанный для защиты от квантовых компьютеров.
Соглашение о ключах Диффи-Хеллмана не ограничивается согласованием ключа, разделяемого только двумя участниками. Любое количество пользователей может принять участие в соглашении, выполняя итерации протокола соглашения и обмениваясь промежуточными данными (которые сами по себе не должны храниться в секрете). Например, Алиса, Боб и Кэрол могут участвовать в соглашении Диффи-Хеллмана следующим образом, со всеми операциями, взятыми по модулю p:
Злоумышленник может видеть g, g, g, g, g и g, но не может использовать любую их комбинацию для эффективного воспроизведения g.
Чтобы распространить этот механизм на более крупные группы, необходимо соблюдать два основных принципа:
Эти принципы оставляют открытыми различные варианты выбора, в каком порядке участники вносят вклад в ключи. Самое простое и очевидное решение - расположить N участников в круг и заставить N ключей вращаться по кругу, пока в конечном итоге каждый ключ не будет добавлен всеми N участниками (заканчивая его владельцем), и каждый участник внесет свой вклад в N ключей. (заканчивая своими). Однако для этого требуется, чтобы каждый участник выполнил N модульных возведений в степень.
Выбирая более оптимальный порядок и полагаясь на тот факт, что ключи можно дублировать, можно уменьшить количество модульных возведений в степень, выполняемых каждым участником, до 2 (N) +1 с использованием подхода типа «разделяй и властвуй», приведенного здесь для восьми участников:
Как только эта операция будет завершена, все участники будут обладать секретом g, но каждый участник будет выполнено только четыре модульных возведения в степень, а не восемь, подразумеваемых простой круговой схемой.
Протокол считается защищенным от перехватчиков, если G и g выбраны правильно. В частности, порядок группы G должен быть большим, особенно если одна и та же группа используется для больших объемов трафика. Злоумышленник должен решить задачу Диффи – Хеллмана, чтобы получить g. В настоящее время это считается трудным для групп, порядок которых достаточно велик. Эффективный алгоритм для решения проблемы дискретного логарифмирования упростил бы вычисление a или b и решение проблемы Диффи – Хеллмана, что сделало бы эту и многие другие криптосистемы с открытым ключом небезопасными. Поля с малой характеристикой могут быть менее безопасными.
Порядок группы G должен иметь большой простой множитель, чтобы предотвратить использование алгоритма Полига – Хеллмана для получения или б. По этой причине простое число Софи Жермен q иногда используется для вычисления p = 2q + 1, называемого безопасным простым числом, поскольку в этом случае порядок G делится только на 2 и q.. Затем иногда выбирают g для генерации подгруппы порядка q группы G, а не G, так что символ Лежандра g никогда не показывает младший бит a. Протокол, использующий такой выбор, например, IKEv2.
g часто представляет собой небольшое целое число, такое как 2. Из-за случайного самосокращения задачи дискретного логарифмирования малое g одинаково безопасно. как любой другой генератор той же группы.
Если Алиса и Боб используют генераторы случайных чисел, выходные данные которых не являются полностью случайными и могут быть в некоторой степени предсказаны, то подслушивать гораздо проще.
В исходном описании обмен Диффи-Хеллмана сам по себе не обеспечивает аутентификации взаимодействующих сторон и, таким образом, уязвим для атаки типа «злоумышленник в середине». Мэллори (активный злоумышленник, выполняющий атаку «человек посередине») может установить два разных обмена ключами, один с Алисой, а другой с Бобом, эффективно маскируясь под Алису для Боба, и наоборот, позволяя ей расшифровать, а затем повторно -encrypt, сообщения передавались между ними. Обратите внимание, что Мэллори должен оставаться посередине, активно расшифровывая и повторно шифруя сообщения каждый раз, когда Алиса и Боб общаются. Если она когда-либо отсутствует, то ее предыдущее присутствие раскрывается Алисе и Бобу. Они будут знать, что все их личные разговоры были перехвачены и расшифрованы кем-то на канале. В большинстве случаев это не поможет им получить закрытый ключ Мэллори, даже если она использовала один и тот же ключ для обоих обменов.
Метод аутентификации взаимодействующих сторон друг с другом обычно необходим для предотвращения атак этого типа. Вместо этого можно использовать варианты протокола Диффи – Хеллмана, такие как протокол STS, чтобы избежать этих типов атак.
Алгоритм сита числового поля, который обычно является наиболее эффективным при решении задачи дискретного логарифмирования, состоит из четыре вычислительных шага. Первые три шага зависят только от порядка группы G, а не от конкретного числа, конечный журнал которого требуется. Оказывается, большая часть интернет-трафика использует одну из нескольких групп размером порядка 1024 бит или меньше. За счет предварительного вычисления первых трех шагов сита числового поля для наиболее распространенных групп злоумышленнику нужно выполнить только последний шаг, который требует гораздо меньше вычислительных затрат, чем первые три шага, чтобы получить конкретный логарифм.. Атака Logjam использовала эту уязвимость для взлома различных интернет-сервисов, которые позволяли использовать группы, порядок которых был 512-битным простым числом, так называемый уровень экспорта. Авторам потребовалось несколько тысяч ядер ЦП на неделю, чтобы предварительно вычислить данные для одного 512-битного простого числа. Как только это будет сделано, отдельные логарифмы могут быть решены примерно за минуту с использованием двух 18-ядерных процессоров Intel Xeon.
По оценке авторов атаки Logjam, для решения дискретного журнала потребовалось гораздо более сложное предварительное вычисление. Проблема для 1024-битного простого числа будет стоить порядка 100 миллионов долларов, что вполне укладывается в бюджет крупного национального разведывательного агентства, такого как Агентство национальной безопасности США (NSA). Авторы Logjam предполагают, что предварительные вычисления против широко используемых 1024-битных простых чисел DH лежат в основе утверждений в просочившихся документах АНБ о том, что АНБ способно взломать большую часть текущей криптографии.
Чтобы избежать этих уязвимостей, Авторы Logjam рекомендуют использовать криптографию на основе эллиптических кривых, для которой не известны подобные атаки. В противном случае они рекомендуют, чтобы порядок p группы Диффи-Хеллмана составлял не менее 2048 бит. По их оценкам, предварительное вычисление, необходимое для 2048-битного простого числа, в 10 раз сложнее, чем для 1024-битных простых чисел.
Шифрование с открытым ключом были предложены схемы, основанные на обмене ключами Диффи – Хеллмана. Первой такой схемой является шифрование Эль-Гамаля. Более современный вариант - Интегрированная схема шифрования.
Протоколы, которые достигают прямой секретности, генерируют новые пары ключей для каждого сеанса и отбрасывают их. в конце сеанса. Обмен ключами Диффи-Хеллмана - частый выбор для таких протоколов из-за быстрого создания ключей.
Когда Алиса и Боб используют общий пароль, они могут использовать соглашение о ключах с аутентификацией паролем (PK) форму Диффи – Хеллмана, чтобы предотвратить атаки человек-посередине. Одна простая схема - сравнить хэш из s, соединенный с паролем, вычисленным независимо на обоих концах канала. Особенностью этих схем является то, что злоумышленник может проверять только один конкретный пароль на каждой итерации с другой стороной, и поэтому система обеспечивает хорошую безопасность с относительно слабыми паролями. Этот подход описан в Рекомендации ITU-T X.1035, которая используется в стандарте домашних сетей G.hn.
Примером такого протокола является Протокол защищенного удаленного пароля.
Также возможно использовать Диффи – Хеллмана как часть открытого ключа инфраструктура, позволяющая Бобу зашифровать сообщение так, чтобы только Алиса могла его расшифровать, без предварительной связи между ними, за исключением того, что Боб доверял знанию открытого ключа Алисы. Открытый ключ Алисы: 
На практике алгоритм Диффи – Хеллмана таким образом не используется, поскольку RSA является доминирующим алгоритмом открытого ключа. Это во многом объясняется историческими и коммерческими причинами, а именно тем, что RSA Security создал центр сертификации для подписи ключей, который стал Verisign. Диффи – Хеллмана, как описано выше, нельзя напрямую использовать для подписи сертификатов. Однако алгоритмы подписи ElGamal и DSA математически связаны с ним, а также MQV, STS и IKE. компонент набора протоколов IPsec для защиты связи Internet Protocol.
