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

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

Эллиптическая кривая Диффи-Хеллмана ( 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] если и если . Бернштейн ^{[8] [9]} представил карту следующим образом: которая определена для всех значений и в . Следуя Миллеру ^[10] Монтгомери ^[5] и Бернштейну ^[9] соглашение о ключах Диффи-Хеллмана может быть выполнено на кривой Монтгомери следующим образом. Пусть будет генератором подгруппы простого порядка . Алиса выбирает секретный ключ и имеет открытый ключ ; Боб выбирает секретный ключ и имеет открытый ключ . Общий секретный ключ Алисы и Боба — . Используя классические компьютеры, наиболее известный метод получения из и требует около времени с использованием алгоритма Поллардса rho. ^[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 бит были предложены три кривые Монтгомери, названные M[996558], M[952902] и M[1504058] соответственно. ^[14] Для M[996558], , для M[952902] и для M[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. Также доступны привязки и альтернативные реализации.
• Curve448 — эллиптическая кривая, потенциально обеспечивающая 224 бита безопасности, разработанная Майком Гамбургом из Rambus Cryptography Research.
• Приложение LINE messenger использует протокол ECDH для сквозного шифрования «Letter Sealing» всех сообщений, отправляемых через это приложение, с октября 2015 года. ^[16]
• Signal Protocol использует 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. Архивировано 06.03.2016 на Wayback Machine , 28 июля 2009 г.
4. Тибор Ягер; Йорг Швенк; Юрай Соморовски (2015-09-04). "Практические атаки с использованием недействительных кривых на TLS-ECDH" (PDF) . Европейский симпозиум по исследованиям в области компьютерной безопасности (ESORICS'15) .
5. Монтгомери, Питер Л. «Ускорение методов Полларда и эллиптических кривых факторизации» (PDF) . Математика вычислений, 48(177):243–264, 1987.
6. Бернстайн, Дэниел Дж.; Ланге, Таня. «Кривые Монтгомери и лестница Монтгомери». В книге редакторов Joppe W. Bos и Arjen K. Lenstra «Темы вычислительной теории чисел, вдохновленные Питером Л. Монтгомери», страницы 82–115. Cambridge University Press, 2017.
7. Костелло, Крейг; Смит, Бенджамин. «Кривые Монтгомери и их арифметика — случай больших характеристических полей». J. Cryptographic Engineering, 8(3):227–240, 2018.
8. Бернстайн, Дэниел Дж. «Можно ли избежать проверок на ноль в быстрой арифметике эллиптических кривых?» (PDF) .
9. Bernstein, Daniel J. "Curve25519: Новые рекорды скорости Диффи-Хеллмана". В: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (ред.) Public Key Cryptography - PKC 2006. Lecture Notes in Computer Science, т. 3958. Springer, Berlin, Heidelberg.
10. Миллер, Виктор С. «Использование эллиптических кривых в криптографии». В Advances in Cryptology - CRYPTO'85, Санта-Барбара, Калифорния, США, 18-22 августа 1985 г., Труды, страницы 417–426. Springer Berlin Heidelberg, 1985.
11. Поллард, Джон М. «Методы Монте-Карло для вычисления индекса mod p» (PDF) . Математика вычислений, 32:918–924, 1978.
12. Гамбург, Майк. «Ed448-goldilocks, новая эллиптическая кривая». Архив ACR Cryptology ePrint, 2015:625, 2015.
13. Нат, Каушик; Саркар, Палаш. «Компромиссы безопасности и эффективности для эллиптических кривых Диффи-Хеллмана на уровнях безопасности 128 и 224 бит». J Cryptogr Eng 12, 107–121 (2022)., Код доступен по адресу https://github.com/kn-cs/x25519
14. Нат, Каушик; Саркар, Палаш. «Эффективное вычисление эллиптической кривой Диффи-Хеллмана на уровне безопасности 256 бит». IET Information Security, 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 . Корпорация LINE. Архивировано из оригинала 1 февраля 2019 г. Получено 5 февраля 2018 г.