ECDSA

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

Особенности

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

Д. Брауном (Daniel R. L. Brown) было доказано, что алгоритм ECDSA не является более безопасным, чем DSA. Им было сформулировано ограничение безопасности для ECDSA, которое привело к следующему заключению:

«Если группа эллиптической кривой может быть смоделирована основной группой и ее хэш-функция удовлетворяет определенному обоснованному предположению, то ECDSA устойчива к chosen-message атаке с существующей фальсификацией.»

Алгоритм ECDSA в 1999 г. был принят, как стандарт ANSI, в 2000 г. — как стандарт IEEE и NIST. Также в 1998 г. алгоритм был принят стандартом ISO. Несмотря на то, что стандарты ЭЦП созданы совсем недавно и находятся на этапе совершенствования, одним наиболее перспективных из них на сегодняшний день является ANSI X9.62 ECDSA от 1999 — DSA для эллиптических кривых.

Выбор параметров

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

Параметры алгоритма

1. Выбор хэш-функции $H(x)$. Для использования алгоритма необходимо, чтобы подписываемое сообщение являлось числом. Хеш-функция должна преобразовать любое сообщение в последовательность битов, которые можно потом преобразовать в число.
2. Выбор большого простого числа $q$ — порядок одной из циклических подгрупп группы точек эллиптической кривой.

   Замечание: Если размерность этого числа в битах меньше размерности в битах значений хэш-функции $H(x)$ то используются только левые биты значения хэш-функции.

3. Простым числом $p$ обозначается характеристика поля координат $F_p$.

Генерирование ключей ECDSA

Для простоты будем рассматривать эллиптические кривые над полем $F_p$, где $F_p$ — конечное простое поле. Причем, если необходимо, конструкцию можно легко адаптировать для эллиптических кривых над другим полем.

Пусть $E$ — эллиптическая кривая, определенная над $F_p$, и $P$ — точка простого порядка $q$ кривой $E(F_p)$. Кривая $E$ и точка $P$ являются системными параметрами. Число $p$ — простое. Каждая пользовательница Алиса конструирует свой ключ посредством следующих действий:

1. Выбирает случайное или псевдослучайное целое число $x$ из интервала $[1,q-1]$.
2. Вычисляет произведение (кратное) $Q$ = $x$·$P$.

Открытым ключом пользовательницы Алисы $A$ является точка $Q$, а закрытым — $x$.

Вместо использования $E$ и $P$ в качестве глобальных системных параметров, можно фиксировать только поле $F_p$ для всех пользователей и позволить каждому пользователю выбирать свою собственную эллиптическую кривую $E$ и точку $P$$\in$ $E(F_p)$. В этом случае определенное уравнение кривой $E$, координаты точки $P$, а также порядок $q$ этой точки $P$ должны быть включены в открытый ключ пользователя. Если поле $F_p$ фиксировано, то аппаратная и программная составляющие могут быть построены так, чтобы оптимизировать вычисления в том поле. В то же время имеется огромное количество вариантов выбора эллиптической кривой над полем $F_p$.

Вычисление цифровой подписи

Для того, чтобы подписать какое-либо сообщение, для которого подсчитано значение $h$ хэш-функции $H$, пользователь $A$ должен сделать следующее:

1. Выбрать случайное целое число $k \in [1, q-1]$.
2. Вычислить $k\cdot P = (x_1, y_1)$ и положить в $r = x_1\mod q$, где $r$ получается из целого числа $x_1$ между $0$ и $(p - 1)$ приведением по модулю $q$.

   Замечание: если $r = 0$, то уравнение подписи $s = k^{-1}(h + x\cdot r)\mod q$ не зависит от секретного ключа $x$, и следовательно, $(r,s)$ не подходит в качестве цифровой подписи. Значит, в случае $r = 0$ необходимо вернуться к шагу 1.

3. Вычислить $k^{-1}\pmod q$ и положить $s = k^{-1}(h + x\cdot r)\mod q$, где h — значение хеш-функции подписываемого сообщения.

   Замечание: если $s = 0$, то значение $s^{-1}\pmod q$, нужное для проверки, не существует. Значит, в случае $s = 0$ необходимо вернуться к шагу 1.

Подписью для сообщения является пара целых чисел $(r, s)$.

Проверка цифровой подписи

Для того, чтобы проверить подпись пользовательницы Алисы $(r, s)$ на сообщение, пользователь Борис $B$ должен сделать следующее:

1. Получить подтвержденную копию открытого ключа $Q$ пользовательницы А;
2. Проверить, что числа $r$ и $s$ являются целыми числами из интервала $[1, q-1]$, и вычислить значение хеш-функции $h$ от сообщения;
3. Вычислить $u_1 = s^{-1}h \mod q$ и $u_2 = s^{-1}r \mod q$;
4. Вычислить $u_1\cdot P + u_2\cdot Q = (x_0, y_0)$, и относительно $x_0$, как целого числа между $0$ и $(p - 1)$, положить $v = x_0 \mod q$;
5. Принять подпись, если и только если $v = r$.

Заметим, что, если пользовательница Алиса вычислила свою подпись правильно, то $u_1P + u_2Q = (u_1 + xu_2)P = (s^{-1}\cdot h\mod q + x\cdot s^{-1}\cdot r\mod q)\cdot P = k\cdot P$, так как $k = s^{-1}(h + xr)\pmod q$, и поэтому $v = r$.

Для подтверждения публичного ключа Q нужно проделать следующее ($O$ здесь обозначает бесконечно удалённую точку):

1. Проверить, что $Q$ не равно $O$ и координаты верны;
2. Проверить, что $Q$ лежит на кривой;
3. Проверить, что $qQ = O$;

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

Для практического применения алгоритма ECDSA налагают ограничения на поля, в которых определены эллиптические кривые. Более того для избежания некоторых известных атак, ограничения накладываются и на уравнения, задающие эллиптические кривые, и на порядок базовых точек. Для простоты в данном разделе будем рассматривать только конечные $F_p$.

Требования к эллиптической кривой

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

Главными параметрами при построении эллиптической кривой являются:

1. размерность поля $p$, где $p$ явлется простым числом;
2. два элемента поля $F_p$ — $a$ и $b$, определенные уравнением эллиптической кривой $E$, где $E$ имеет вид:

   $y^2 = x^3 + ax + b$,

   где $a$, $b$ $\in$ $F_p$, и $4a^3$ + $27b^2$ $\not\equiv$ 0 $\pmod p$.

3. два элемента поля $F_p$ — $x_G$ и $y_G$, которые определяют конечную точку $G = (x_G, y_G)$ — генератор группы $E(F_p)$
4. порядок $q$ точки $G$, где $q > 2^{160}$ и $q$ > 4 $\sqrt{p}$
5. сомножитель $h$ = #$E(F_p)$/$q$, где обозначение #$E(F_p)$ означает порядок группы точек эллиптической кривой $E(F_p)$.

Генерация главных параметров

Один из способом генерирования криптографически надежных параметров заключается в следующем:

1. Выбираем коэффициенты $a$ и $b$ специфическим образом используя в вычислениях случайные/псевдослучайные числа. Пусть $E$ — эллиптическая кривая — $y^2 = x^3 + ax + b$;
2. Вычисляем $N = \#E(F_p)$;
3. Проверяем, что $N$ имеет делитель, который является большим простым числом $q (q > 2^{160}$ и $q > 4 \sqrt{p})$. Если нет, то нужно вернуться на шаг 1.
4. Проверяем, что $q$ не делит ${p^k - 1}$ для каждого $k$, $1 \le k \le 100$. Если нет, то нужно вернуться на шаг 1;
5. Проверяем, что $q \ne p$. Если нет, то нужно вернуть на шаг 1;
6. Берем случайную точку $G' \in E(F_q)$ и положить $G = (N/q)G'$. Повторяем до тех пор пока $G \ne O$.

В 1985 г. Скооф (Schoof) представил алгоритм, работающий за полимиальное время, для подсчета $\#E(F_p)$, число точек эллиптической кривой определенная над полем $F_p$ (p — нечетное простое число). Алгоритм Скоофа является достаточно не эффективным на практике для значений $p$, которые действительно представляют интерес, то есть $p > 2^{160}$. В последние несколько лет было проделано много работы по улучшению и ускорению алгоритма Скоофа, сейчас он называется SEA (Schoof-Elkies-Atkin) алгоритм. С такими улучшениями криптографически пригодные эллиптические кривые, определенные над полями, чьи порядки более, чем $2^{200}$, могут быть сгенерированы за несколько часов на рабочих станциях.

Преимущества ECDSA перед DSA

ECDSA является очень привлекательным алгоритмом для реализации ЭЦП. Самым важным преимуществом ECDSA является возможность его работы на значительно меньших полях $F_p$. Как, в общем, с криптографией эллиптической кривой, предполагается, что битовый размер открытого ключа, который будет необходим для ECDSA, равен двойному размеру секретного ключа в битах. Для сравнения, при уровне безопасности в 80 бит (то есть атакующему необходимо примерно $2^{80}$ версий подписи для нахождения секретного ключа), размер открытого ключа DSA равен, по крайней мере, 1024 бит, когда как открытого ключа ECDSA — 160 бит. С другой стороны размер подписи одинаков и для DSA, и для ECDSA: $4t$ бит, где $t$ — уровень безопасности, измеренный в битах, то есть — примерно 320 бит для уровня безопасности в 80 бит.

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

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

Ссылки

• Neal Koblitz and Alfred Menezes (1995). — Another Look at Generic Groups. Архивировано из первоисточника 27 февраля 2012. Проверено 27 ноября 2008.