WikiSort.ru - Не сортированное

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

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

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

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

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

Для простоты будем рассматривать эллиптические кривые над полем ${\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}\mod q}$ , где ${\displaystyle r}$ получается из целого числа ${\displaystyle x_{1}}$ между ${\displaystyle 0}$ и ${\displaystyle (p-1)}$ приведением по модулю ${\displaystyle q}$ .

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

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

   Замечание: если ${\displaystyle s=0}$ , то значение ${\displaystyle s^{-1}{\pmod {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\mod q}$ и ${\displaystyle u_{2}=s^{-1}r\mod q}$ ;
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}\mod q}$ ;
5. Принять подпись, тогда и только тогда, когда ${\displaystyle v=r}$ .

Заметим, что, если пользователь Алиса вычислила свою подпись правильно, то ${\displaystyle u_{1}P+u_{2}Q=(u_{1}+xu_{2})P=(s^{-1}\cdot h\mod q+x\cdot s^{-1}\cdot r\mod q)\cdot P=k\cdot P}$ , так как ${\displaystyle k=s^{-1}(h+xr){\pmod {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}}$ , могут быть сгенерированы за несколько часов на рабочих станциях.