ECDSA

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

История

Эллиптические кривые, в качестве математического понятия, изучаются уже достаточно давно, существует множество научных работ на эту тему. Однако, несмотря на все исследования, их применение для реальных задач, в частности для криптографии, было неизвестно до конца 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) [math]\displaystyle{ D = (q, FR, a, b, G, n, h) }[/math] эллиптической кривой над конечным полем [math]\displaystyle{ \mathbb{F}_q }[/math] называется совокупность следующих величин:

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

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

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

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

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

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

Ввод: Порядок поля [math]\displaystyle{ q }[/math], индикатор представления поля [math]\displaystyle{ FR }[/math] для [math]\displaystyle{ \mathbb{F}_q }[/math], [math]\displaystyle{ L }[/math] - уровень безопасности: [math]\displaystyle{ 160 \leqslant L \leqslant [\log_2q] }[/math] и [math]\displaystyle{ 2^L \geqslant 4 \sqrt q }[/math]. Вывод: Основные параметры эллиптической кривой [math]\displaystyle{ D = (q, FR, a, b, G, n, h) }[/math].

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

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

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

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

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

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

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

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

Ввод: Основные параметры эллиптической кривой [math]\displaystyle{ D }[/math], открытый ключ - [math]\displaystyle{ Q }[/math]. Вывод: Решение о принятии или отклонении достоверности открытого ключа [math]\displaystyle{ Q }[/math].

Шаг 1. Проверьте, что [math]\displaystyle{ Q \neq \mathcal{O} }[/math]. Шаг 2. Проверьте, что [math]\displaystyle{ (x_G, y_G) }[/math] являются правильно представленными элементами в [math]\displaystyle{ \mathbb{F}_q }[/math], т.е. целыми числами, принадлежащими [math]\displaystyle{ [1, q-1] }[/math]. Шаг 3. Проверьте, что [math]\displaystyle{ Q }[/math] удовлетворяет уравнению эллиптической кривой, определяемому элементами поля [math]\displaystyle{ a, b }[/math]. Шаг 4. Проверьте, что [math]\displaystyle{ nQ = \mathcal{O} }[/math]. Шаг 5. Если какая-либо проверка не прошла, то вернуть "Отклонить", иначе "Принять".

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

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

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

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

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

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

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

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

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

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

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

[math]\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_2d) \bmod n }[/math]

Таким образом, получаем [math]\displaystyle{ X = (x_2, y_2) = u_1G+u_2Q = (u_1+u_2d)G = kG }[/math], поэтому [math]\displaystyle{ v = r }[/math], что и требовалось доказать.

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

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

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

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

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

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

Шаг 1. Выбираем [math]\displaystyle{ k = 84430 \in [1, 114466] }[/math]. Шаг 2. Вычисляем координаты точки [math]\displaystyle{ kG = (x_1, y_1) = (11705, 10585) }[/math]. Шаг 3. Вычисляем [math]\displaystyle{ r = x_1 \bmod n = 11705 \bmod 114973 = 31167 }[/math]. Шаг 4. Вычисляем [math]\displaystyle{ s = k^{-1}(e + dr) \bmod n = 84430^{-1} (1789679805 + 86109 \cdot 31167) \bmod 114973 = 82722 }[/math].

4. Проверим достоверность подписи [math]\displaystyle{ (r, s) }[/math] для сообщения [math]\displaystyle{ m }[/math] с помощью алгоритма проверки цифровой подписи.

Шаг 1. Вычисляем [math]\displaystyle{ w = s^{-1} \bmod n = 82722^{-1} \bmod 114973 = 83035 }[/math]. Шаг 2. Вычисляем [math]\displaystyle{ u_1 = ew \bmod n = 1789679805 \cdot 83035 \bmod 114973 = 71001 }[/math] и [math]\displaystyle{ u_2 = rw \bmod n = 31167 \cdot 83035 \bmod 114973 = 81909 }[/math]. Шаг 3. Вычисляем координаты точки [math]\displaystyle{ X = u_1G + u_2Q = (66931,53304) + (88970,41780) = (31167,31627) }[/math]. Шаг 4. Вычислим [math]\displaystyle{ v = x_2 \bmod n = 31167 \bmod 114973 = 31167 }[/math]. Шаг 5. Проверяем [math]\displaystyle{ v = r = 31167 }[/math]. Принимаем подпись.

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

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 для одного конкретного конечного поля.

Литература

• 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. Архивировано 22 января 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 года.