Эллиптическая кривая Диффи – Хеллмана

Протокол ключевого соглашения

Эллиптическая кривая Диффи-Хеллмана ( ECDH ) — это протокол соглашения о ключах , который позволяет двум сторонам, каждая из которых имеет пару открытого и закрытого ключей с эллиптической кривой , установить общий секрет по незащищенному каналу . ^{[1] [2] [3]} Этот общий секрет можно использовать непосредственно в качестве ключа или для получения другого ключа . Ключ или производный ключ затем можно использовать для шифрования последующих сообщений с использованием шифра с симметричным ключом . Это вариант протокола Диффи-Хеллмана, использующий криптографию на основе эллиптических кривых .

Протокол установления ключа

В следующем примере показано, как устанавливается общий ключ. Предположим, Алиса хочет установить общий ключ с Бобом , но единственный доступный им канал может быть подслушан третьей стороной. Первоначально необходимо согласовать параметры домена (то есть в простом или двоичном случае). Также каждая сторона должна иметь пару ключей, подходящую для криптографии на эллиптических кривых, состоящую из закрытого ключа (случайно выбранного целого числа в интервале ) и открытого ключа, представленного точкой (где , то есть результат сложения с самим собой раз ). Пусть пара ключей Алисы будет , а пара ключей Боба — . Каждая сторона должна знать открытый ключ другой стороны до выполнения протокола. ${\displaystyle (p,a,b,G,n,h)}$ ${\displaystyle (m,f(x),a,b,G,n,h)}$ ${\displaystyle d}$ ${\displaystyle [1,n-1]}$ ${\displaystyle Q}$ ${\displaystyle Q=d\cdot G}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle (d_{\text{A}},Q_{\text{A}})}$ ${\displaystyle (d_{\text{B}},Q_{\text{B}})}$

Алиса вычисляет точку . Боб вычисляет точку . Общий секрет — ( координата x точки). Большинство стандартизированных протоколов, основанных на ECDH, получают симметричный ключ с помощью некоторой функции получения ключа на основе хэша. ${\displaystyle (x_{k},y_{k})=d_{\text{A}}\cdot Q_{\text{B}}}$ ${\displaystyle (x_{k},y_{k})=d_{\text{B}}\cdot Q_{\text{A}}}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{k}}$

Общий секрет, рассчитанный обеими сторонами, одинаков, поскольку . ${\displaystyle d_{\text{A}}\cdot Q_{\text{B}}=d_{\text{A}}\cdot d_{\text{B}}\cdot G=d_{\text{B}}\cdot d_{\text{A}}\cdot G=d_{\text{B}}\cdot Q_{\text{A}}}$

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

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

Если Алиса злонамеренно выбирает недопустимые точки кривой для своего ключа, а Боб не подтверждает, что точки Алисы являются частью выбранной группы, она может собрать достаточно остатков ключа Боба, чтобы получить его закрытый ключ. Было обнаружено, что несколько библиотек TLS уязвимы для этой атаки. ^[4]

Общий секрет равномерно распределен по подмножеству размером . По этой причине секрет не следует использовать непосредственно в качестве симметричного ключа, но его можно использовать в качестве энтропии для функции получения ключа. ${\displaystyle [0,p)}$ ${\displaystyle (n+1)/2}$

Ключевое соглашение Диффи-Хеллмана о кривых Монтгомери

Пусть такое то . Эллиптическая кривая формы Монтгомери представляет собой совокупность всех, удовлетворяющих уравнению, вместе с точкой на бесконечности, обозначенной как . Это называется аффинной формой кривой. Множество всех -рациональных точек , обозначаемых как, есть множество всех, удовлетворяющих наряду с . При правильно определенной операции сложения представляет собой группу с единичным элементом. Известно, что порядок этой группы кратен 4. На самом деле обычно можно получить и такое, что порядок для простого числа . Далее можно последовать более обширному обсуждению кривых Монтгомери и их арифметики. ^{[5] [6] [7]} ${\displaystyle A,B\in F_{p}}$ ${\displaystyle B(A^{2}-4)\neq 0}$ ${\displaystyle E_{M,A,B}}$ ${\displaystyle (x,y)\in F_{p}\times F_{p}}$ ${\displaystyle By^{2}=x(x^{2}+Ax+1)}$ ${\displaystyle \infty }$ ${\displaystyle F_{p}}$ ${\displaystyle E_{M,A,B}}$ ${\displaystyle E_{M,A,B}(F_{p})}$ ${\displaystyle (x,y)\in F_{p}\times F_{p}}$ ${\displaystyle By^{2}=x(x^{2}+Ax+1)}$ ${\displaystyle \infty }$ ${\displaystyle E_{M,A,B}(F_{p})}$ ${\displaystyle \infty }$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle E_{M,A,B}}$ ${\displaystyle 4q}$ ${\displaystyle q}$

Для эффективности вычислений предпочтительнее работать с проективными координатами. Проективная форма кривой Монтгомери равна . Для точки на -карта координат следующая: ^[7] if и if . Бернштейн ^{[8] [9]} ввел отображение следующим образом: которое определено для всех значений и в . Следуя Миллеру, ^[10], Монтгомери ^[5] и Бернштейну, ^[9] ключевое соглашение Диффи-Хеллмана может быть выполнено на кривой Монтгомери следующим образом. Пусть – генератор подгруппы простого порядка группы . Алиса выбирает секретный ключ и имеет открытый ключ ; Боб выбирает секретный ключ и имеет открытый ключ . Общий секретный ключ Алисы и Боба — . Использование классических компьютеров, наиболее известный метод получения и требует некоторого времени с использованием алгоритма Ро Полларда. ^[11] ${\displaystyle E_{M,A,B}}$ ${\displaystyle BY^{2}Z=X(X^{2}+AXZ+Z^{2})}$ ${\displaystyle P=[X:Y:Z]}$ ${\displaystyle E_{M,A,B}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x(P)=[X:Z]}$ ${\displaystyle Z\neq 0}$ ${\displaystyle x(P)=[1:0]}$ ${\displaystyle P=[0:1:0]}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{0}(X:Z)=XZ^{p-2}}$ ${\displaystyle X}$ ${\displaystyle Z}$ ${\displaystyle F_{p}}$ ${\displaystyle Q}$ ${\displaystyle E_{M,A,B}(F_{p})}$ ${\displaystyle s}$ ${\displaystyle x_{0}(sQ)}$ ${\displaystyle t}$ ${\displaystyle x_{0}(tQ)}$ ${\displaystyle x_{0}(stQ)}$ ${\displaystyle x_{0}(stQ)}$ ${\displaystyle Q,x_{0}(sQ)}$ ${\displaystyle x_{0}(tQ)}$ ${\displaystyle O(p^{1/2})}$

Самый известный пример кривой Монтгомери — Curve25519 , предложенный Бернштейном. ^[9] Для Curve25519 и . Другая кривая Монтгомери, являющаяся частью TLS 1.3, — это Curve448 , представленная Гамбургом. ^[12] Для Curve448 и . Пара кривых Монтгомери, названных M[4698] и M[4058], конкурирующих с Curve25519 и Curve448 соответственно, была предложена в ^[13] Для M[4698] и для M[4058], . На 256-битном уровне безопасности в ^[14] были предложены три кривые Монтгомери с названиями M[996558], M[952902] и M[ 1504058 ] . 1504058] соответственно. Помимо этих двух, другие предложения кривых Монтгомери можно найти по адресу. ^[15] ${\displaystyle p=2^{255}-19,A=486662}$ ${\displaystyle B=1}$ ${\displaystyle p=2^{448}-2^{224}-1,A=156326}$ ${\displaystyle B=1}$ ${\displaystyle p=2^{251}-9,A=4698,B=1}$ ${\displaystyle p=2^{444}-17,A=4058,B=1}$ ${\displaystyle p=2^{506}-45,A=996558,B=1}$ ${\displaystyle p=2^{510}-75,A=952902,B=1}$ ${\displaystyle p=2^{521}-1,A=1504058,B=1}$

Программное обеспечение

• Curve25519 — популярный набор параметров эллиптических кривых и эталонная реализация Дэниела Дж. Бернштейна на языке C. Также доступны привязки и альтернативные реализации.
• Приложение LINE Messenger использует протокол ECDH для сквозного шифрования всех сообщений, отправляемых через это приложение, с октября 2015 года. ^[16]
• Протокол Signal использует ECDH для обеспечения безопасности после компрометации. Реализации этого протокола встречаются в Signal , WhatsApp , Facebook Messenger и Skype .

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

• Обмен ключами Диффи-Хеллмана
• Прямая секретность

Рекомендации

1. NIST, Специальная публикация 800-56A, Рекомендации по схемам установления парных ключей с использованием криптографии дискретного логарифма, март 2006 г.
2. Certicom Research, Стандарты эффективной криптографии, SEC 1: Криптография с эллиптическими кривыми, версия 2.0, 21 мая 2009 г.
3. Криптография NSA Suite B, Руководство по внедрению Suite B для NIST SP 800-56A. Архивировано 6 марта 2016 г. на Wayback Machine , 28 июля 2009 г.
4. Тибор Ягер; Йорг Швенк; Юрай Соморовский (04 сентября 2015 г.). «Практические атаки на TLS-ECDH с использованием недействительных кривых» (PDF) . Европейский симпозиум по исследованиям в области компьютерной безопасности (ESORICS'15) .
5. Монтгомери, Питер Л. «Ускорение методов факторизации Полларда и эллиптических кривых» (PDF) . Математика вычислений, 48 (177): 243–264, 1987.
6. Бернштейн, Дэниел Дж.; Ланге, Таня. «Кривые Монтгомери и лестница Монтгомери». В книге Джоппе В. Боса и Арьена К. Ленстры, редакторов, «Темы вычислительной теории чисел», вдохновленные Питером Л. Монтгомери, страницы 82–115. Издательство Кембриджского университета, 2017.
7. Костелло, Крейг; Смит, Бенджамин. «Кривые Монтгомери и их арифметика - случай больших характеристических полей». Дж. Криптографическая инженерия, 8 (3): 227–240, 2018.
8. Бернштейн, Дэниел Дж. «Можем ли мы избежать проверки на ноль в быстрой арифметике с эллиптической кривой?» (PDF) .
9. Бернштейн, Дэниел Дж. «Curve25519: Новые рекорды скорости Диффи-Хеллмана». В: Юнг М., Додис Ю., Киайас А., Малкин Т. (ред.) Криптография с открытым ключом - PKC 2006. Конспект лекций по информатике, том 3958. Springer, Берлин, Гейдельберг.
10. Миллер, Виктор С. «Использование эллиптических кривых в криптографии». В журнале «Достижения в криптологии - CRYPTO'85», Санта-Барбара, Калифорния, США, 18–22 августа 1985 г., Труды, страницы 417–426. Шпрингер Берлин Гейдельберг, 1985.
11. Поллард, Джон М. «Методы Монте-Карло для вычисления индекса по модулю p» (PDF) . Математика вычислений, 32:918–924, 1978.
12. Гамбург, Майк. «Ed448-Златовласка, новая эллиптическая кривая». Архив электронной печати ACR Cryptology, 2015: 625, 2015.
13. Нат, Кошик; Саркар, Палаш. «Компромисс безопасности и эффективности для эллиптической кривой Диффи-Хеллмана на 128- и 224-битных уровнях безопасности». J Cryptogr Eng 12, 107–121 (2022)., Код доступен по адресу https://github.com/kn-cs/x25519.
14. Нат, Кошик; Саркар, Палаш. «Эффективное вычисление Диффи-Хеллмана по эллиптической кривой на 256-битном уровне безопасности». Информационная безопасность ИЭПП, 14(6):633640, 2020., Код доступен по адресу https://github.com/kn-cs/mont256-dh и https://github.com/kn-cs/mont256-vec.
15. Бернштейн, Дэниел Дж.; Ланге, Таня. «Безопасные кривые: выбор безопасных кривых для криптографии с эллиптическими кривыми» . Проверено 15 апреля 2024 г.
16. JI (13 октября 2015 г.). «Новое поколение безопасных сообщений: «Запечатывание писем»». Блог инженеров LINE . Компания ЛАЙН. Архивировано из оригинала 1 февраля 2019 года . Проверено 5 февраля 2018 г.