ECDSA

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

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

История

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

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

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

Применение

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

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

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

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

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

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

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

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

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

Ввод: Порядок поля ${\displaystyle q}$, индикатор представления поля ${\displaystyle FR}$ для ${\textstyle \mathbb {F} _{q}}$, ${\displaystyle 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}}$, удовлетворяющие условию ${\displaystyle 4a^{3}+27b^{2}\not \equiv 0{\bmod {q}}}$. Шаг 2. ${\textstyle N:=\#E(\mathbb {F} _{q})}$, порядок кривой можно вычислить при помощи алгоритма SEA. Шаг 3. Проверьте, что ${\textstyle N{\bmod {n}}=0}$ при большом простом числе ${\displaystyle n\geqslant 2^{L}}$. Если нет, тогда перейдите к шагу 1. Шаг 4. Проверьте, что ${\displaystyle q^{k}-1{\bmod {n}}=0}$ ${\displaystyle \forall k\in [1,20]}$. Если нет, тогда перейдите к шагу 1. Шаг 5. Проверьте, что ${\displaystyle n\neq q}$. Если нет, тогда перейдите к шагу 1. Шаг 6. ${\displaystyle h:=N/n}$. Шаг 7. Выберите произвольную точку ${\textstyle G^{'}\in E(\mathbb {F} _{q})}$ и задайте ${\textstyle G:=hG^{'}}$. Повторяйте, пока ${\textstyle G\neq {\mathcal {O}}}$, где ${\displaystyle {\mathcal {O}}}$ - бесконечно удалённая точка Шаг 8. Верните ${\textstyle (q,FR,a,b,G,n,h)}$

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

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

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

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

Шаг 1. Выберите случайное или псевдослучайное целое число ${\displaystyle d\in [1,n-1]}$. Шаг 2. Вычислите координаты точки на эллиптической кривой ${\displaystyle Q=dG}$. Шаг 3. Верните ${\displaystyle (Q,d)}$.

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

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

Ввод: Основные параметры эллиптической кривой ${\textstyle D}$, открытый ключ - ${\displaystyle Q}$. Вывод: Решение о принятии или отклонении достоверности открытого ключа ${\displaystyle 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. Если какая-либо проверка не прошла, то вернуть "Отклонить", иначе "Принять".

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

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

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

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

Шаг 1. Выберите случайное или псевдослучайное целое число ${\displaystyle k\in [1,n-1]}$. Шаг 2. Вычислите координаты точки ${\displaystyle kG=(x_{1},y_{1})}$. Шаг 3. Вычислите ${\displaystyle r=x_{1}{\bmod {n}}}$. Если ${\displaystyle r=0}$, тогда перейдите к шагу 1. Шаг 4. Вычислите ${\displaystyle e={\mathcal {H}}(m)}$. Шаг 5. Вычислите ${\displaystyle s=k^{-1}(e+dr){\bmod {n}}}$. Если ${\displaystyle s=0}$, тогда перейдите к шагу 1. Шаг 6. Верните ${\displaystyle (r,s)}$.

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

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

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

Шаг 1. Проверьте, что ${\displaystyle r,s}$ - целые числа, принадлежащие ${\displaystyle [1,n-1]}$. Если какая-либо проверка не удалась, то вернуть "Отклонить". Шаг 2. Вычислите ${\displaystyle e={\mathcal {H}}(m)}$. Шаг 3. Вычислите ${\displaystyle w=s^{-1}{\bmod {n}}}$. Шаг 4. Вычислите ${\displaystyle u_{1}=ew{\bmod {n}}}$ и ${\displaystyle u_{2}=rw{\bmod {n}}}$. Шаг 5. Вычислите координаты точки ${\displaystyle X=(x_{2},y_{2})=u_{1}G+u_{2}Q}$. Шаг 6. Если ${\displaystyle X={\mathcal {O}}}$, то вернуть "Отклонить". Иначе вычислить ${\displaystyle v=x_{2}{\bmod {n}}}$. Шаг 7. Если ${\displaystyle v=r}$, то вернуть "Принять", иначе "Отклонить"

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

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

$${\displaystyle 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

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

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

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

Шаг 1. Выбираем ${\displaystyle d=86109\in [1,114466]}$. Шаг 2. Вычисляем координаты точки ${\displaystyle Q=dG=(6345,28549)}$.

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

Шаг 1. Выбираем ${\displaystyle k=84430\in [1,114466]}$. Шаг 2. Вычисляем координаты точки ${\displaystyle 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. Проверим достоверность подписи ${\displaystyle (r,s)}$ для сообщения ${\displaystyle m}$ с помощью алгоритма проверки цифровой подписи.

Шаг 1. Вычисляем ${\displaystyle w=s^{-1}{\bmod {n}}=82722^{-1}{\bmod {1}}14973=83035}$. Шаг 2. Вычисляем ${\displaystyle u_{1}=ew{\bmod {n}}=1789679805\cdot 83035{\bmod {1}}14973=71001}$ и ${\displaystyle u_{2}=rw{\bmod {n}}=31167\cdot 83035{\bmod {1}}14973=81909}$. Шаг 3. Вычисляем координаты точки ${\displaystyle X=u_{1}G+u_{2}Q=(66931,53304)+(88970,41780)=(31167,31627)}$. Шаг 4. Вычислим ${\displaystyle v=x_{2}{\bmod {n}}=31167{\bmod {1}}14973=31167}$. Шаг 5. Проверяем ${\displaystyle v=r=31167}$. Принимаем подпись.

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

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

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

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

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

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

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

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

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

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

Примечания

1. Diophantus Arithmetic, с. 221.
2. Liao H. Z., Shen Y. Y, с. 109—110.
3. Liao H. Z., Shen Y. Y, с. 110.
4. Mayer H.
5. Lopez J., Dahab R, с. 12.
6. Hankerson et al, с. 172.
7. Hankerson et al, с. 173-174.
8. Hankerson et al, Алгоритм генерации основных параметров, с. 174.
9. Hankerson et al, с. 175-178.
10. Hankerson et al, Алгоритм генерации ключевой пары, с. 180.
11. Hankerson et al, Алгоритм проверки открытого ключа, с. 181.
12. Liao H. Z., Shen Y. Y, Алгоритм генерации цифровой подписи, с. 116-117.
13. Liao H. Z., Shen Y. Y, Алгоритм проверки цифровой подписи, с. 117.
14. Liao H. Z., Shen Y. Y, Доказательство работы алгоритма проверки цифровой подписи, с. 117.
15. Liao H. Z., Shen Y. Y, с. 118—119.
16. Brown D.
17. Коржев В.
18. Hankerson et al, Предисловие, с. xix.
19. Lopez J., Dahab R, Аннотация.
20. Schneier B. The NSA Is Breaking Most Encryption on the Internet.
21. Schneier B. The Strange Story of Dual_EC_DRBG.
22. Lopez J., Dahab R.

Литература

• Liao H. Z., Shen Y. Y. On the Elliptic Curve Digital Signature Algorithm  (неопр.). «Tunghai Science» (2006). Дата обращения: 28 сентября 2022. Архивировано 28 сентября 2022 года.
• Hankerson D., Menezes A. J., Vanstone S. Guide to elliptic curve cryptography  (неопр.). «Springer Science & Business Media» (2006). Дата обращения: 16 ноября 2022.
• Lopez J., Dahab R. An overview of elliptic curve cryptography  (неопр.). «Institute of Computing. State University of Campinas» (2000). Дата обращения: 16 ноября 2022.
• Коржев В. Цифровая подпись. Эллиптические кривые  (неопр.). «Открытые системы» (8 августа 2002). Дата обращения: 16 ноября 2008. Архивировано 31 декабря 2012 года.
• Mayer H. ECDSA security in bitcoin and ethereum: a research survey  (неопр.). «CoinFaabrik» (28 июня 2016). Дата обращения: 28 сентября 2022. Архивировано 20 января 2022 года.
• Brown D. Generic groups, collision resistance, and ECDSA  (неопр.). «Codes and Cryptography» (26 февраля 2002). Дата обращения: 27 ноября 2008. Архивировано 27 февраля 2012 года.

Ссылки

• Schneier B. The NSA Is Breaking Most Encryption on the Internet  (неопр.) (5 сентября 2013).
• Schneier B. The Strange Story of Dual_EC_DRBG  (неопр.) (5 сентября 2013).
• Neal Koblitz and Alfred Menezes  (неопр.) (1995). — Another Look at Generic Groups. Дата обращения: 27 ноября 2008. Архивировано 27 февраля 2012 года.
• Александрийский Д.  (неопр.) Издательство «Наукa», Главная редакция физико-математической литературы (1974). — Арифметика и книга о многоугольных числах. Дата обращения: 2 декабря 2022.