Система Orphus

Цифровые подписи, требования к ним и характеристики на примере стандарта ГОСТ Р 34.10-2001

Российский стандарт ЭЦП основан на криптосистеме типа Эль-Гамаль.

В качестве группы используется группа точек на эллиптической кривой над конечным полем(группа должна быть порядка 2^{255} элементов).

Пусть имеются две стороны A и B и между ними канал связи. Пусть сторона A желает передать сообщение M стороне B и подписать его. Сторона B должна проверить правильность подписки, то есть аутентифицировать сторону A.

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

  • Выбрать простое число p>2^{255},
  • Записать уравнение эллиптической кривой
E:~y^2=x^3+ax+b~\bmod~p,

которое определяет группу точек эллиптической кривой E(\mathbb{Z}).

Для того, чтобы выбрать группу, Alice задает два случайныx числа 0<a,b<p-1, либо эллиптический инвариант J(E) в интервале 0<J(E)<1728:

J(E)=1728\frac{4a^3}{4a^3+27b^2}~\bmod~p,

и для нахождения a,b вычисляется

K=\frac{J(E)}{1728-J(E)},~~a=3K~\bmod~p,~~b=2K~\bmod~p.
  • подобрать числа натуральное n и простое q такие, что
m=nq,~2^{254}<q<2^{256},~n\geqslant 1,

где m - порядок группы точек эллиптической кривой E(\mathbb{Z}_p), а q - делитель этого порядка.

  • Выбрать точку в циклической подгруппе порядка q - точку P.
P\in\mathbb{E}(\mathbb{Z}_p): qP\equiv 0.
  • Случайно выбирать число d и вычислить точку
Q=dP,
  • Сформировать секретный ключ: SK=\{d\}
  • Сформировать открытый ключ: PK=\{E,p,q,P,Q\}

Процесс подписи сообщения

  • Вычисляет число e=h(M)~\bmod~q.
  • Случайно выбирает число r и вычисляет точку
    C=rP=(x_c,y_c),
    если такая точка не существует, то выбирает другое число r.
  • Вычисляет число a=x_c~\bmod~q.
  • Вычисляет число b=re+ad~\bmod~q.
  • Формирует подпись
S(M)=\{a,b\}.

Процесс проверки подписи

  • Проверить условия
    a<q,~a<b.
    Если эти условия не выполняются, то подпись отвергается. Если условия выполняются, то процедура продолжается.
  • Вычислить число
e=h(M)~\bmod~q.
  • Вычислить числа
b'=be^{-1}~\bmod~q,
a'=-ae^{-1}~\bmod~q.
  • Вычислить точку
\tilde{C}=b'P+a'Q=(\tilde{x}_c,\tilde{y}_c).

Если подпись верна, должна получиться исходная точка C.

  • Проверяет условие \tilde{x}_c~\bmod ~q=a. Если условие выполняется, то подпись принимается, в противном случае - отвергается.

стр 110


Система Orphus

Комментарии