ECDSA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что, если пользователь Алиса вычислила свою подпись правильно, то ${\displaystyle u_{1}P+u_{2}Q=(u_{1}+xu_{2})P=(s^{-1}\cdot h{\bmod {q}}+x\cdot s^{-1}\cdot r{\bmod {q}})\cdot P=k\cdot P}$, так как ${\displaystyle k=s^{-1}(h+xr){\bmod {q}}}$ и, и поэтому ${\displaystyle v=r}$.

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

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

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

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

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

   ${\displaystyle y^{2}=x^{3}+ax+b}$,

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

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

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

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

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