Interested Article - ECDSA

ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом , использующийся для построения и проверки электронной цифровой подписи при помощи криптографии на эллиптических кривых .

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

История

Эллиптические кривые в качестве математического понятия изучаются уже достаточно давно. Например, ещё у древнегреческого математика Диофанта в III веке нашей эры в труде « Арифметика » были задачи, которые сводились к нахождению рациональных точек на эллиптической кривой . Однако, их применение для реальных задач, в частности, для области криптографии, было неизвестно до конца XX века. В 1985 году Виктор Миллер и Нил Коблиц предложили использование эллиптических кривых для криптографии .

В 1991 году Национальным институтом стандартов и технологий (NIST) был разработан DSA , построенный на идее использования проблемы дискретного логарифма . Вскоре после этого NIST запросил публичные комментарии по поводу своего предложения о схемах цифровой подписи. Воодушевившись данной идеей, Скотт Ванстоун в статье «Responses to NIST’s proposal» предложил аналог алгоритму цифровой подписи, использующий криптографию на эллиптических кривых (ECDSA) .

В период с 1998-2000 гг. ECDSA был принят различными организациями как стандарт ( ISO 14888-3, ANSI X9.62, IEEE 1363—2000, FIPS 186-2) .

Применение

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

Основные параметры эллиптической кривой

Основными параметрами (англ. domain parameters) ${\textstyle D=(q,FR,a,b,G,n,h)}$ эллиптической кривой над конечным полем $\mathbb {F} _{q}$ называется совокупность следующих величин :

Порядок конечного поля $q$ (например, простое конечное поле $\mathbb {F} _{p}$ при ${\textstyle q=p}$ , где ${\textstyle p>3}$ и является простым числом ).
${\textstyle FR}$ (Field Representation) — индикатор , использующийся для представления элементов, принадлежащих полю $\mathbb {F} _{q}$ .
Два элемента поля $a,b\in \mathbb {F} _{q}$ , задающие коэффициенты уравнения эллиптической кривой $E$ над полем $\mathbb {F} _{q}$ (например, $y^{2}=x^{3}+ax+b$ при $q=p>3$ ).
Базовая точка ${\textstyle G=(x_{G},y_{G})\in E(\mathbb {F} _{q})}$ , имеющая простой порядок $n$ .
Целое число ${\textstyle h}$ , являющееся кофактором ${\textstyle h=\#E(\mathbb {F} _{q})/n}$ , где ${\textstyle \#E(\mathbb {F} _{q})}$ — порядок кривой, численно совпадающий с числом точек в ${\textstyle E(\mathbb {F} _{q})}$ .

Параметры должны быть выбраны таким образом, чтобы эллиптическая кривая, определённая над конечным полем $\mathbb {F} _{q}$ , была устойчива ко всем известным атакам, применимым к ECDLP . Помимо этого могут быть и другие ограничения, связанные с соображениями безопасности или реализации. Как правило, основные параметры являются общими для группы сущностей, однако в некоторых приложениях (реализациях), они могут быть специфичными для каждого конкретного пользователя

ECDSA по стандарту ANSI X9.62

Для практического применения ECDSA налагают ограничения на поля , в которых определены эллиптические кривые. Для простоты рассмотрим случай реализации алгоритмов, когда $\mathbb {F} _{q}$ — простое конечное поле (для других полей — аналогично), тогда наше эллиптическое уравнение принимает вид ${\textstyle y^{2}=x^{3}+ax+b}$ .

Алгоритм генерации основных параметров

Для того, чтобы избежать известных атак, основанных на проблеме дискретного логарифма в группе точек эллиптической кривой , необходимо, чтобы число точек эллиптической кривой $E$ делилось на достаточно большое простое число $n$ . Стандарт ANSI X9.62 требует $n>2^{160}$ . Предлагается следующий алгоритм :

Ввод : Порядок поля $q$ , индикатор представления поля $FR$ для ${\textstyle \mathbb {F} _{q}}$ , $L$ - уровень безопасности: ${\textstyle 160\leqslant L\leqslant [\log _{2}q]}$ и ${\textstyle 2^{L}\geqslant 4{\sqrt {q}}}$ .

Вывод : Основные параметры эллиптической кривой ${\textstyle D=(q,FR,a,b,G,n,h)}$ .

Шаг 1. Выберите верифицировано случайным образом элементы ${\textstyle a,b\in \mathbb {F} _{q}}$ , удовлетворяющие условию $4a^{3}+27b^{2}\not \equiv 0{\bmod {q}}$ .

Шаг 2. ${\textstyle N:=\#E(\mathbb {F} _{q})}$ , порядок кривой можно вычислить при помощи алгоритма .

Шаг 3. Проверьте, что ${\textstyle N{\bmod {n}}=0}$ при большом простом числе $n\geqslant 2^{L}$ . Если нет, тогда перейдите к шагу 1.

Шаг 4. Проверьте, что $q^{k}-1{\bmod {n}}=0$ $\forall k\in [1,20]$ . Если нет, тогда перейдите к шагу 1.

Шаг 5. Проверьте, что $n\neq q$ . Если нет, тогда перейдите к шагу 1.

Шаг 6. $h:=N/n$ .

Шаг 7. Выберите произвольную точку ${\textstyle G^{'}\in E(\mathbb {F} _{q})}$ и задайте ${\textstyle G:=hG^{'}}$ . Повторяйте, пока ${\textstyle G\neq {\mathcal {O}}}$ , где ${\mathcal {O}}$ - бесконечно удалённая точка

Шаг 8. Верните ${\textstyle (q,FR,a,b,G,n,h)}$

Алгоритмы верификации случайным образом дают гарантию того, что эллиптическая кривая над конечным полем была сгенерирована абсолютно случайно .

Алгоритм генерации ключевой пары

Будем рассматривать обмен сообщениями между Алисой и Бобом . Предварительно используя алгоритм генерации основных параметров, Алиса получает свои основные параметры эллиптической кривой. Используя следующую последовательность действий, Алиса сгенерирует себе открытый и закрытый ключ .

Ввод : Основные параметры эллиптической кривой ${\textstyle D}$ .

Вывод : Открытый ключ - $Q$ , закрытый ключ - $d$ .

Шаг 1. Выберите случайное или псевдослучайное целое число $d\in [1,n-1]$ .

Шаг 2. Вычислите координаты точки на эллиптической кривой $Q=dG$ .

Шаг 3. Верните $(Q,d)$ .

Алгоритм проверки открытого ключа

Целью проверки открытого ключа является подтверждение того, что открытый ключ обладает определенными арифметическими свойствами . Успешное выполнение данного алгоритма демонстрирует, что соответствующий закрытый ключ математически существует, но не гарантирует, что кто-то не вычислил данный закрытый ключ или что заявленный владелец действительно обладает им .

Ввод : Основные параметры эллиптической кривой ${\textstyle D}$ , открытый ключ - $Q$ .

Вывод : Решение о принятии или отклонении достоверности открытого ключа $Q$ .

Шаг 1. Проверьте, что ${\textstyle Q\neq {\mathcal {O}}}$ .

Шаг 2. Проверьте, что ${\textstyle (x_{G},y_{G})}$ являются правильно представленными элементами в ${\textstyle \mathbb {F} _{q}}$ , т.е. целыми числами, принадлежащими ${\textstyle [1,q-1]}$ .

Шаг 3. Проверьте, что ${\textstyle Q}$ удовлетворяет уравнению эллиптической кривой, определяемому элементами поля ${\textstyle a,b}$ .

Шаг 4. Проверьте, что ${\textstyle nQ={\mathcal {O}}}$ .

Шаг 5. Если какая-либо проверка не прошла, то вернуть "Отклонить", иначе "Принять".

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

Алиса, обладающая основными параметрами кривой $D$ и закрытым ключом $d$ , хочет подписать сообщение $m$ , для этого она должна сгенерировать подпись $(r,s)$ .

В дальнейшем ${\mathcal {H}}$ обозначает криптографическую хэш-функцию , выходное значение которой имеют битовую длину не более $n$ (если это условие не выполняется, то выходное значение ${\mathcal {H}}$ может быть усечено). Предполагается, что мы работаем с выходом функции, уже преобразованным в целое число.

Ввод : Основные параметры эллиптической кривой ${\textstyle D}$ , закрытый ключ $d$ , сообщение $m$ .

Вывод : Подпись $(r,s)$ .

Шаг 1. Выберите случайное или псевдослучайное целое число $k\in [1,n-1]$ .

Шаг 2. Вычислите координаты точки $kG=(x_{1},y_{1})$ .

Шаг 3. Вычислите $r=x_{1}{\bmod {n}}$ . Если $r=0$ , тогда перейдите к шагу 1.

Шаг 4. Вычислите $e={\mathcal {H}}(m)$ .

Шаг 5. Вычислите $s=k^{-1}(e+dr){\bmod {n}}$ . Если $s=0$ , тогда перейдите к шагу 1.

Шаг 6. Верните $(r,s)$ .

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

Чтобы проверить подпись Алисы $(r,s)$ сообщения $m$ , Боб получает аутентичную копию её основных параметров кривой $D$ и связанный с ними открытый ключ $Q$ :.

Ввод : Основные параметры эллиптической кривой ${\textstyle D}$ , открытый ключ $Q$ , сообщение $m$ , подпись $(r,s)$ .

Вывод : Решение о принятии или отклонении подписи.

Шаг 1. Проверьте, что $r,s$ - целые числа, принадлежащие $[1,n-1]$ . Если какая-либо проверка не удалась, то вернуть "Отклонить".

Шаг 2. Вычислите $e={\mathcal {H}}(m)$ .

Шаг 3. Вычислите $w=s^{-1}{\bmod {n}}$ .

Шаг 4. Вычислите $u_{1}=ew{\bmod {n}}$ и $u_{2}=rw{\bmod {n}}$ .

Шаг 5. Вычислите координаты точки $X=(x_{2},y_{2})=u_{1}G+u_{2}Q$ .

Шаг 6. Если $X={\mathcal {O}}$ , то вернуть "Отклонить". Иначе вычислить $v=x_{2}{\bmod {n}}$ .

Шаг 7. Если $v=r$ , то вернуть "Принять", иначе "Отклонить"

Доказательство работы алгоритма проверки цифровой подписи

Пусть подпись $(r,s)$ для сообщения $m$ действительно была сгенерирована Алисой, в таком случае, $s=k^{-1}(e+dr){\bmod {n}}$ . Перестановка дает следующее :

k\equiv s^{-1}(e+dr){\bmod {n}}\equiv (s^{-1}e+s^{-1}dr){\bmod {n}}\equiv (we+wdr){\bmod {n}}\equiv (u_{1}+u_{2}d){\bmod {n}}

Таким образом, получаем ${\textstyle X=(x_{2},y_{2})=u_{1}G+u_{2}Q=(u_{1}+u_{2}d)G=kG}$ , поэтому ${\textstyle v=r}$ , что и требовалось доказать.

Пример работы ECDSA

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

1. Используя алгоритм генерации основных параметров , получим следующие значения: $p=114973$ , эллиптическая кривая $E:y^{2}=x^{3}-3x+69424$ , и базовая точка $G=(11570,42257)$ с порядком $n=114467$ .

2. Сгенерируем пару ключей в соответствии с алгоритмом генерации ключевой пары :

Шаг 1. Выбираем $d=86109\in [1,114466]$ .

Шаг 2. Вычисляем координаты точки $Q=dG=(6345,28549)$ .

3. Алгоритмом генерации цифровой подписи подпишем сообщение, заданное в виде текста ${\textstyle m=worldof}$ со значением хэш-функции $e={\mathcal {H}}(m)=1789679805$ .

Шаг 1. Выбираем $k=84430\in [1,114466]$ .

Шаг 2. Вычисляем координаты точки $kG=(x_{1},y_{1})=(31167,10585)$ .

Шаг 3. Вычисляем ${\textstyle r=x_{1}{\bmod {n}}=31167{\bmod {1}}14973=31167}$ .

Шаг 4. Вычисляем ${\textstyle s=k^{-1}(e+dr){\bmod {n}}=84430^{-1}(1789679805+86109\cdot 31167){\bmod {1}}14973=82722}$ .

4. Проверим достоверность подписи $(r,s)$ для сообщения $m$ с помощью алгоритма проверки цифровой подписи .

Шаг 1. Вычисляем $w=s^{-1}{\bmod {n}}=82722^{-1}{\bmod {1}}14973=83035$ .

Шаг 2. Вычисляем $u_{1}=ew{\bmod {n}}=1789679805\cdot 83035{\bmod {1}}14973=71001$ и $u_{2}=rw{\bmod {n}}=31167\cdot 83035{\bmod {1}}14973=81909$ .

Шаг 3. Вычисляем координаты точки $X=u_{1}G+u_{2}Q=(66931,53304)+(88970,41780)=(31167,31627)$ .

Шаг 4. Вычислим $v=x_{2}{\bmod {n}}=31167{\bmod {1}}14973=31167$ .

Шаг 5. Проверяем $v=r=31167$ . Принимаем подпись.

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

ECDSA по сравнению c DSA

Д. Брауном (Daniel R. L. Brown) было доказано, что алгоритм ECDSA не является более безопасным, чем DSA . Им было сформулировано ограничение безопасности для ECDSA, которое привело к следующему заключению: «Если группа эллиптической кривой может быть смоделирована основной группой и её хеш-функция удовлетворяет определённому обоснованному предположению, то ECDSA устойчива к атаке на основе подобранного открытого текста с существующей фальсификацией» .

Математические преимущества

Стойкость алгоритма шифрования основывается на проблеме дискретного логарифма в группе точек эллиптической кривой . В отличие от проблемы простого дискретного логарифма и проблемы факторизации целого числа , не существует субэкспоненциального алгоритма для проблемы дискретного логарифма в группе точек эллиптической кривой. По этой причине «сила на один бит ключа» существенно выше в алгоритме, который использует эллиптические кривые .

Это означает, что в криптографии на эллиптических кривых можно использовать значительно меньшие параметры, чем в других системах с открытыми ключами, таких как RSA и DSA , но с эквивалентным уровнем безопасности. К примеру, битовый размер ключей : 160-битный ключ будет равносилен ключам с 1024-битным модулем в RSA и DSA при сопоставимом уровне безопасности (против известных атак). Преимущества, полученные от меньших размеров параметров (в частности, ключей), включают скорость выполнения алгоритма, эффективное использование энергии, пропускной полосы, памяти . Они особенно важны для приложений на устройствах с ограниченными возможностями, таких как смарт-карты .

Опасения по поводу разработанных алгоритмов

Явной проблемой является отсутствие доверия к некоторым уже разработанным ранее алгоритмам . Например, NIST Special Publication 800-90 , содержащая детерминированный генератор случайных битов на эллиптических кривых Dual_EC_DRBG . В самом стандарте содержится набор констант кривой, появление которых в представленном виде не объяснено, Шумоу и Фергюсон показали, что данные постоянные связаны с некоторым случайным набором чисел, работающим как бэкдор , возможно, для целей АНБ , но этому нет никаких достоверных подтверждений .

Практическая реализация

ECDSA реализован в таких криптографических библиотеках, как OpenSSL , Cryptlib , Crypto++ , реализации протоколов GnuTLS , интерфейсе программирования приложений CryptoAPI . Существует и множество других программных реализаций алгоритма электронной цифровой подписи на эллиптических кривых, большинство из которых в основном сосредоточено на одном приложении, например, быстрой реализации для одного конкретного конечного поля .

Примечания

, с. 221.
↑ , с. 109—110.
, с. 110.
.
, с. 12.
, с. 172.
, с. 173-174.
, Алгоритм генерации основных параметров, с. 174.
, с. 175-178.
, Алгоритм генерации ключевой пары, с. 180.
, Алгоритм проверки открытого ключа, с. 181.
, Алгоритм генерации цифровой подписи, с. 116-117.
, Алгоритм проверки цифровой подписи, с. 117.
, Доказательство работы алгоритма проверки цифровой подписи, с. 117.
, с. 118—119.
.
.
, Предисловие, с. xix.
, Аннотация.
.
.
.

Литература

Liao H. Z., Shen Y. Y. . « » (2006). Дата обращения: 28 сентября 2022. 28 сентября 2022 года.
Hankerson D., Menezes A. J., Vanstone S. . « Springer Science & Business Media» (2006). Дата обращения: 16 ноября 2022.
Lopez J., Dahab R. . «Institute of Computing. State University of Campinas» (2000). Дата обращения: 16 ноября 2022.
Коржев В. . « Открытые системы » (8 августа 2002). Дата обращения: 16 ноября 2008. 31 декабря 2012 года.
Mayer H. . « » (28 июня 2016). Дата обращения: 28 сентября 2022. 20 января 2022 года.
Brown D. . « » (26 февраля 2002). Дата обращения: 27 ноября 2008. 27 февраля 2012 года.

Ссылки

Schneier B. (5 сентября 2013).
Schneier B. (5 сентября 2013).
(1995). — Another Look at Generic Groups. Дата обращения: 27 ноября 2008. 27 февраля 2012 года.
Издательство «Наукa», Главная редакция физико-математической литературы (1974). — Арифметика и книга о многоугольных числах. Дата обращения: 2 декабря 2022.

[_f5207649494a5fa9-1] , с. 221.

[_aa8b2dd3ce27871c-2] , с. 109—110.

[_12951dd583eebd92-3] , с. 110.

[_580f8eb83e032005-4] .

[_7a1e5a612a760f62-5] , с. 12.

[_578ead0f2a631842-6] , с. 172.

[_6b35877ad4798674-7] , с. 173-174.

[_4b607ffe2e0466b9-8] , Алгоритм генерации основных параметров, с. 174.

[_3b80ab8a1fa6090e-9] , с. 175-178.

[_f3690b1eb9fdb6c9-10] , Алгоритм генерации ключевой пары, с. 180.

[_6bcdbfd99ae8c820-11] , Алгоритм проверки открытого ключа, с. 181.

[_ca823258459e6bec-12] , Алгоритм генерации цифровой подписи, с. 116-117.

[_53597676551f4fb3-13] , Алгоритм проверки цифровой подписи, с. 117.

[_772e4df6c4541372-14] , Доказательство работы алгоритма проверки цифровой подписи, с. 117.

[_e5bd58d5fff3d987-15] , с. 118—119.

[_d71b7d3f502bf443-16] .

[_93dd2c4100754073-17] .

[_4d4afc4ab473a256-18] , Предисловие, с. xix.

[_3b0df7c77d580225-19] , Аннотация.

[_0355c06d8752415b-20] .

[_53161055992d8e2c-21] .

[_daebb2965d49dd3b-22] .