ECDSA

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

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

История

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

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

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

Применение

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

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

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

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

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

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

Для практического применения ECDSA налагают ограничения на поляШаблон:Sfn, в которых определены эллиптические кривые. Для простоты рассмотрим случай реализации алгоритмов, когда ${𝔽}_q$ — простое конечное поле (для других полей — аналогично), тогда наше эллиптическое уравнение принимает вид $y^2=x^3+ax+b$.

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

Для того, чтобы избежать известных атак, основанных на проблеме дискретного логарифма в группе точек эллиптической кривой, необходимо, чтобы число точек эллиптической кривой $E$ делилось на достаточно большое простое число $n$. Стандарт ANSI X9.62 требует $n>2^{160}$. Предлагается следующий алгоритмШаблон:Sfn: Шаблон:Рамка Ввод: Порядок поля $q$, индикатор представления поля $FR$ для ${𝔽}_q$, $L$ - уровень безопасности: $160⩽L⩽[{\log }_{2}q]$ и $2^L⩾4\sqrt{q}$.

Вывод: Основные параметры эллиптической кривой $D=(q,FR,a,b,G,n,h)$. Шаблон:Конец рамки Шаблон:Рамка Шаг 1. Выберите верифицировано случайным образом элементы $a,b\in {𝔽}_q$, удовлетворяющие условию $4a^3+27b^2\equiv ̸0modq$.

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

Шаг 3. Проверьте, что $Nmodn=0$ при большом простом числе $n⩾2^L$. Если нет, тогда перейдите к шагу 1.

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

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

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

Шаг 7. Выберите произвольную точку $G^{\text{'}}\in E({𝔽}_q)$ и задайте $G:=h{G}^{\text{'}}$. Повторяйте, пока $G\ne 𝒪$, где $𝒪$ - бесконечно удалённая точка

Шаг 8. Верните $(q,FR,a,b,G,n,h)$ Шаблон:Конец рамки Алгоритмы верификации случайным образом дают гарантию того, что эллиптическая кривая над конечным полем была сгенерирована абсолютно случайноШаблон:Sfn.

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

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

Вывод: Открытый ключ - $Q$, закрытый ключ - $d$. Шаблон:Конец рамки Шаблон:Рамка Шаг 1. Выберите случайное или псевдослучайное целое число $d\in [1,n-1]$.

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

Шаг 3. Верните $(Q,d)$. Шаблон:Конец рамки Шаблон:Выпадающий список

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

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

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

Вывод: Подпись $(r,s)$. Шаблон:Конец рамки Шаблон:Рамка Шаг 1. Выберите случайное или псевдослучайное целое число $k\in [1,n-1]$.

Шаг 2. Вычислите координаты точки $kG=(x_1,y_1)$.

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

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

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

Шаг 6. Верните $(r,s)$. Шаблон:Конец рамки

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

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

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

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

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

Шаг 4. Вычислите $u_1=ewmodn$ и $u_2=rwmodn$.

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

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

Шаг 7. Если $v=r$, то вернуть "Принять", иначе "Отклонить" Шаблон:Конец рамки Шаблон:Выпадающий список

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

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

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. Алгоритмом генерации цифровой подписи подпишем сообщение, заданное в виде текста $m=worldof$ со значением хэш-функции $e=\mathscr{H}(m)=1789679805$. Шаблон:Рамка Шаг 1. Выбираем $k=84430\in [1,114466]$.

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

Шаг 3. Вычисляем $r=x_{1}modn=31167mod114973=31167$.

Шаг 4. Вычисляем $s=k^{-1}(e+dr)modn=84430^{-1}(1789679805+86109\cdot 31167)mod114973=82722$. Шаблон:Конец рамки 4. Проверим достоверность подписи $(r,s)$ для сообщения $m$ с помощью алгоритма проверки цифровой подписи. Шаблон:Рамка Шаг 1. Вычисляем $w=s^{-1}modn=82722^{-1}mod114973=83035$.

Шаг 2. Вычисляем $u_1=ewmodn=1789679805\cdot 83035mod114973=71001$ и $u_2=rwmodn=31167\cdot 83035mod114973=81909$.

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

Шаг 4. Вычислим $v=x_{2}modn=31167mod114973=31167$.

Шаг 5. Проверяем $v=r=31167$. Принимаем подпись. Шаблон:Конец рамки

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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web

Ссылки

• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web