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)}$ эллиптической кривой над конечным полем ${\displaystyle \mathbb {F} _{q}}$ называется совокупность следующих величин :

• Порядок конечного поля ${\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 . Помимо этого могут быть и другие ограничения, связанные с соображениями безопасности или реализации. Как правило, основные параметры являются общими для группы сущностей, однако в некоторых приложениях (реализациях), они могут быть специфичными для каждого конкретного пользователя

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

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

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

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

Ввод : Порядок поля ${\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})}$ , порядок кривой можно вычислить при помощи алгоритма . Шаг 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)}$

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

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

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

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

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

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

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

В дальнейшем ${\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}$ :.

Ввод : Основные параметры эллиптической кривой ${\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}$ , то вернуть "Принять", иначе "Отклонить"

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

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

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 устойчива к атаке на основе подобранного открытого текста с существующей фальсификацией» .

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

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

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

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

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

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

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

Примечания

Литература

• 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.