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

Криптографический алгоритм для цифровых подписей

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

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

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

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

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

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

Алиса создает пару ключей, состоящую из закрытого ключа integer , случайно выбранного в интервале ; и открытого ключа curve point . Мы используем для обозначения умножения точки эллиптической кривой на скаляр . ${\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 можно решить для , закрытого ключа: учитывая две подписи и , используя одно и то же неизвестное для разных известных сообщений и , злоумышленник может вычислить и , и поскольку (все операции в этом параграфе выполняются по модулю ), злоумышленник может найти . Поскольку , злоумышленник теперь может вычислить закрытый ключ . ${\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 r,s}$ ${\displaystyle m}$ ${\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. Пусть будут крайними левыми битами e . ${\displaystyle z}$ ${\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}$

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

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

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

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

Реализации

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

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

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

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

Ссылки

1. Джонсон, Дон; Менезес, Альфред (1999). "Алгоритм цифровой подписи на эллиптических кривых (ECDSA)". Исследования Certicom. Канада . CiteSeerX  10.1.1.38.8014 .
2. NIST FIPS 186-4, июль 2013 г., стр. 19 и 26.
3. Console Hacking 2010 — PS3 Epic Fail Архивировано 15 декабря 2014 г. на Wayback Machine , стр. 123–128.
4. "Уязвимость безопасности Android" . Получено 24 февраля 2015 г. .
5. Порнин, Т. (2013). RFC 6979 — Детерминированное использование алгоритма цифровой подписи (DSA) и алгоритма цифровой подписи на эллиптических кривых (ECDSA) (технический отчет). doi : 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. "Архив Cryptology ePrint: Отчет 2011/232" . Получено 24 февраля 2015 г.
10. «Заметка об уязвимости VU#536044 — OpenSSL допускает утечку закрытого ключа ECDSA посредством удаленной атаки по времени». www.kb.cert.org .
11. "ChangeLog". OpenSSL Project . Получено 22 апреля 2014 г.
12. "Ошибка Android разрушает кошельки Bitcoin". The Register. 12 августа 2013 г.
13. Шнайер, Брюс (5 сентября 2013 г.). «АНБ взламывает большинство шифров в Интернете». Шнайер о безопасности .
14. "SafeCurves: выбор безопасных кривых для эллиптической криптографии". 25 октября 2013 г.
15. Бернстайн, Дэниел Дж.; Ланге, Таня (31 мая 2013 г.). «Угрозы безопасности кривых NIST» (PDF) .
16. Шнайер, Брюс (15 ноября 2007 г.). «Странная история Dual_EC_DRBG». Шнайер о безопасности .
17. Гринемайер, Ларри (18 сентября 2013 г.). «Попытки АНБ обойти технологию шифрования нанесли ущерб стандарту криптографии США». Scientific American.
18. "[email protected]\doc - projects/libssh.git". Общий репозиторий libssh .
19. Бернстайн, Дэниел Дж. (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. Версия для печати в электронном виде
• Ян Ф. Блейк, Гадиэль Серусси и Найджел Смарт , редакторы, Advances in Elliptic Curve Cryptography , London Mathematical Society Lecture Notes Series 317, Cambridge University Press, 2005.
• Hankerson, D.; Vanstone, S .; Menezes, A. (2004). Руководство по эллиптической криптографии . Springer Professional Computing. Нью-Йорк: Springer . doi :10.1007/b97644. ISBN 0-387-95273-X. S2CID  720546.

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

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