Алгоритм цифровой подписи с эллиптической кривой - Elliptic Curve Digital Signature Algorithm

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Подтвердите это ${ displaystyle r}$ и ${ displaystyle s}$ целые числа в ${ Displaystyle [1, п-1]}$. В противном случае подпись недействительна.
2. Рассчитать ${ displaystyle e = { textrm {HASH}} (м)}$, где HASH - это та же функция, которая используется при генерации подписи.
3. Позволять ${ displaystyle z}$ быть ${ displaystyle L_ {n}}$ крайние левые части ${ displaystyle e}$.
4. Рассчитать ${ Displaystyle и_ {1} = zs ^ {- 1} , { bmod {,}} п}$ и ${ 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 г эквив х_ {1} { pmod {п}}}$, в противном случае недействителен.

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

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

Не сразу понятно, почему проверка вообще работает правильно. Чтобы понять почему, обозначим как ${ displaystyle 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}$

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

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

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

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

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

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

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

${ Displaystyle С = к раз G}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Расширяя определение ${ displaystyle 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}$, это открытый ключ Алисы.

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

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

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

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

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

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

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

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

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

Обе эти проблемы кратко изложены в libssh кривая25519 вступление.^[19]

Реализации

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

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

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

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

$ ДатаСр 4 мар, 10:24:52 EST 2020$ openssl s_client -connect wikipedia.org:443 # вывод ниже имеет УДАЛЕНИЯ для краткостиПОДКЛЮЧЕНО (00000003)depth = 2 O = Digital Signature Trust Co., CN = DST Корневой CA X3проверить возврат: 1глубина = 1 C = США, O = Let's Encrypt, CN = Let's Encrypt Authority X3проверить возврат: 1глубина = 0 CN = * .wikipedia.orgпроверить возврат: 1---Цепочка сертификатов 0 с: / 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 = Digital Signature Trust Co./CN=DST Корневой CA X3---Сертификат сервера----- НАЧАТЬ СЕРТИФИКАТ -----MIIHOTCCBiGgAwIBAgISA4srJU6bpT7xpINN6bbGO2 / mMA0GCSqGSIb3DQEBCwUA     ... УДАЛЕНО много строк ....kTOXMoKzBkJCU8sCdeziusJtNvWXW6p8Z3UpuTw =----- КОНЕЦ СЕРТИФИКАТА -----subject = / CN = *. wikipedia.orgэмитент = / C = US / O = Let's Encrypt / CN = Let's Encrypt Authority X3---Имена ЦС сертификатов клиента не отправленыДайджест подписи участников: 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    ID сеанса: ... УДАЛЕНО ...    Идентификатор сеанса-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, Конструкции, коды и криптография, 35, 119–152, 2005. версия ePrint
• Ян Ф. Блейк, Гадиэль Серусси и Найджел Смарт, редакторы, Достижения в криптографии с эллиптическими кривыми, Серия лекций Лондонского математического общества 317, Cambridge University Press, 2005.
• Hankerson, D .; Ванстон, С.; Менезеш, А. (2004). Руководство по криптографии с эллиптическими кривыми. Springer Professional Computing. Нью-Йорк: Springer. Дои:10.1007 / b97644. ISBN  0-387-95273-X. S2CID  720546.

внешняя ссылка

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