Диффи хеллман: Алгоритм Диффи — Хеллмана / Хабр

Диффи—Хеллмана, Эль-Гамаля, MTI/A(0), STS / Хабр

Предисловие

Данный текст будет являться одной из переписанных глав для учебного пособия по защите информации кафедры радиотехники и систем управления, а также, с этого учебного кода, кафедры защиты информации МФТИ (ГУ). Полностью учебник доступен на github (см. также draft releases). На Хабре планирую выкладывать новые «большие» куски, во-первых, чтобы собрать полезные комментарии и замечания, во-вторых, дать сообществу больше обзорного материала по полезным и интересным темам. Предыдущие разделы главы «Криптографически протоколы»: 1, 2, 3

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

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

Протокол Диффи—Хеллмана

Первый алгоритм с открытым ключом был предложен Диффи и Хеллманом в работе 1976 года «Новые направления в криптографии» (Bailey Whitfield Diffie, Martin Edward Hellman, «New directions in cryptography», [Diffie, Hellman 1976]). Данный протокол, который также можно назвать схемой Диффи—Хеллмана, стал первым, позволивший уменьшить требования к каналу связи для установления защищённого соединения без предварительного обмена ключами.

Протокол позволяет двум сторонам создать общий сеансовый ключ используя такой канал связи, который может прослушивать злоумышленник, но в предположении, что последний не может менять содержимое сообщений.

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

Протокол обмена состоит из следующих действий.

1. Алиса выбирает случайное
2. Боб выбирает случайное
   
   Боб вычисляет сессионный ключ
3. Алиса вычисляет

Таким способом создан общий секретный сессионный ключ . За счёт случайного выбора значений и в новом сеансе будет получен новый сессионный ключ.

Протокол обеспечивает только генерацию новых сессионных ключей (цель G10). В отсутствие третей доверенной стороны он не обеспечивает ни аутентификацию сторон (цель G1), из-за отсутствия проходов с подтверждением владения ключом отсутствует аутентификация ключа (цель G8). Зато, так как протокол не использует длительные «мастер»-ключи, можно говорить о том, что он обладает свойством совершенной прямой секретности (цель G9).

Протокол можно использовать только с такими каналами связи, в которые не может вмешаться активный криптоаналитик. В противном случае протокол становится уязвим к простой «атаке посередине».

1. Алиса выбирает случайное
2. Меллори выбирает случайное
   
   Меллори вычисляет сессионный ключ для канала с Алисой

3. Алиса вычисляет сессионный ключ для канала с Меллори (думая, что Меллори это Боб)

4. Боб выбирает случайное
   
   Боб вычисляет сессионный ключ для канала с Меллори (думая, что Меллори это Алиса)

5. Меллори вычисляет сессионный ключ для канала с Бобом

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

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

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

1. Стороны договорились о группе точек эллиптической кривой , её циклической подгруппе мощности и генераторе группы (или хотя бы достаточно большой подгруппы группы ).
2. Алиса выбирает случайное
3. Боб выбирает случайное
   
   Боб вычисляет точку
4. Алиса вычисляет точку

В качестве нового сессионного ключа стороны могут выбрать, например, первую координату найденной точки .

Протокол Эль-Гамаля

Протокол Эль-Гамаля ([ElGamal, 1984], [ElGamal, 1985]) за счёт предварительного распространения открытого ключа одной из сторон обеспечивает аутентификацию ключа для этой стороны. Можно гарантировать, что только владелец соответствующего закрытого ключа сможет вычислить сеансовый ключ. Однако подтверждение факта получение ключа (выполнение целей G1 и G8) не является частью протокола.

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

   
   Открытый ключ находится в общем открытом доступе для всех сторон. Криптоаналитик не может подменить его — подмена будет заметна.

2. Алиса выбирает секрет и вычисляет сеансовый ключ

3. Боб вычисляет сеансовый ключ

Протокол не обеспечивает гарантию выбора нового сессионного ключа в каждом сеансе протокола (G10), а использование «мастер»-ключа для передачи сеансового ключа позволяет злоумышленнику вычислить все сессионные ключи из прошлых сеансов при компрометации закрытого ключа (цель G9).

Протокол MTI/A(0)

В 1986 году Ц. Мацумото (Tsutomu Matsumoto), И. Такашима (Youichi Takashima) и Х. Имаи (Hideki Imai) предложили несколько алгоритмов, позже названных семейством протоколов MTI ([Matsumoto, Tsutomu, Imai 1986]). За счёт предварительного распространения открытых ключей обоих сторон они обеспечивали неявную аутентификацию ключа (цель G7). То есть сессионный ключ гарантированно мог получить только владельцы соответствующих открытых ключей. Мы рассмотрим одного из представителей данного семейства — протокол MTI/A(0).

Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .

Каждая из сторон (Алиса и Боб) сгенерировала пару из закрытого и открытого ключей:

1. Алиса сгенерировала случайное число
2. Боб сгенерировал случайное число
   
   Боб вычислил сеансовый ключ
3. Алиса вычислила сеансовый ключ

Если открытые ключи и соответствуют своим закрытым ключам и , то вычисленные участниками сессионные ключи совпадают:

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

Как и другие представители криптосистем-протоколов, MTI не разрабатывался с учётом возможности компрометации закрытых «мастер»-ключей и (цель G9).

Протокол Station-to-Station

Протокол STS (Station-to-Station, [Diffie, Oorschot, Wiener 1992]) предназначен для систем мобильной связи. Он использует идеи протокола Диффи—Хеллмана и криптосистемы RSA. Особенностью протокола является использование механизма электронной подписи для взаимной аутентификации сторон.

Предварительно стороны договорились об общих параметрах системы и , где — большое простое число, а — примитивный элемент поля .

Каждая из сторон и обладает долговременной парой ключей: закрытым ключом для расшифрования и создания электронной подписи и открытым ключом для шифрования и проверки подписи .

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

Протокол состоит из четырёх проходов, три из которых включают передачу сообщений ([Черёмушкин 2009]).

1. Алиса выбирает случайное число .
2. Боб выбирает случайное число .
   
   Боб вычисляет сессионный ключ .
3. Алиса вычисляет сессионный ключ .
   
   Алиса проверяет подпись в сообщении .
4. Боб проверяет подпись в сообщении .

Протокол обеспечивает арантию формирования новых ключей (G10), но не совершенную прямую секретность (G9).

Как показала атака Лоу 1996 года ([Lowe 1996]), протокол не может гарантировать аутентификацию субъектов (цель G1), ключей (G7) и подтверждение владения сессионным ключом (G8). Хотя злоумышленник не может получить доступ к новому сессионному ключу, если протокол использовать только для аутентификации субъектов, Алиса может принять злоумышленника за Боба.

1. Алиса выбирает случайное число .
3. Боб выбирает случайное число .
   
   Боб вычисляет сессионный ключ .

5. Алиса вычисляет сессионный ключ .
   
   Алиса проверяет подпись в сообщении .

После успешного завершения протокола Алиса уверена, что общается с Бобом.

Как и все остальные «криптосистемы-протоколы», протокол Station-to-Station основывается на некотором внешнем источнике информации об открытых ключах участников, не подвергая сомнению корректность и надёжность этого источника. Что, в общем случае, неверно. Если информация о ключах участников нужно получать извне при каждом сеансе протокола (например, если участников много, и запомнить ключи всех возможности нет), то канал получения открытых ключей будет основной целью активного криптоаналитика для рассмотренных протоколов. Как от этого защититься с использованием примитивов асимметричной криптографии — в следующем разделе.

Литература

• [Diffie, Hellman 1976] Diffie W., Hellman M. E. New directions in cryptography // Information Theory, IEEE Transactions on. — 1976. — нояб. — т. 22, № 6. — с. 644—654. — ISSN 0018-9448. — DOI: 10.1109/TIT.1976.1055638.
• [ElGamal, 1984] El Gamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // Proceedings of CRYPTO 84 on Advances in Cryptology. — Santa Barbara, California, USA: Springer-Verlag New York, Inc., 1985. — с. 10—18. — ISBN 0-387-15658-5. — URL: dl.acm.org/citation.cfm?id=19478.19480.
• [ElGamal, 1985] El Gamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Transactions on Information Theory. — 1985. — июль. — т. 31, № 4. — с. 469—472. — DOI: 10.1109/TIT.1985.1057074.
• [Matsumoto, Tsutomu, Imai 1986] Matsumoto T., Takashima Y., Imai H. On seeking smart publickey-distribution systems // Trans. Inst. Electron. Commun. Eng. Jpn. Sect. E. т. 69. вып. 2. — 02.1986. — с. 99—106.
• [Diffie, Oorschot, Wiener 1992] Diffie W., Van Oorschot P. C., Wiener M. J. Authentication
  
  and authenticated key exchanges // Designs, Codes and Cryptography. — 1992. — июнь. — т. 2, № 2. — с. 107—125. — ISSN 1573-7586. — DOI: 10.1007/BF00124891.
• [Lowe 1996] Lowe G. Some new attacks upon security protocols // CSFW ’96 Proceedings of the 9th IEEE workshop on Computer Security Foundations. —Washington, DC, USA: IEEE Computer Society, 1996. — с. 162.
• [Черёмушкин 2009] Черёмушкин А. В. Криптографические протоколы: основные свойства и уязвимости // Прикладная дискретная математика. — 2009. — нояб. — вып. 2. — с. 115—150. — URL: cyberleninka.ru/article/n/kriptograficheskieprotokoly-osnovnye-svoystva-i-uyazvimosti.pdf.

Послесловие

Автор будет благодарен за фактические и другие замечания к тексту.

прошлое и настоящее / Блог компании «Актив» / Хабр

Как известно, последняя революция в криптографии случилась в 1976 году из-за статьи “New Directions in Cryptography” американских ученых Уитфилда Диффи (Whitfield Diffie) и Мартина Хеллмана (Martin Hellman). Эта работа оказалась для последующего развития криптографии как «Большой Взрыв» — произошло рождение новой вселенной асимметричной криптографии. До этого момента (во всяком случае в открытой печати) существовала только симметричная криптография. Молодыми и никому тогда не известными учеными впервые была предложена схема, в которой для выработки общего секрета абонентам изначально не надо было обмениваться какими-либо секретными ключами. Помимо своей первозданности этот алгоритм интересен тем, что несмотря на то, что могут устаревать “сложные” задачи, лежащие в основе его безопасности, их можно успешно заменять новыми. Изначально это была задача дискретного логарифмирования в мультипликативной группе конечного поля (Discrete Logarithm Problem, сокр. — DLP), сейчас на практике широко используется задача дискретного логарифмирования в группе точек эллиптической кривой (Elliptic Curve DLP — ECDLP). В будущем (не таком уж далеком) предполагается использовать другие “сложные” задачи, которые будет иметь экспоненциальную сложность не только на классическом, но и на квантовом компьютере. Они называются постквантовыми. Одной из таких задач является задача нахождения изогении между эллиптическими кривыми, о которой я хочу рассказать в этой статье.

Поскольку цель статьи – максимально просто объяснить новый математический “движок” для протокола Диффи-Хеллмана (Diffie-Hellman или сокращенно — DH), то не рассматриваются некоторые атаки: мы предполагаем, что злоумышленник может только читать сообщения в канале, но не может вмешиваться в работу канала, чтобы перехватывать сообщения абонентов и отправлять свои (т.е. злоумышленник не “Человек посередине”). На практике (к примеру, в протоколе TLS) на открытые ключи DH может ставиться подпись и тут уже Человек Посередине подменить ключ DH не может: от сервера клиенту открытый ключ DH приходит как сертификат, от клиента к серверу – временный (ephemeral) ключ, подписанный на постоянном закрытом ключе ЭЦП клиента. В общем, в суровой реальности от подмены открытых ключей DH спасает технология PKI, основанная на доверии обеих сторон одному УЦ. Но, опять же, чтобы не отвлекать читателя от главного – математики, про PKI я ничего не пишу в этой статье. И еще раз: поскольку известны случаи, когда реализовывались и внедрялись системы, в которых стороны обменивались временными (ephemeral) открытыми ключами, которые стороны никак не проверяли (видимо те, кто их проектировал считали себя слишком занятыми людьми, чтобы изучить основы криптографии или хотя бы обратиться к специалистам), то прошу не забывать, что в реальной жизни это необходимо. Человек Посередине (он же Посредник, он же Man-in-the-middle) – это не Снежный Человек и он существует.

Прошлое: классический Диффи-Хеллман

Алиса и Боб изначально выбирают параметры (domain parameters): мультипликативную группу конечного поля и g — генератор ее подгруппы. Ничего страшного в слове генератор нет. Это всего лишь один из элементов группы со следующим свойством: если взять его степени от 1 до числа элементов группы, мы получим всю группу целиком. Подгруппа – это подмножество группы, которая сама по себе – тоже группа (при перемножении ее элементов в любых сочетаниях, мы получим только элементы этого самого подмножества).

Пример: – мультипликативная группа конечного поля.

Элементы группы:

числа от 1 до p — 1, где p – простое число.

Групповая операция a*b mod p: умножаем элементы группы a и b, затем a*b делим на p. Остаток от деления a*b на p и есть результат операции a*b mod p.

К примеру, пусть модуль p равен 11. Чаще всего обозначается как . Состоит из 11 – 1 = 10 элементов: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Число элементов в группе называется порядком группы (group order). Порядок равен 10.

А теперь немного поиграем с операциями:

5*6 mod 11 = 8,
1*10 mod 11 = 10.

1 для этой группы – это нейтральный элемент. Neutral — т.к. он “не взаимодействует” ни с какими другими элементами и результат операции с ним всегда равен второму элементу операции. В данном случае 1*10 mod 11 — это 10.

6*2 mod 11 = 1.

Для любого элемента любой группы существует обратный элемент, который “обращает” его в нейтральный. Для этой группы 6 и 2 – обратные друг для друга.

Когда групповая операция называется умножением (как в случае ), то используют такие обозначения для обратного к элемента: Т.е. * = 1 Что еще можно сказать про эту группу? Она коммутативна (или абелева):

mod p = mod p: от перестановки a и b результат не меняется.

Генераторы группы — это такие ее элементы, все степени которых являются всеми элементами группы. Группы, в которых есть хотя бы один такой элемент называют циклическими. Как понять, что x – генератор? Самый примитивный метод: построить таблицу степеней x:

Как насчет степеней 2?

2*2 mod 11 = 4
4*2 mod 11 = 8
8*2 mod 11 = 5
5*2 mod 11 = 10
10*2 mod 11 = 9
9*2 mod 11 = 7
7*2 mod 11 = 3
3*2 mod 11 = 6
6*2 mod 11 = 1 — мы видим, что цикл замкнулся. Степени 2 генерируют всю группу .

Итого: 2 — генератор .

Порядок элемента – минимальная степень, в которую его надо возвести, чтобы получить нейтральный. Порядок 2 в равен 10.

Теперь рассмотрим степени 3:

3*3 mod 11 = 9
9*3 mod 11 = 5
5*3 mod 11 = 4
4*3 mod 11 = 1

Порядок 3 равен 5. Он не “пробегает” все значения , т.к. мы видим, что на пятой степени происходит зацикливание: если продолжить умножение, то опять получим 3, 9, 5, 4, 1.

Что еще можно сказать про 3?

Это тоже генератор. Но не для , а для ее подгруппы, состоящей из пяти элементов {3, 9, 5, 4, 1}.

Легко видеть, что это подмножество -подгруппа: есть нейтральный элемент 1. Замкнутость: результат любых a*b mod p для этих чисел не выходит за пределы этого множества, ведь результат будет одним из множества {3, 9, 5, 4, 1}.

Каждый элемент имеет обратный: 3*4 mod 11 = 1, 9*5 mod 11 = 1, 1*1 mod 11 = 1. Какие еще подгруппы есть в ?

Еще есть группа порядка 2: {1, 10}

Ну и конечно же тривиальные подгруппы { 1 } и {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} (т.к. формально группа является подгруппой самой себя)

Как можно оптимизировать поиск генератора для ?

Тут необходимо использовать фундамент теории групп – теорему Лагранжа: “Порядок подгруппы делит порядок группы”.

Элемент x либо является генератором группы, либо является генератором одной из ее подгрупп. Следовательно, возведение x в степени порядков подгрупп и сравнение результата с 1 может это подтвердить или опровергнуть.

Вернемся к . Благодаря теореме Лагранжа мы совершенно уверенно можем сказать, что есть нетривиальные подгруппы только порядков 2 и 5, так как порядок равен 10.

Таким образом мы могли бы сократить вычисления для 2, возведя его только в степени 2 и 5!

mod 11 = 4 ≠1
mod 11 = ** mod 11 = mod 11 = 10 ≠1 Теперь этих вычислений достаточно, чтобы доказать, что 2 – генератор

Аналогично для 4:

4*4 mod 11 = 5 ≠1 ok, следующий шаг считаем пятую степень для 4:
mod 11 = ** 4 mod 11 = 5*5*4 mod 11 = 100 mod 11 = 1 -> 4 – это не генератор Как быть, если структура чуть сложнее? Рассмотрим :

Порядок 18 = 3*3*2. Делители 18: 2, 3, 6, 9 Выбираем случайный элемент, например 3:

Возводим 3 в степень r1 = 18/3 = 6:
mod 19 = 7 ≠1

Возводим 3 в степень r2 = 18/2 = 9:
mod 19 = 18 ≠1

Совершенно не обязательно возводить исследуемый элемент в степени всех подгрупп т.е. 2, 3, 6, 9, т.к. если элемент окажется генератором подгруппы подгруппы, то все равно возведение в степень порядка подгруппы даст 1.

К примеру, если бы мы выбрали не 3, а 11, то остановились бы на первом шаге:

mod 19 = 1.

т.к. 11 имеет порядок 3
mod 19 = mod 19 = mod 19

3 в генерирует подгруппу {1, 7, 11}

Нетривиальные подгруппы : {1, 18}, {1, 7, 11}, {1, 7, 8, 11, 12, 18}, {1, 4, 5, 6, 7, 9, 11, 16, 17}

Но вернемся к DH. На практике это выбор параметров для него – это выбор большого ( ~, т.е длины 3072 бит) простого числа p и генератора , порядок которого (т.е минимальная степень, которая дает в результате 1: mod p=1 ) – тоже большое простое число (~). Базовая операция которую выполняется в алгоритме – возведение в степень x по модулю: mod p.

Примечание: Алисе и Бобу необходимо проверять приходящие извне ключи на принадлежность их “рабочей” подгруппе большого простого порядка q:

Алиса проверяет mod p = 1? Если нет, то протокол прерывается.

Аналогично поступает Боб: он проверяет ключ, пришедший от Алисы: mod p = 1?

Мы сейчас не рассматриваем противника, который мог бы подменить по дороге открытые ключи, но тем не менее всегда надо помнить, что и в криптографии встречаются случаи из разряда “при таких друзьях нам и враги не нужны”: программа на устройствах Алисы или Боба может содержать различные ошибки (в реализации модульной арифметики, или просто может повредиться память).

Если проверки прошли нормально, то Алиса и Боб считают ключи для симметричных алгоритмов, чтобы уже с их помощью защищать канал передачи данных (например шифровать данные и считать MAC (Message Autentication Code) или просто считать MAC).

Обратная к mod p операция называется Discrete Logarithm (DL) или по нашему Дискретное Логарифмирование: пусть известны p, g и . Требуется найти степень x. Это как раз то, что очень интересно злоумышленнику.

Выбором группы занимаются конечно же не лично Алиса или Боб, а криптографы (хотя, некоторое подмножество всех Алис и Бобов принадлежит к их множеству, но мы не рассматриваем этот частный случай). Подмножество криптографов, которые глубоко разбираются в строении групп и знают, какие из них использовать безопасно иногда публикуют результаты своей работы в виде конкретных чисел p ,g и пошаговых описаний алгоритмов с тестовыми векторами. Их можно найти в виде стандартов NIST или RFC.

Вот пример небезопасных параметров для DH: группа “гладкого” порядка, т.е. у которой число элементов можно представить в виде произведения степеней небольших простых чисел, т.к. в ней можно легко вычислить дискретный логарифм с помощью метода Поллига-Хеллмана, который вычисляет дискретный логарифм в подгруппах группы, а потом с помощью китайской теоремы об остатках получает логарифм для самой группы. Поскольку вычисления по китайской теореме сами по себе достаточно просты, то сложность всего алгоритма Поллига-Хеллмана можно приблизительно оценить, как сложность вычисления DL в самой большой из подгрупп простого порядка.

Настоящее: эллиптический Диффи-Хеллман

В 1985 году Нил Коблиц (Neal I. Koblitz) и Виктор Миллер (Victor Saul Miller) независимо друг от друга изобрели, как можно использовать эллиптические кривые в криптографии. Их открытие помогло создать эллиптические варианты алгоритмов Диффи-Хеллмана, Эль-Гамаля, MQV, DSS, ГОСТ Р 34.10-94, которые изначально использовали мультипликативную группу конечного поля. В результате новые алгоритмы (за исключением ГОСТ) получили префикс EC: ECDH, EC ElGamal, ECMQV, ECDSS. А наш российский ГОСТ Р 34.10-94 трансформировался в ГОСТ Р 34.10-2001 (а потом в более надежный 34.10-2012). Зачем был нужен такой переход к эллиптическим кривым? Он позволил проводить более быстрые вычисления при том же уровне безопасности.

Алиса и Боб выбирают Доменные параметры (domain parameters) для эллиптических кривых.

Из чего состоят Доменные параметры для эллиптических кривых:

1. Поле Галуа GF(). Cостоит из элементов, где p —

характеристика поля (простое число)

(На практике чаще используют n = 1. Обозначается GF() и называется

простым полем (prime field). Его элементы — все числа от 0 до p-1)

2. Уравнение Вейерштрасса кривой над полем GF() (“Над полем” означает, что

все коэффициенты (в данном случае A и B) и решения (x и y) – элементы поля):

= +A+B (для p > 3)

где A и B такие, что 4+27 ≠ 0, x, y – афинные

координаты

3. Порядок группы точек (число всех ее элементов)

Обозначается как #E(GF( ))

Представляется как q*k, где q (большое простое число) – порядок подгруппы, а k – маленькое

число (не обязательно простое) называется cofactor (сомножитель)

4. Генератор подгруппы группы точек кривой (base point): точка Q, имеющая порядок q. (Алгоритм дискретного логарифмирования Поллига-Хеллмана применим также и к группе точек эллиптической кривой, как и к любой другой абелевой группе, поэтому группа точек должна иметь “негладкий” порядок. Т.е. равный произведению большого простого числа на маленькое число. В отличие от классического варианте, группа которого всегда содержит p-1 элемент, группа эллиптических кривых могут иметь и простой порядок)

Напомним самое основное:

Элементы группы — это точки кривой, т.е. пары (x, y) — решения уравнения Вейерштрасса. Групповая операция называется сложением точек:

(x1, y1) + (x2, y2) = (x3, y3)

Плюс еще есть так называемая Точка На Бесконечности (Point At Infinity) или нулевая точка (но точка на бесконечности – звучит красивее, согласитесь) Обозначим ее O. Это аналог единицы для мультипликативной группы конечного поля (из классического DH): 1*t mod p = t*1 mod p = t, для кривых: (x, y) + O= O + (x, y) = (x, y). Ее принципиальное отличие от сестры из мультипликативной группы заключается в том, что ее нельзя представить в виде каких-либо элементов поля, т.е. как обычную точку (x, y) так, чтобы можно было проводить с ней вычисления как с остальными точками по общей формуле.

В первой части статьи мы будем рассматривать только простое поле GF(p), поэтому все примеры и формулы используют суффикс mod p:

Формула сложения точек (X1, Y1) и (X2, Y2):

X3 = – X1- X2 mod p

Y3 = µ(X1 — X3) — Y1 mod p

где µ= (Y2-Y1)/(X2-X1) mod p, если X1 ≠ X2:

Если же X1 = X2 и Y1 = Y2 ≠ 0, то µ= (3+A)/2Y1 mod p

В случае, когда X1 = X2 и Y1 = — Y2 mod p, то формулы неприменимы и результат – точка на бесконечности.

Дроби помогают красивее выразить обратный элемент в мультипликативной группе: к примеру, mod p означает * mod p, где — обратное к значению

Обозначим скалярное произведение числа n на точку Q так: [n]*Q.

[n]*Q = Q + Q + … + Q + Q

n раз (это последовательная проделанная n раз операция сложения с помощью приведенных выше формул) Злоумышленник знает доменные параметры: кривую и точку Q (генератор подгруппы) а также результат умножения скаляра n на точку Q: [n]*Q. Что он хочет найти: число n (т.е решить задачу ECDLP). В каком случае это легко? Капитан Очевидность говорит, что если Q принадлежит подгруппе небольшого размера, то точка [n]*Q будет принадлежать той же самой подгруппе и злоумышленник будет перебирать все возможные скаляры и умножать их на Q, пока не получит известную ему точку [n]*Q. Поэтому Q должна принадлежать подгруппе большого простого порядка.

Итак, основная группа должна содержать подгруппу большого простого порядка (иными словами порядок всей группы должен быть НЕ гладким). Капитан Очевидность снова в деле и сообщает: чтобы группа могла содержать большую подгруппу, необходимо, чтобы сама группа была большой. Порядок группы точек кривой E над полем GF() обозначается как #E(GF()). Теорема Хассе дает весьма полезную оценку:

#E(GF()) = + 1 – t, где t – след Фробениуса, который по абсолютной величине t ≤ 2*. Т.е. порядок группы #E(GF()):
+ 1 – ≤ #E(GF()) ≤ + 1 +

Теперь мы знаем, как число элементов поля связано с числом точек: они практически не отличается по порядку. Можно ли утверждать, что для злоумышленнику необходимо порядка точек кривой вычислений для получения скаляра? Для “брутфорса” – да, но ведь есть более красивый метод, который требует гораздо меньше усилий. Метод Полларда, который также применим и для DLP (как и к любой другой коммутативной группе). Это вероятностный алгоритм. Число операций, которые он требует — около квадратного корня из числа элементов группы. Таким образом, если мы рассматриваем “боевые” криптографические кривые (c q*k, где q большое простое число, а k – маленькое число: на практике 1, 2 или 4 ) то их безопасность удобно оценивать как число операций, которое должен выполнить злоумышленник при помощи самого «продвинутого» метода для этих кривых – метода Полларда.

Пример:

Наиболее часто используемая в мире кривая NIST P-256 над простым полем.

Структура ее группы такая: порядок равен большому простому числу. Т.е порядок равен q*k, где q – простое, а cofactor k = 1. Ее безопасность можно оценить как , поскольку на сегодняшний день для NIST P-256 ничего лучше метода Полларда не придумано.

Помимо кривых с гладким порядком есть и другие, которые позволяют относительно легко решить ECDLP: суперсингулярные (со следом Фробениуса t таким, что: t mod p = 0) и аномальные ( t = 1 ). Предположим, что кривая Боба и Алиса не попадает ни в одну из этих плохих компаний и поэтому практически решить ECDLP для нее невозможно.

Примечание: как и в случае с классическим DH, хорошим тоном считается проверка всех (входящих и исходящих) точек на принадлежность к группе, но тут ситуация немножко сложнее. Сначала координаты подставляются в уравнение – это проверка на вхождение в группу. Потом для проверки на принадлежность большой подгруппе порядка q мы умножаем точку на q. Если в результате получаем точку на бесконечности, то все OK, а если нет — точка лежит в какой-то другой подгруппе и протокол должен быть прерван.

Итого:

Классический DH: в результате обмена ключами у Алисы и Боба появляется одинаковый элемент группы: ее генератор, умноженный на себя x*y раз: mod p

А теперь сopypaste:

Эллиптический DH: в результате обмена ключами у Алисы и Боба появляется одинаковый элемент группы: ее генератор — точка Q, сложенная с собой x*y раз: [x*y]*Q

Разница в названии операций для данных групп (сложение или умножение) не важна (ведь у группы только есть только одна операция). Так что теперь более попробуем более универсально:

в результате обмена ключами у Алисы и Боба появляется одинаковый элемент группы: ее генератор, над которым была проведена x*y раз групповая операция с ним же.

Квантовый кошмар и ненависть

Классический и эллиптический DH помимо математического изящества объединяет один неприятный факт: сложные (для обычных компьютеров) задачи ECDLP и DLP, лежащие в их основе могут быть легко решены, если будут созданы квантовые компьютеры, которые способны удержать в связанном состоянии достаточно большое число кубит (от нескольких сотен до нескольких тысяч). 
Кроме того, это означает конец для криптосистемы RSA: квантовый алгоритм Шора позволяет разлагать большие числа на простые множители за полиномиальное время. Поэтому именно для асимметричных алгоритмов постквантовая тема очень актуальна. Для симметричных шифров все пока не так ужасно – их будут атаковать квантовым алгоритмом Гровера, который имеет сложность квадратный корень из мощности множества ключа. К примеру, если вы использовали AES c длиной ключа 128 бит, то чтобы сохранить тот же уровень безопасности нужен тот же AES, но c 256 битным ключом (а AES-128 падает до 64 битного уровня, т.е. атакующему нужно будет выполнить операций на квантовом компьютере).

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

Литература:

Брюс Шнайер, Нильс Фергюссон “Практическая криптография”

Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone “Handbook of Applied Cryptography”

Lawrence C. Washington “Elliptic Curves: Number Theory and Cryptography, Second Edition”

Основы шифрования (часть 1) — Алгоритм Диффи-Хеллмана

Основы шифрования (часть 1) — Алгоритм Диффи-Хеллмана

Некоторое время назад я проводил исследование, чтобы лучше понять, как устроены криптографические алгоритмы. Сфера применения подобных алгоритмов весьма обширна. Мы защищаем информацию, хранящуюся на дисках или передаваемую через интернет. Мы проводим верификацию отсылаемых сообщений. В некоторых платежных системах шифрование является неотъемлемой частью.

Автор: Malarkey

Некоторое время назад я проводил исследование, чтобы лучше понять, как устроены криптографические алгоритмы. Сфера применения подобных алгоритмов весьма обширна. Мы защищаем информацию, хранящуюся на дисках или передаваемую через интернет. Мы проводим верификацию отсылаемых сообщений. В некоторых платежных системах шифрование является неотъемлемой частью. Тема криптографии настолько глубока и сложна, что неподготовленному человеку легко запутаться и наделать непоправимых ошибок, и поэтому весь приведенный ниже код не следует использовать в реальных задачах. Основная цель – ознакомиться с базовыми концепциями. Если вы хотите узнать историю вопроса, рекомендую почитать книгу The Code Book. Более детально различные аспекты криптографии описаны в книге Cryptography Engineering. Изучив вышеуказанную литературу, вы сможете лучше понимать, о чем я буду говорить в этой статье.

Суть проблемы

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

Алгоритм Диффи-Хеллмана

Рассмотрим схему обмена секретными ключами при помощи алгоритма Диффи-Хеллмана (Diffie-Hellman Key Exchange, DHKE). Более подробно с этой темой можно ознакомиться в русскоязычной и англоязычной Википедии. Ниже показана наглядная схема обмена между двумя пользователями. Алиса и Боб хотят использовать общий ключ для шифрования переписки. Рассмотрим детально этот процесс, используя краски вместо чисел:

1. Алиса и Боб выбрали общую краску.




2. Алиса и Боб выбрали по одной секретной краске.




3. Алиса и Боб смешали общую и секретную краску.




4. Алиса и Боб обменялись получившимися смешанными красками.




5. Алиса смешала полученную смешанную краску от Боба со своей секретной краской.




6. Боб смешал полученную смешанную краску от Алисы со своей секретной краской.




7. Теперь у Алисы и Боба есть общая секретная краска.

(Алиса и Боб будут периодически встречаться в наших рассуждениях, так что привыкайте).

Рисунок 1: Наглядная схема получения общего секретного ключа (из Википедии)

Рабочий пример

Схема обмена секретным ключом реализована мной в коде. Ниже показан результат работы утилиты (для большей наглядности используются дополнительные флаги).

Рисунок 2: Результаты работы скрипта, реализующего алгоритм Диффи-Хеллмана

Небольшие пояснения к Рисунку 2:

• «x -> y» означает, что «x» отсылает сообщение «y»




• «Internal» означает, что действие происходит локально на машине одного из оппонентов

Вначале Алиса выбирает простое базовое число (5) и передает через Еву информацию Бобу. Затем Алиса выбирает еще одно простое число (23), которое будет использоваться при вычислениях, и опять передает через Еву информацию Бобу. Далее Алиса и Боб выбирают секретные числа и производят математические вычисления с использованием чисел 5 и 23. Затем Алиса и Боб через Еву обмениваются полученными сведениями. Далее каждый из оппонентов вычисляет секретный ключ.

Математическая сторона вопроса

«Как же работает этот алгоритм?», — спросите вы. Здесь нам на помощь приходит модулярная арифметика. Рассмотрим выражение g^x mod p. Числа g и p являются эквивалентом общей краски (см. схему выше). Существуют некоторые ограничения относительного того, какие числа можно использовать в качестве g и x (рассмотрим ниже). Число p – простое. Алиса и Боб будут выбирать секретные числа или секретные краски (a и b соответственно). Эти числа могут быть любыми. Затем каждый вычисляет выражение g^x mod p и рассказывает своему оппоненту конечный результат (смешанная краска). Теперь у Алисы есть значение B = g^b mod p, полученное от Боба, а у Боба есть значение A = g^a mod p, полученное от Алисы. Затем оппоненты вычисляют секретный ключ. Алиса вычисляет выражение B^a mod p, а Боб — A^b mod p.

Подождите, B^a mod p и A^b mod p – это и есть секретные ключи? Тогда мы должны быть уверены, что оба выражения дают одинаковый результат. Рассмотрим еще раз весь алгоритм по шагам.

1. Алиса и Боб выбирают два числа g и p.




2. Алиса и Боб выбирают секретные числа (a и b соответственно)




3. Алиса и Боб вычисляют g ^ x mod p, где x – секретное число.




4. Алиса и Боб обмениваются полученными данными (числа A и B соответственно).




5. Алиса и Боб используют полученное число и секретное число для вычисления общего ключа.

В шаге 5 имеем следующее:

У Алисы: B^a mod p = (g^b mod p) ^ a mod p = g^ab mod p.

У Боба: A^b mod p = (g^a mod p) ^ b mod p = g^ab mod p.

Чтобы лучше понять, как работает этот алгоритм, нам придется глубже погрузиться в модулярную арифметику.

Когда вы вычисляете выражение y mod z, на самом деле вычисляется остаток от деления y / z (или y % z, как принято в большинстве языков программирования). Если y < z, тогда y % z = y. Когда y > z выражение работает наподобие часов. По мере увеличения числа y выражение y % z будет равняться значениям в диапазоне от 0 до z – 1. Как только y станет кратно z, отсчет начинается сначала. Выясняется, что операция возведения в степень в модулярной арифметике имеет свойство транзитивности. То есть (a ^ b) ^ c mod d = (a ^ c) ^ b mod d = a^ (b ^ c) mod d. Алиса вычисляет выражение (g^b mod p) ^ a mod p, которое эквивалентно (g^b)^a mod p. В конечном счете, мы получаем выражение g^ab mod p.

Как было сказано ранее, на числа g и p накладываются определенные ограничения. Для выражения a ^ b mod c итоговый результат зависит от выбранных чисел. Рассмотрим выражение: a ^ b mod 7.

2 ^ 1 mod 7 = 2 mod 7 = 2

2 ^ 2 mod 7 = 4 mod 7 = 4

2 ^ 3 mod 7 = 8 mod 7 = 1

2 ^ 4 mod 7 = 16 mod 7 = 2

2 ^ 5 mod 7 = 32 mod 7 = 4

2^ 6 mod 7 = 64 mod 7 = 1

…

Понимаете, в чем дело? В результате мы имеет только 3 различных числа, и количество секретных ключей лишь половина всех чисел, которые меньше 7 (а ограниченное количество ключей напрямую влияет на уровень безопасности).

Вместо 2 возьмем 3:

3 ^ 1 mod 7 = 3 mod 7 = 3

3 ^ 2 mod 7 = 9 mod 7 = 2

3 ^ 3 mod 7 = 27 mod 7 = 6

3 ^ 4 mod 7 = 81 mod 7 = 4

3 ^ 5 mod 7 = 243 mod 7 = 5

3^ 6 mod 7 = 729 mod 7 = 1

….

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

Преимущества алгоритма

Алисе и Бобу удалось сгенерировать одинаковый ключ, но насколько решена наша проблема? Рассмотрим ситуацию с позиции Евы (курьера, который передает информацию).

Рисунок 3: Информация, которую видит курьер

Если скрипт запущен без флагов, на выходе показывается информацию, которую видит Ева. В примере выше Ева видит числа g и p, а также A и B. Чтобы вычислить секретный ключ, Еве нужно определить значения числа a (или b), используя выражение A = g^a mod p. Найти решение этого уравнения, которое часто называют секретно вычисляемой функцией (trap door function), довольно сложно. Подобные выражения легко вычисляются в одну сторону, но тяжело в другую (через некоторые двери вы не можете вернуться обратно). Если хотите копнуть глубже, ознакомьтесь со статьей, где описана проблема дискретного логарифмирования.

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

Во второй части мы рассмотрим алгоритм RSA.

Ссылки

https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

https://en.wikipedia.org/wiki/Discrete_logarithm_problem

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

Протокол Диффи — Хеллмана — Национальная библиотека им. Н. Э. Баумана

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:44, 1 февраля 2016.

Протокол Ди́ффи-Хе́ллмана^[1] (DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричное шифрование|симметричного шифрования.

Описание алгоритма

Самый распространенный пример во всех учебных пособиях:
Предположим, существует два абонента: Алиса и Боб. Обоим абонентам известны два числа g и p, желательно простых, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a, Боб — число b. Затем Алиса вычисляет значение (1):

A=gamodp{\displaystyle A=g^{a}{\bmod {p}}}
(1)

и пересылает его Бобу, а Боб вычисляет (2):

B=gbmodp{\displaystyle B=g^{b}{\bmod {p}}}
(2)

и передаёт Алисе. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть, у него нет возможности вмешаться в процесс передачи).

На втором этапе Алиса на основе имеющегося у неё a и полученного по сети B вычисляет значение (3):

Bamodp=gabmodp{\displaystyle B^{a}{\bmod {p}}=g^{ab}{\bmod {p}}} (3)

Боб на основе имеющегося у него b и полученного по сети A вычисляет значение (4):

Abmodp=gabmodp{\displaystyle A^{b}{\bmod {p}}=g^{ab}{\bmod {p}}} (4)

Как нетрудно видеть, у Алисы и Боба получилось одно и то же число (5):

K=gabmodp{\displaystyle K=g^{ab}{\bmod {p}}}
(5)

Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления (3) или (4) по перехваченным gamodp{\displaystyle g^{a}{\bmod {p}}} и gbmodp{\displaystyle g^{b}{\bmod {p}}}, если числа p, a, b выбраны достаточно большими.

При работе алгоритма каждая сторона:

1. Генерирует случайное натуральное число a — закрытый ключ
2. Совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

   p является случайным простым числом

   (p-1)/2 также должно быть случайным простым числом (для повышения безопасности)

   g является первообразным корнем по модулю p (также является простым числом)

3. Вычисляет открытый ключ A, используя преобразование над закрытым ключом

   A = g^amod p

4. Обменивается открытыми ключами с удалённой стороной
5. Вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a

   K = B^amod p

   К получается равным с обеих сторон, потому что:

   B^amod p = (g^bmod p)^amod p = g^abmod p = (g^amod p)^bmod p = A^bmod p

В практических реализациях для a и b используются числа порядка 10¹⁰⁰ и p порядка 10³⁰⁰. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

Пример

Ева — криптоаналитик. Она читает пересылку Боба и Алисы, но не изменяет содержимого их сообщений^[2].

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

Протокол Диффи — Хеллмана для конференц-связи

Разновидность протокола используемого при общении трех и более участников.
Участники:
 A,B,C{\displaystyle ~A,B,C}

1.  A:gx(modp)→B{\displaystyle ~A:g^{x}{\pmod {p}}\rightarrow B},где  p{\displaystyle ~p} — простое,  g{\displaystyle ~g} — первообразный корень.
2.  B:y=gy(p)→C{\displaystyle ~B:y=g^{y}(p)\rightarrow C}
3.  C:z=gz(p)→A{\displaystyle ~C:z=g^{z}(p)\rightarrow A}
4.  A:z′=zx(p)→B{\displaystyle ~A:z’=z^{x}(p)\rightarrow B}
5.  B:x′=xy(p)→C{\displaystyle ~B:x’=x^{y}(p)\rightarrow C}
6.  C:y′=yz(p)→A{\displaystyle ~C:y’=y^{z}(p)\rightarrow A}

 {k=y′x(p)k=z′y(p)k=y′z(p) ⇒ k=gxyz(modp){\displaystyle ~{\begin{cases}k=y’^{x}(p)\\k=z’^{y}(p)\\k=y’^{z}(p)\end{cases}}\ \Rightarrow \ k=g^{xyz}{\pmod {p}}}

Ссылки

Протокол MQV — старый добрый Диффи-Хеллман, но не совсем / Хабр

Вот уже более 30 лет протокол распределения ключей Диффи-Хеллмана радует глаз простого криптомана своей простотой и надежностью. Для тех, кто эти последние 30 лет провел за занятиями более веселыми, нежели изучение криптографических протоколов, поясняю.
Протокол Диффи-Хеллмана был опубликован в 1976 году и послужил началом эры асимметричной криптографии. Суть его до гениального проста: Алиса и Боб хотят получить общий ключ для симметричной криптосистемы. Для этого они, договорившись, выбирают два больших числа g и p. Эти числа известны им обоим и держать их в секрете не имеет никакого смысла. Затем Алиса в тайне генерирует большое секретное число a, а Боб — большое число b. А далее за дело берется простая арифметика. Алиса посылает Бобу число
.
Боб в свою очередь высылает Алисе
.

Теперь, чтобы получить общий ключ Алиса вычисляет , а Боб находит .
Нетрудно проверить, что , т.к.
.
Гениальность идеи заключается в том, что для получения ключа K Алисе и Бобу не понадобится много времени, в то время, как злоумышленнику, чтобы найти K нужно уметь решать задачу дискретного логарифмирования.
Боясь утомить читателя общеизвестными фактами, перехожу сразу к сути дела. А что если абстрагироваться от теории и перейти к практике? То получим следующее.

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

То есть, Меллори получает один ключ общий с Алисой(которая считает, что это Боб), и один ключ общий с Бобом(который считает, что это Алиса). А, следовательно, он может получать от Алисы любое сообщение для Боба расшифровать его ключом , прочитать, зашифровать ключом и передать Бобу. Таким образом, подлог может оставаться незамеченным очень долгое время.

ЭЦП в качестве защиты

Как бороться с такой уязвимостью? Самый логичный и простой ответ: нужна взаимная аутентификация. И тут на помощь приходит ЭЦП.
Если у Боба имеется открытый ключ Алисы, и он уверен на сто процентов, что это действительно ключ Алисы, то тогда для защиты от атаки «человек посередине» Алисе достаточно подписать своим закрытым ключом число на шаге 1. Теперь Меллори может сколько угодно пытаться выдать себя за Алису, но подделать ее подпись он не сможет, а Боба сразу начнут терзать «смутные сомненья».
Казалось бы решение найдено, протокол доработан, уязвимость устранена. Но… Как всегда есть одно но. И в данном случае в роли такового выступает чрезмерное увеличение размера сообщений за счет добавления подписи. Наглядно этот эффект демонстрирует следующая таблица:

Как видно из этой таблицы размер сообщений увеличивается в разы. Казалось бы, да и бог же с ними с этими лишними 320 битами, кому от них вред то будет? Но в криптографии не терпят полумер. Вот потому и был придуман протокол MQV, избавляющий Диффи-Хеллман от уязвимости и при этом не использующий ЭЦП.

Протокол MQV

Итак, протокол MQV – протокол распределения ключей, поддерживающий взаимную аутентификацию сторон и тем самым устраняющий уязвимость к атаке «человек посередине», присущей классическому Диффи-Хеллману. Помимо прочего, для аутентификации пользователей не используется никакая вспомогательная информация, наподобие ЭЦП, что позволяет существенно сократить размер передаваемых сообщений.

Теперь о самом протоколе.
Алиса и Боб имеют каждый свою ключевую пару, состоящие из открытых и закрытых ключей: и . Разумеется, Бобу известен открытый ключ Алисы, а той в свою очередь известен открытый ключ Боба.
Далее, Алиса и Боб генерируют сеансовую пару ключей: и .
Затем происходит обмен как в классическом протоколе Диффи-Хеллмана:
Алиса к Бобу:
Боб к Алисе:
Теперь Алиса знает: A, B, C, D, a, .
А Бобу известны: A, B, C, D, b, .
Чтобы получить общий ключ K они должны проделать следующие операции.

Алиса:

Выбирает число l, равное размеру сообщения в битах деленному на 2. Так если используется EC-MQV и длина сообщения равна 160 бит, то l=80.

1. Задает

2. Находит

3. Задает

4. Вычисляет

5. Находит

6. Вычисляет

Боб проделывает те же действия, но со своими закрытыми ключами:

1. Задает

2. Находит

3. Задает

4. Вычисляет

5. Находит

6. Вычисляет

Получившиеся в результате вычислений числа и есть общий секретный ключ. Убедимся в этом:
, т.к. и ;
, т.к. ;
, т.к. и ;
, т.к. ;
.

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

Несмотря на кажущуюся сложность, в скорости протокол MQV ничего не теряет по сравнению со схемой использующей ЭЦП, ведь и там и там используется одна и та же операция возведения в степень по модулю простого числа. Выгода же от использования протокола заключается в следующем. Это, во-первых, устойчивость к атаке «человек посередине», во-вторых, небольшой размер сообщений, а, в-третьих, удобная реализация протокола, избавляющая пользователя от необходимости подписывать каждое отправляемое сообщение.

upd:

Литература

1. Н. Смарт «криптография»(наиболее полное описание протокола MQV на русском из всех мною встреченных).

2. Болотов А. и др. «Элементарное введение в эллиптическую криптографию»(описание протокола на эллиптических кривых).

3. Ну и ссылка на википедию.

АНБ скомпрометировало протокол Диффи-Хеллмана? / Хабр

Уже давно ходят слухи, что АНБ способно дешифровать значительную часть зашифрованного интернет-трафика. Этому есть косвенные свидетельства. В 2012 году некий сотрудник АНБ на условиях анонимности утверждал, что агентство добилось «прорыва в вычислениях», которые дают им «возможность взломать нынешнюю публичную криптографию». Документы Сноудена тоже указывают на некоторые исключительные возможности АНБ: из них следует, что агентство построило широкую инфраструктуру для перехвата и расшифровки VPN-трафика, и что оно вероятно обладает возможностью расшифровать по крайней мере часть HTTPS и SSH соединений по запросу.

Документы не дают понять, как такое возможно. 13 октября на конференции ACM CCS выступили известные криптографы Алекс Халдерман (Alex Halderman) и Надя Хенингер (Nadia Heninger) с докладом, в котором они предполагают, что решили эту таинственную загадку. Кстати, их работа признана лучшим докладом конференции.

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

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

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

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

Есть ли смысл разведывательному агентству инвестировать такие деньги, чтобы обрабатывать по одному числу за год? Халдерман и Хенингер считают, что есть. Дело в том, что если взломать самое распространённое в реальных приложениях простое число, то вы сможете дешифровать две трети мирового VPN-трафика и получите доступ к четверти SSH-серверов!

Взлом второго по популярности числа даёт вам доступ к пассивной прослушке примерно 20% HTTPS-серверов из списка миллиона самых популярных сайтов.

Другими словами, однократные инвестиции в оборудование позволят расшифровать триллионы зашифрованных соединений.

Бюджет АНБ, несомненно, достаточен для этого.

Подробнее см. работу Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice.

Алгоритм Диффи — это… Что такое Алгоритм Диффи?

Алгори́тм Ди́ффи — Хе́ллмана (англ. Diffie-Hellman, DH) — алгоритм, позволяющий двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Этот ключ может быть использован для шифрования дальнейшего обмена с помощью алгоритма симметричного шифрования.

Алгоритм был впервые опубликован Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом в 1976 году.

В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркля», признавая вклад Меркля в изобретение криптографии с открытым ключом.

Предисловие

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

История

Схема обмена ключами Диффи — Хеллмана, изобретённая в 1976 году при сотрудничестве Уитфилда Диффи и Мартина Хеллмана, под сильным влиянием работы Ральфа Меркля (Ralph Merkle) о системе распространения публичных ключей, стала первым практическим методом для получения общего секретного ключа при общении через незащищенный канал связи. Для обеспечения устойчивости, по совету Джона Гилла (John Gill), была использована проблема дискретного логарифмирования.

Годом позже был изобретен первый алгоритм асимметричного шифрования RSA, который решил проблему общения через незащищённый канал кардинально.

В 2002 году Мартин Хеллман писал:

«Эта система … с тех пор известна под названием алгоритма Диффи — Хеллмана. Однако, когда система была впервые описана на бумаге Диффи и мной, это была система распространения публичных ключей, концепция которой была выработана Мерклем, и поэтому она должна называться „алгоритмом Диффи — Хеллмана — Меркля“, если её связывают с именами. Я надеюсь что это небольшое изменение поможет признанию равного вклада Меркля в изобретение криптографии с открытыми ключами.»^[1]

Патенты зарегистрированны в Соединенных штатах(истек 29 Апреля 1997) и Канаде. Группа Public Key Partners(PKPб Парнеры по открытым ключам), получила вместе с другими патентами в области криптографии с открытыми ключами получила лицензию на этот патент. В патенте U.S. Patent 4 200 770 (в настоящее время истекшем), описывающем данный алгоритм, изобретателями значатся Хеллман, Диффи и Меркль.

В декабре 1997 года была обнародована информация, что в 1974 году Малькольм Вильямсон изобрел математический алгоритм, основанный на коммутативности показателей при последовательном возведении в степень (то есть, ), аналогичный алгоритму Диффи-Хеллмана.^[2]

Описание алгоритма

Предположим, что обоим абонентам известны некоторые два числа g и p (например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение и пересылает его второму, а второй вычисляет и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи).

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

Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ

При работе алгоритма, каждая сторона:

1. генерирует случайное натуральное число a — закрытый ключ
2. совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

   p является случайным простым числом

   g является первообразным корнем по модулю p

3. вычисляет открытый ключ A, используя преобразование над закрытым ключом

   A = g^a mod p

4. обменивается открытыми ключами с удалённой стороной
5. вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a

   K = B^a mod p

   К получается равным с обеих сторон, потому что:

   B^a mod p = (g^b mod p)^a mod p = g^ab mod p = (g^a mod p)^b mod p = A^b mod p

В практических реализациях, для a и b используются числа порядка 10¹⁰⁰ и p порядка 10³⁰⁰. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

Пример

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

• s = секретный ключ. s = 2
• g = открытое простое число. g = 5
• p = открытое простое число. p = 23
• a = секретный ключ Алисы. a = 6
• A = открытый ключ Алисы. A = g^a mod p = 8
• b = секретный ключ Боба. b = 15
• B = открытый ключ Боба. B = g^b mod p = 19

Алиса знает

p = 23

g = 5

a = 6

A = 56 mod 23 = 8

B = 5b mod 23 = 19

s = 196 mod 23 = 2

s = 8b mod 23 = 2

s = 196 mod 23 = 8b mod 23

s = 2

Алиса не знает

b=?

Боб знает

p = 23

g = 5

b = 15

B = 515 mod 23 = 19

A = 5a mod 23 = 8

s = 815 mod 23 = 2

s = 19a mod 23 = 2

s = 815 mod 23 = 19a mod 23

s = 2

Боб не знает

а=?

Ева знает

p = 23

g = 5

A = 5a mod 23 = 8

B = 5b mod 23 = 19

s = 19a mod 23

s = 8b mod 23

s = 19a mod 23 = 8b mod 23

Ева не знает

а=?

b=?

s=?

Diffie-Hellman с тремя и более участниками

Протокол обмена ключами можно расширить на случай с тремя и более участниками. В следующем примере Алиса, Боб и Кэрол вместе генерируют секретный ключ.

x = секретный ключ Алисы.

X = открытый ключ Алисы.

y = секретный ключ Боба.

Y = открытый ключ Боба.

z = секретный ключ Кэрол.

Z = открытый ключ Кэрол.

(1) Алиса выбирает случайное целое число x и вычисляет

X=mod n

(2) Боб выбирает случайное целое число y и вычисляет

Y=mod n

(3) Кэрол выбирает случайное целое число y и вычисляет

Z=mod n

(4) Алиса посылает Бобу

=mod n

(5)Боб посылает Кэрол

=mod n

(6) Кэрол посылает Алисе

=mod n

(7) Алиса вычисляет

k=mod n

(8) Боб вычисляет

k=mod n

(9) Кэрол вычисляет

k=mod n

Секретный ключ к=mod n, никто из прослушивающих канал не могут узнать этот ключ. Протокол можно расширить на четырёх и более участником, просто добаляются новые участники и этапы вычисления.

Шифрование с открытым ключом

Данный алгоритм может также использоваться в качестве алгоритма шифрования с открытым ключом. В этом случае общая схема остаётся аналогичной приведённой выше, но с небольшими отличиями. Алиса не передаёт значения p, g и A Бобу напрямую, а публикует их заранее в качестве своего открытого ключа. Боб выполняет свою часть вычислений, после чего шифрует сообщение симметричным алгоритмом, используя K в качестве ключа, и передаёт шифротекст Алисе вместе со значением B. Однако такой подход не получил распространения, в этой области доминирует алгоритм RSA.

Обмен ключом без обмена ключем

Если имеется сообщество пользователей, каждый из пользователей может опубливать открытый ключ X=mod n, в общей базе данных. Если Алиса хочет установить связь с Бобом, ей надо получить открытый ключ Боба и сгенерировать их общий секретный ключ. Алиса может зашифровать сообщение открытым ключом и послать его Бобу. Боб извлечет открытый ключ Алисы и найдет общий секретный ключ. Каждая пара пользователей может использовать свой уникальный секретный ключ, не требуя обмена данными между пользователями.Открытые ключи должны пройти сертификацию для защиты от нессанкционированного доступа, и эти ключи должны постоянно меняться.

Криптографическая стойкость

Криптографическая стойкость алгоритма Диффи — Хеллмана (то есть сложность вычисления K=g^ab mod p по известным p, g, A=g^a mod p и B=g^b mod p), основана на предполагаемой сложности проблемы дискретного логарифмирования. Однако хотя умение решать проблему дискретного логарифмирования позволит взломать алгоритм Диффи — Хеллмана, обратное утверждение до сих пор является открытым вопросом (другими словами, эквивалентность этих проблем не доказана).

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

Задача Диффи-Хеллмана и задача дискретного логарифмирования

Стойкость разделенного ключа в протоколе Диффи-Хеллмана обеспечивается вычислением значенияе по заданным числам и . Эта задача называется вычислительной проблемой Диффи-Хеллмана (CDH problem —Diffie-Hellman problem)

Вычислительная проблема Диффи-Хеллмана(в конечном поле)

ИСХОДНЫЕ ДАННЫЕ:
desq : описание конечного поля  ;
g∈ — порождающий элемент группы  ;
,∈, где 0 < a, b < q.
РЕЗУЛЬТАТ:

Такая формулировка представляет собой общую постановку задачи в конечном поле представляет общий случай, для Диффи-Хеллмана используется специальный случай. Если бы проблему Диффи-Хеллмана было легко решить, то значение mod p можно было бы найти, зная числа p, g, и , которые являются частью протокола. Предполагая, что противник обладает возможностями перехвата информации, следует предположить, что эти числа не являются для него секретом. Проблема Диффи-Хеллмана опирается на сложность вычисления дискретного логарифма (discrete logarithm problem)

Задача дискретного логарифмирования (в конечном поле)

ИСХОДНЫЕ ДАННЫЕ:
desq : описание конечного поля  ;
g∈ — порождающий элемент группы  ;
h ∈
РЕЗУЛЬТАТ:
Уникальное число a < q, удовлетворяющее условию h = .
Целое число a обозначается как h.

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

Сформулируем точные предположения о неразрешимости проблемы Диффи-Хеллмана

Предположение. (Условия неразрешимости проблемы Диффи-Хеллмана) Алгоритмом решения проблемы Диффи-Хеллмана называется вероятностный полиномиальный алгоритм A с преимуществом ε > 0: ε = Prob[A(desc(), g,,)]. Входные данные А указанны в определение (Вычислительная проблема Диффи-Хеллмана) (в конечном поле). Пусть IG — генератор вариантов, получающий на вход число время работы которого является полиномом от параметра k, а результатом — 1) desq(), где |q| = k, и 2) порождающий элемент g ∈. Будем говорить, что генератор IG удовлетворяет условиям неразрешимости проблемы Диффи-Хеллмана, если для вариантов IG() не существует алгоритма решения с преимуществом ε> 0, которое не является пренебрежимо малым по сравнению со всеми достаточно большими числами k.

См. также

Примечания

Калькулятор обмена ключей Диффи-Хеллмана

Калькулятор обмена ключами Диффи-Хеллмана

Dirty Diffie-Hellman
(Как грязный Санта, но более интересный)

Дрянной PHP-скрипт для простого калькулятора обмена ключами Диффи-Хеллмана. Думаю, я мог бы использовать Javascript вместо PHP, но у меня были ошибки округления.

 а = 5
A = g  a  mod p = 10  5  mod 541 = 456
б = 7
B = g  b  mod p = 10  7  mod 541 = 156
Алиса и Боб меняют местами A и B ввиду Карла
ключ  a  = B  a  мод p = 156  5  мод 541 = 193
ключ  b  = A  B  мод p = 456  7  мод 541 = 193
 

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

Фиксированные числа: g = 10, p = 541

Шаги участников:

1. Найдите кого-то, кого вы не знаете, и представьтесь.

2. Один из вас — Алиса (a), а другой — Боб (b). Если пол не совпадает, это
хорошо, один из вас может быть Аланом, а другой Барб, мне все равно.

3. Вы оба выбираете число от 1 до 100, но не говорите другому
человек этот номер.

4. Алиса, вычислите A = g ^a mod p = 10 ^a mod 541.
Боб, вычислим B = g ^b mod p = 10 ^b mod 541.
Не стесняйтесь вырвать свой калькулятор или смартфон или просто использовать это
калькулятор:
http: // www.irongeek.com/diffie-hellman.php

5. Алиса и Боб, устно обменяйтесь А и Б в присутствии Карла (Или, как указывает Chux0r, возможно, «Сочельник»).

6. Алиса, вычислите SecretKeyA = B ^a mod p = B ^a mod 541. Обратите внимание на верхний индекс.
выбранная вами строчная переменная.
Боб, вычислите SecretKeyB = A ^b mod p = A ^b mod 541. Обратите внимание, что верхний индекс — это
выбранная вами строчная переменная.

7. Если вы все сделали правильно, SecretKeyA должен быть таким же, как SecretKeyB.Пиши свой
имена, значения A и B и общий результат SecretKey на листе бумаги
и сдадим на рисунок.

Чертеж:

Офицер рисует лист бумаги и объявляет двух человек,
значения их A и B, а затем подождите 20 сек. Если кто-то еще может объявить
Общий секретный ключ Алисы и Боба через 20 секунд, вместо этого они побеждают.

.Шифрование с открытым ключом

— как работает атака «человек в середине» в Диффи-Хеллмане?

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

Загрузка…

2. Авторизоваться
   зарегистрироваться

3. текущий

.

новейших вопросов ‘diffie-hellman’ — qaru

Переполнение стека

1. Около

2. Продукты

3. Для команд

1. Переполнение стека
   Общественные вопросы и ответы

2. Переполнение стека для команд
   Где разработчики и технологи делятся частными знаниями с коллегами

3. Вакансии
   Программирование и связанные с ним технические возможности карьерного роста

4. Талант
   Нанимайте технических специалистов и создавайте свой бренд работодателя

5. Реклама
   Обратитесь к разработчикам и технологам со всего мира

6. О компании

.

No related posts.