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

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

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

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

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

Общий секрет, рассчитанный обеими сторонами, одинаков, поскольку $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 ]}

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

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

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

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

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

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

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

См. также

Ссылки

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

[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) .

[plmont-5] Jump up to: ^а ^б Монтгомери, Питер Л. «Ускорение методов факторизации Полларда и эллиптических кривых» (PDF) . Математика вычислений, 48 (177): 243–264, 1987.

[djbmont-6] Бернштейн, Дэниел Дж.; Ланге, Таня. «Кривые Монтгомери и лестница Монтгомери» . В книге Джоппе В. Боса и Арьена К. Ленстры, редакторов, «Темы вычислительной теории чисел», вдохновленные Питером Л. Монтгомери, страницы 82–115. Издательство Кембриджского университета, 2017.

[costellomont-7] Jump up to: ^а ^б Костелло, Крейг; Смит, Бенджамин. «Кривые Монтгомери и их арифметика — случай больших характеристических полей» . Дж. Криптографическая инженерия, 8 (3): 227–240, 2018.

[8] Бернштейн, Дэниел Дж. «Можем ли мы избежать проверки нуля в быстрой арифметике с эллиптическими кривыми?» (PDF) .

[curve25519-9] Jump up to: ^а ^б ^с Бернштейн, Дэниел Дж. «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.

[knpsjec2022-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 г.

[linecorp-letter-sealing-16] СО (13 октября 2015 г.). «Новое поколение безопасных сообщений: «Запечатывание писем» » . Блог инженеров LINE . Компания ЛАЙН. Архивировано из оригинала 1 февраля 2019 года . Проверено 5 февраля 2018 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]