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

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

Размер ключа и подписи [ править ]

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

Алгоритм генерации подписи [ править ]

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

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

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

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

Чтобы Алиса подписала сообщение , она выполняет следующие действия:${\displaystyle m}$

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

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

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

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

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

Алгоритм проверки подписи [ править ]

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

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

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

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

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

Правильность алгоритма [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle C=k\times G}$

По определению r это этап проверки 6.

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

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

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

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

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

Правильность алгоритма восстановления [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Безопасность [ править ]

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

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

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

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

Проблемы [ править ]

Существует два типа проблем с ECDSA:

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

Оба этих проблем приведены в libssh curve25519 введения . ^[20]

Реализации [ править ]

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

• Ботан
• Надувной Замок
• cryptlib
• Крипто ++
• libgcrypt
• GnuTLS
• OpenSSL
• волк
• LibreSSL
• mbed TLS
• Microsoft CryptoAPI
• Crypto API (Linux)

Пример использования [ править ]

Wikipedia.org использует ECDSA в наборе шифров TLS для аутентификации в веб-браузерах, что показано в следующей сокращенной транскрипции.

$ date среда, 4 марта 10:24:52 EST 2020 $ openssl s_client -connect wikipedia.org:443 # в приведенных ниже выводах для краткости указаны УДАЛЕНИЯ СОЕДИНЕН (00000003) depth = 2 O = Digital Signature Trust Co., CN = DST Root CA X3 verify return: 1 depth = 1 C = US, O = Let's Encrypt, CN = Let's Encrypt Authority X3 verify return: 1 depth = 0 CN = * .wikipedia.org verify return: 1 --- Цепочка сертификатов 0 s: / CN = *. wikipedia.org  i: / C = US / O = Let's Encrypt / CN = Let's Encrypt Authority X3 1 с: / C = US / O = Let's Encrypt / CN = Let's Encrypt Authority X3  i: / O = Цифровая подпись Trust Co./CN=DST Root CA X3 --- Сертификат сервера----- BEGIN CERTIFICATE ----- MIIHOTCCBiGgAwIBAgISA4srJU6bpT7xpINN6bbGO2 / mMA0GCSqGSIb3DQEBCwUA  ... много линий DELETED .... kTOXMoKzBkJCU8sCdeziusJtNvWXW6p8Z3UpuTw = ----- END CERTIFICATE ----- Заголовок = / CN = *. Wikipedia.org эмитент = / C = US / O = Let's Encrypt / CN = Let's Encrypt Authority X3 --- Не отправлены имена CA сертификатов клиента Дайджест подписи однорангового узла: SHA256 Временный ключ сервера: ECDH, P-256, 256 бит --- Подтверждение SSL прочитано 3353 байта и записанные 431 байта --- Новый, TLSv1 / SSLv3, Шифр ​​- ECDHE-ECDSA-AES256-GCM-SHA384 Открытый ключ сервера - 256 бит Безопасное повторное согласование поддерживается Сжатие: НЕТ Расширение: НЕТНет согласованного ALPN SSL-сеанс:  Протокол: TLSv1.2  Шифр: ECDHE-ECDSA-AES256-GCM-SHA384  Идентификатор сеанса: ... УДАЛЕН ...  Идентификатор сеанса-ctx:  Мастер-ключ: ... УДАЛЕНО .. .  Key-Arg: Нет  Идентификатор PSK: Нет  Подсказка идентификатора PSK: Нет  Имя пользователя SRP: Нет  Время начала: 1583335210  Тайм-аут: 300 (сек)  Проверить код возврата: 0 (ок) --- ГОТОВО

См. Также [ править ]

• EdDSA
• RSA (криптосистема)

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Аккредитованный комитет по стандартам 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 , Designs, Codes and Cryptography, 35 , 119–152, 2005. Версия для печати ePrint
• Ян Ф. Блейк, Гадиэль Серусси и Найджел Смарт , редакторы, Advances in Elliptic Curve Cryptography , London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
• Hankerson, D .; Ванстон, С .; Менезес, А. (2004). Руководство по криптографии с эллиптическими кривыми . Springer Professional Computing. Нью-Йорк: Спрингер . DOI : 10.1007 / b97644 . ISBN 0-387-95273-X. S2CID  720546 .

Внешние ссылки [ править ]

• Стандарт цифровой подписи; включает информацию о ECDSA
• Алгоритм цифровой подписи с эллиптической кривой (ECDSA); предоставляет подробное руководство по ECDSA . Обратная ссылка