Алгоритм цифровой подписи эллиптической кривой

В криптографии алгоритм цифровой подписи с эллиптической кривой ( ECDSA ) предлагает вариант алгоритма цифровой подписи (DSA), который использует криптографию с эллиптической кривой .

Размеры ключей и подписей

Как и в случае с криптографией на основе эллиптических кривых в целом, размер секретного ключа , который, как предполагается, необходим для ECDSA, примерно в два раза превышает размер уровня безопасности в битах. ^{[ 1 ]} Например, при уровне безопасности 80 бит — это означает, что злоумышленнику требуется максимум около $2^{80}$ операции по поиску закрытого ключа — размер закрытого ключа ECDSA будет составлять 160 бит. С другой стороны, размер подписи и для DSA, и для ECDSA одинаков: примерно $4t$ биты, где $t$ является показателем степени в формуле $2^{t}$ , то есть около 320 бит для уровня безопасности 80 бит, что эквивалентно $2^{80}$ операции.

Алгоритм генерации подписи

Предположим, Алиса хочет послать Бобу подписанное сообщение . Первоначально они должны согласовать параметры кривой. $({\textrm {CURVE}},G,n)$ . Помимо поля и уравнения кривой нам понадобится $G$ , базовая точка простого порядка на кривой; $n$ - мультипликативный порядок точки $G$ .

Параметр
ИЗГИБ	используемое поле эллиптической кривой и уравнение
Г	базовая точка эллиптической кривой, точка на кривой, которая порождает подгруппу большого простого порядка n
н	целого порядка G означает, что $n\times G=O$ , где $O$ является элементом идентичности.
$d_{A}$	закрытый ключ (выбирается случайно)
$Q_{A}$	открытый ключ $d_{A}\times G$ (рассчитано по эллиптической кривой)
м	сообщение для отправки

Порядок $n$ базовой точки $G$ должен быть простым . Действительно, мы предполагаем, что каждый ненулевой элемент кольца $\mathbb {Z} /n\mathbb {Z}$ обратима, так что $\mathbb {Z} /n\mathbb {Z}$ должно быть поле . Это подразумевает, что $n$ должно быть простым (ср. тождество Безу ).

Алиса создает пару ключей, состоящую из целого числа закрытого ключа. $d_{A}$ , случайно выбранный в интервале $[1,n-1]$ ; и точка кривой открытого ключа $Q_{A}=d_{A}\times G$ . Мы используем $\times$ для обозначения умножения точки эллиптической кривой на скаляр .

Чтобы Алиса подписала сообщение $m$ , она выполняет следующие шаги:

Рассчитать $e={\textrm {HASH}}(m)$ . (Здесь HASH — это криптографическая хеш-функция , такая как SHA-2 , выходные данные которой преобразуются в целое число.)
Позволять $z$ быть $L_{n}$ самые левые биты $e$ , где $L_{n}$ длина в битах группового порядка $n$ . (Обратите внимание, что $z$ может быть больше, чем $n$ но не дольше . ^{[ 2 ]})
Выберите криптографически безопасное случайное целое число. $k$ от $[1,n-1]$ .
Вычислить точку кривой $(x_{1},y_{1})=k\times G$ .
Рассчитать $r=x_{1}\,{\bmod {\,}}n$ . Если $r=0$ , вернитесь к шагу 3.
Рассчитать $s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$ . Если $s=0$ , вернитесь к шагу 3.
Подпись - пара $(r,s)$ . (И $(r,-s\,{\bmod {\,}}n)$ также является действительной подписью.)

Как отмечается в стандарте, это требуется не только для $k$ быть секретным, но также важно выбирать разные $k$ для разных подписей. В противном случае уравнение из шага 6 можно решить для $d_{A}$ , закрытый ключ: с учетом двух подписей $(r,s)$ и $(r,s')$ , используя ту же самую неизвестную $k$ для разных известных сообщений $m$ и $m'$ , злоумышленник может вычислить $z$ и $z'$ , и поскольку $s-s'=k^{-1}(z-z')$ (все операции в этом пункте выполняются по модулю $n$ ) злоумышленник может найти $k={\frac {z-z'}{s-s'}}$ . С $s=k^{-1}(z+rd_{A})$ , теперь злоумышленник может вычислить закрытый ключ $d_{A}={\frac {sk-z}{r}}$ .

Эта ошибка реализации была использована, например, для извлечения ключа подписи, используемого для PlayStation 3 . игровой консоли ^{[ 3 ]}

Другой способ, которым подпись ECDSA может привести к утечке закрытых ключей, — это когда $k$ генерируется неисправным генератором случайных чисел . Подобный сбой в генерации случайных чисел привел к тому, что пользователи Android Bitcoin Wallet потеряли свои средства в августе 2013 года. ^{[ 4 ]}

Чтобы гарантировать, что $k$ уникален для каждого сообщения, можно полностью обойти генерацию случайных чисел и генерировать детерминированные подписи, получив $k$ как из сообщения, так и из закрытого ключа. ^{[ 5 ]}

Алгоритм проверки подписи

Чтобы Боб подтвердил подлинность подписи Алисы $r,s$ в сообщении $m$ , у него должна быть копия ее точки кривой открытого ключа $Q_{A}$ . Боб может проверить $Q_{A}$ является допустимой точкой кривой следующим образом:

Проверьте это $Q_{A}$ не равен единичному элементу $O$ , и в противном случае его координаты действительны.
Проверьте это $Q_{A}$ лежит на кривой.
Проверьте это $n\times Q_{A}=O$ .

После этого Боб выполняет следующие шаги:

Убедитесь, что $r$ и $s$ являются целыми числами в $[1,n-1]$ . В противном случае подпись недействительна.
Рассчитать $e={\textrm {HASH}}(m)$ , где HASH — это та же функция, которая используется при генерации подписи.
Позволять $z$ быть $L_{n}$ самые левые биты $e$ .
Рассчитать $u_{1}=zs^{-1}\,{\bmod {\,}}n$ и $u_{2}=rs^{-1}\,{\bmod {\,}}n$ .
Вычислить точку кривой $(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}$ . Если $(x_{1},y_{1})=O$ тогда подпись недействительна.
Подпись действительна, если $r\equiv x_{1}{\pmod {n}}$ , в противном случае недействителен.

Обратите внимание, что эффективная реализация будет вычислять обратную $s^{-1}\,{\bmod {\,}}n$ только один раз. Кроме того, используя трюк Шамира, сумма двух скалярных умножений $u_{1}\times G+u_{2}\times Q_{A}$ можно вычислить быстрее, чем два скалярных умножения, выполненные независимо. ^{[ 6 ]}

Корректность алгоритма

Не сразу понятно, почему проверка вообще работает правильно. Чтобы понять почему, обозначим как $C$ точку кривой, вычисленную на этапе 5 проверки:

C=u_{1}\times G+u_{2}\times Q_{A}

Из определения открытого ключа как $Q_{A}=d_{A}\times G$ ,

C=u_{1}\times G+u_{2}d_{A}\times G

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

C=(u_{1}+u_{2}d_{A})\times G

Расширяя определение $u_{1}$ и $u_{2}$ начиная с шага проверки 4,

C=(zs^{-1}+rd_{A}s^{-1})\times G

Собираем общий термин $s^{-1}$ ,

C=(z+rd_{A})s^{-1}\times G

Расширяя определение $s$ из шага 6 подписи,

C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}\times G

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

C=k\times G

Из определения $r$ это шаг проверки 6.

Это показывает только то, что правильно подписанное сообщение будет проверено правильно; другие свойства, такие как неправильно подписанные сообщения, которые не могут быть проверены правильно, и устойчивость к криптоаналитическим атакам, необходимы для безопасного алгоритма подписи.

Восстановление открытого ключа

Учитывая сообщение $m$ и подпись Алисы $r,s$ по этому сообщению Боб может (потенциально) восстановить открытый ключ Алисы: ^{[ 7 ]}

Убедитесь, что $r$ и $s$ являются целыми числами в $[1,n-1]$ . В противном случае подпись недействительна.
Вычислить точку кривой $R=(x_{1},y_{1})$ где $x_{1}$ является одним из $r$ , $r+n$ , $r+2n$ и т. д. (при условии $x_{1}$ не слишком велико для поля кривой) и $y_{1}$ такое значение, что уравнение кривой удовлетворяется. Обратите внимание, что может быть несколько точек кривой, удовлетворяющих этим условиям, и каждое другое $значение R$ приводит к отдельному восстановленному ключу.
Рассчитать $e={\textrm {HASH}}(m)$ , где HASH — это та же функция, которая используется при генерации подписи.
Пусть $z$ будет $L_{n}$ самые левые биты $e$ .
Рассчитать $u_{1}=-zr^{-1}\,{\bmod {\,}}n$ и $u_{2}=sr^{-1}\,{\bmod {\,}}n$ .
Вычислить точку кривой $Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R$ .
Подпись действительна, если $Q_{A}$ , соответствует открытому ключу Алисы.
Подпись недействительна, если были испробованы все возможные $точки R$ , и ни одна из них не соответствует открытому ключу Алисы.

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

Корректность алгоритма восстановления

Начните с определения $Q_{A}$ с шага восстановления 6,

Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R

Из определения $R=(x_{1},y_{1})=k\times G$ с момента подписания шага 4,

Q_{A}=u_{1}\times G+u_{2}k\times G

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

Q_{A}=(u_{1}+u_{2}k)\times G

Расширяя определение $u_{1}$ и $u_{2}$ с шага восстановления 5,

Q_{A}=(-zr^{-1}+skr^{-1})\times G

Расширяя определение $s$ из шага 6 подписи,

Q_{A}=(-zr^{-1}+k^{-1}(z+rd_{A})kr^{-1})\times G

Поскольку произведение обратного элемента и элемента является единицей, у нас остается

Q_{A}=(-zr^{-1}+(zr^{-1}+d_{A}))\times G

Первое и второе слагаемые компенсируют друг друга,

Q_{A}=d_{A}\times G

Из определения $Q_{A}=d_{A}\times G$ , это открытый ключ Алисы.

Это показывает, что правильно подписанное сообщение восстановит правильный открытый ключ при условии, что дополнительная информация была передана для однозначного расчета точки кривой. $R=(x_{1},y_{1})$ из значения подписи $r$ .

Безопасность

В декабре 2010 года группа, назвавшая себя Fail0verflow, объявила о восстановлении закрытого ключа ECDSA, используемого Sony для подписи программного обеспечения для игровой консоли PlayStation 3 . Однако эта атака сработала только потому, что Sony не реализовала алгоритм должным образом, поскольку $k$ был статичным, а не случайным. Как указано выше в разделе «Алгоритм генерации подписи» , это делает $d_{A}$ разрешима, что делает весь алгоритм бесполезным. ^{[ 8 ]}

29 марта 2011 г. два исследователя опубликовали IACR . статью ^{[ 9 ]} демонстрация возможности получения закрытого ключа TLS сервера с использованием OpenSSL , который аутентифицируется с помощью Elliptic Curves DSA по двоичному полю посредством временной атаки . ^{[ 10 ]} Уязвимость была исправлена в OpenSSL 1.0.0e. ^{[ 11 ]}

В августе 2013 года выяснилось, что ошибки в некоторых реализациях Java- класса SecureRandom иногда приводили к коллизиям в $k$ ценить. Это позволило хакерам восстановить закрытые ключи, предоставив им тот же контроль над транзакциями биткойнов, что и владельцы законных ключей, используя тот же эксплойт, который использовался для раскрытия ключа подписи PS3 в некоторых реализациях приложений Android , которые используют Java и полагаются на ECDSA для аутентификации. транзакции. ^{[ 12 ]}

Эту проблему можно предотвратить с помощью детерминированной генерации k, как описано в RFC 6979.

Обеспокоенность

Некоторые опасения, высказанные по поводу ECDSA:

Политические проблемы : достоверность кривых, полученных NIST, подвергается сомнению после того, как стало известно, что АНБ охотно вставляет бэкдоры в программное обеспечение, аппаратные компоненты и опубликованные стандарты; известные криптографы ^{[ 13 ]} выразили ^{[ 14 ]}^{[ 15 ]} сомнения относительно того, как были построены кривые NIST, а добровольное искажение данных уже было доказано в прошлом. ^{[ 16 ]}^{[ 17 ]} (См. также в libssh Curve25519 введение . ^{[ 18 ]}) Тем не менее, доказательства того, что названные кривые NIST используют редкую слабость, пока отсутствуют.
Технические проблемы : сложность правильной реализации стандарта, его медлительность и недостатки конструкции, которые снижают безопасность в недостаточно защищенных реализациях. ^{[ 19 ]}

Реализации

Ниже приведен список криптографических библиотек, обеспечивающих поддержку ECDSA:

См. также

Ссылки

^ Джонсон, Дон; Менезес, Альфред (1999). «Алгоритм цифровой подписи на основе эллиптической кривой (ECDSA)». Исследование Сертиком. Канада . CiteSeerX 10.1.1.38.8014 .
^ NIST FIPS 186-4, июль 2013 г., стр. 19 и 26.
↑ Взлом консоли 2010 — PS3 Epic Fail. Архивировано 15 декабря 2014 г., в Wayback Machine , страницы 123–128.
^ «Уязвимость безопасности Android» . Проверено 24 февраля 2015 г.
^ Порнин, Т. (2013). RFC 6979 — Детерминированное использование алгоритма цифровой подписи (DSA) и алгоритма цифровой подписи на основе эллиптических кривых (ECDSA) (технический отчет). дои : 10.17487/RFC6979 . Проверено 24 февраля 2015 г.
^ «Двойная система счисления в криптографии с эллиптическими кривыми» (PDF) . Проверено 22 апреля 2014 г.
^ Дэниел Р.Л. Браун SECG SEC 1: Криптография с эллиптическими кривыми (версия 2.0) https://www.secg.org/sec1-v2.pdf
^ Бендель, Майк (29 декабря 2010 г.). «Хакеры описывают безопасность PS3 как эпический провал: получите неограниченный доступ» . Exophase.com . Проверено 5 января 2011 г.
^ «Архив криптологии ePrint: отчет 2011/232» . Проверено 24 февраля 2015 г.
^ «Примечание об уязвимости VU#536044 — OpenSSL утечка закрытого ключа ECDSA в результате удаленной атаки по времени» . www.kb.cert.org .
^ «Журнал изменений» . Проект OpenSSL . Проверено 22 апреля 2014 г.
^ «Ошибка Android поражает биткойн-кошельки» . Регистр. 12 августа 2013 г.
^ Шнайер, Брюс (5 сентября 2013 г.). «АНБ взламывает большую часть шифрования в Интернете» . Шнайер по безопасности .
^ «SafeCurves: выбор безопасных кривых для криптографии с эллиптическими кривыми» . 25 октября 2013 г.
^ Бернштейн, Дэниел Дж.; Ланге, Таня (31 мая 2013 г.). «Угрозы безопасности кривых NIST» (PDF) .
^ Шнайер, Брюс (15 ноября 2007 г.). «Странная история Dual_EC_DRBG» . Шнайер по безопасности .
^ Гринмайер, Ларри (18 сентября 2013 г.). «Попытки АНБ обойти технологию шифрования, нарушившую стандарт криптографии США» . Научный американец.
^ « [электронная почта защищена] \doc - project/libssh.git» . Общий репозиторий libssh .
^ Бернштейн, Дэниел Дж. (23 марта 2014 г.). «Как спроектировать систему подписи на основе эллиптической кривой» . Блог cr.yp.to.

Дальнейшее чтение

Аккредитованный комитет по стандартам X9 , ASC X9 выпускает новый стандарт криптографии с открытым ключом/ECDSA , 6 октября 2020 г. Источник
Аккредитованный комитет по стандартам X9 , Американский национальный стандарт X9.62-2005, Криптография с открытым ключом для индустрии финансовых услуг, Алгоритм цифровой подписи на основе эллиптической кривой (ECDSA) , 16 ноября 2005 г.
Certicom Research, Стандарты эффективной криптографии, SEC 1: Криптография с эллиптическими кривыми , версия 2.0, 21 мая 2009 г.
Лопес Дж. и Дахаб Р. Обзор криптографии с эллиптическими кривыми , Технический отчет IC-00-10, Государственный университет Кампинаса, 2000 г.
Дэниел Дж. Бернштейн , Алгоритм возведения в степень Пиппенджера , 2002.
Дэниел Р.Л. Браун, Общие группы, устойчивость к столкновениям и ECDSA , Проекты, коды и криптография, 35 , 119–152, 2005. Версия для электронной печати
Ян Ф. Блейк, Гадиэль Серусси и Найджел Смарт , редакторы, «Достижения в криптографии эллиптических кривых» , серия 317 лекций Лондонского математического общества, Cambridge University Press, 2005.
Хэнкерсон, Д.; Ванстон, С. ; Менезес, А. (2004). Руководство по криптографии на основе эллиптических кривых . Springer Профессиональные вычисления. Нью-Йорк: Спрингер . дои : 10.1007/b97644 . ISBN 0-387-95273-Х . S2CID 720546 .

Внешние ссылки

[1] Джонсон, Дон; Менезес, Альфред (1999). «Алгоритм цифровой подписи на основе эллиптической кривой (ECDSA)». Исследование Сертиком. Канада . CiteSeerX 10.1.1.38.8014 .

[2] NIST FIPS 186-4, июль 2013 г., стр. 19 и 26.

[3] Взлом консоли 2010 — PS3 Epic Fail. Архивировано 15 декабря 2014 г., в Wayback Machine , страницы 123–128.

[4] «Уязвимость безопасности Android» . Проверено 24 февраля 2015 г.

[5] Порнин, Т. (2013). RFC 6979 — Детерминированное использование алгоритма цифровой подписи (DSA) и алгоритма цифровой подписи на основе эллиптических кривых (ECDSA) (технический отчет). дои : 10.17487/RFC6979 . Проверено 24 февраля 2015 г.

[6] «Двойная система счисления в криптографии с эллиптическими кривыми» (PDF) . Проверено 22 апреля 2014 г.

[7] Дэниел Р.Л. Браун SECG SEC 1: Криптография с эллиптическими кривыми (версия 2.0) https://www.secg.org/sec1-v2.pdf

[8] Бендель, Майк (29 декабря 2010 г.). «Хакеры описывают безопасность PS3 как эпический провал: получите неограниченный доступ» . Exophase.com . Проверено 5 января 2011 г.

[9] «Архив криптологии ePrint: отчет 2011/232» . Проверено 24 февраля 2015 г.

[10] «Примечание об уязвимости VU#536044 — OpenSSL утечка закрытого ключа ECDSA в результате удаленной атаки по времени» . www.kb.cert.org .

[11] «Журнал изменений» . Проект OpenSSL . Проверено 22 апреля 2014 г.

[12] «Ошибка Android поражает биткойн-кошельки» . Регистр. 12 августа 2013 г.

[13] Шнайер, Брюс (5 сентября 2013 г.). «АНБ взламывает большую часть шифрования в Интернете» . Шнайер по безопасности .

[14] «SafeCurves: выбор безопасных кривых для криптографии с эллиптическими кривыми» . 25 октября 2013 г.

[15] Бернштейн, Дэниел Дж.; Ланге, Таня (31 мая 2013 г.). «Угрозы безопасности кривых NIST» (PDF) .

[16] Шнайер, Брюс (15 ноября 2007 г.). «Странная история Dual_EC_DRBG» . Шнайер по безопасности .

[17] Гринмайер, Ларри (18 сентября 2013 г.). «Попытки АНБ обойти технологию шифрования, нарушившую стандарт криптографии США» . Научный американец.

[18] « [электронная почта защищена] \doc - project/libssh.git» . Общий репозиторий libssh .

[19] Бернштейн, Дэниел Дж. (23 марта 2014 г.). «Как спроектировать систему подписи на основе эллиптической кривой» . Блог cr.yp.to.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]