GOST_R_34.10-2001.tex

\section[Российский стандарт ЭП ГОСТ Р 34.10-2001]{Российский стандарт ЭП \protect\\ ГОСТ Р 34.10-2001}
\selectlanguage{russian}

Российский стандарт цифровой подписи основан на криптосистеме типа Эль-Гамаля\index{криптосистема!Эль-Гамаля}, в которой в качестве группы используется группа точек эллиптической кривой над конечным полем (см. Приложение). Группа должна быть большой с количеством элементов порядка $2^{255}$.

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

$A$ формирует открытый ключ следующим образом.

\begin{enumerate}
    \item Выбирает простое число $p > 2^{255}$.
    \item Записывает уравнение эллиптической кривой
        \[ E: ~ y^2 = x^3 + a x + b \mod p, \]
        которое определяет группу точек эллиптической кривой $\E(\Z_p)$.
        Выбирает группу, задавая либо случайные числа $0 < a, b < p-1$, либо инвариант $J(E)$:
        \[ J(E) = 1728 \frac{4 a^3}{4 a^3 + 27 b^2} \mod p. \]
        Если кривая задается инвариантом $J(E) \in \Z_p$, то он выбирается случайно в интервале $0 < J(E) < 1728$. Для нахождения $a,b$ вычисляется
        \[ K = \frac{J(E)}{1728 - J(E)}, \]
        \[ \begin{array}{l}
            a = 3 K \mod p, \\
            b = 2 K \mod p. \\
        \end{array} \]
    \item Пусть $m$ -- порядок группы точек эллиптической кривой $\E(\Z_p)$. ~Пользователь $A$ подбирает число $n$ и простое число $q$ такие, что
        \[ m = n q, ~ 2^{254} < q < 2^{256}, ~ n \geq 1, \]
        где $q$ -- делитель порядка группы.

        В циклической подгруппе порядка $q$ выбирается точка
        \[ P \in \E(\Z_p): ~ q P \equiv 0. \]
    \item Случайно выбирает число $d$ и вычисляет точку $Q = d P$.
    \item Формирует секретный и открытый ключи:
        \[ \SK = (d), ~ \PK = (p, E, q, P, Q). \]
\end{enumerate}

Теперь сторона $A$ создает свою цифровую подпись $S(M)$ сообщения $M$, выполняя следующие действия.
\begin{enumerate}
    \item Вычисляет число $\alpha = h(M)$, где $h$ -- криптографическая хэш-функция, определенная стандартом ГОСТ Р 34.11-94. В российском стандарте длина $h(M)$ равна 256 бит.
    \item Вычисляет  $e = \alpha \mod q$.
    \item Случайно выбирает число $k$ и вычисляет точку
        \[ C = k P = (x_c, y_c). \]
    \item Вычисляет  $r = x_c \mod q$.
	Если $r = 0$, то выбирает другое $k$.
    \item Вычисляет  $s = k e + r d \mod q$.
    \item Формирует подпись
        \[ S(M) = (r, s). \]
\end{enumerate}
Сторона $A$ передает стороне $B$ сообщение с подписью
    \[ (M, ~ S(M)). \]

Сторона $B$ проверяет подпись $(r,s)$, выполняя процедуру проверки подписи.
\begin{enumerate}
    \item Вычисляет  $\alpha = h(M)$ и $e = \alpha \mod q$.
    \item Вычисляет  $e^{-1} \mod q$.
    \item Проверяет условия $r < q, ~ r < s$. Если эти условия не выполняются, то подпись отвергается. Если условия выполняются, то процедура продолжается.
    \item Вычисляет числа
        \[ \begin{array}{l}
            a = s e^{-1} \mod q, \\
            b = -r e^{-1} \mod q. \\
        \end{array} \]
    \item Вычисляет точку
        \[ \tilde{C} = a P + b Q = (\tilde{x}_c, \tilde{y}_c). \]
        Если подпись верна, должны получить исходную точку $C$.
    \item Проверяет условие $\tilde{x}_{c} \mod q = r$. Если условие выполняется, то подпись принимается, в противном случае --- отвергается.
\end{enumerate}

Рассмотрим вычислительную сложность вскрытия подписи. Предположим, что криптоаналитик ставит своей задачей определение секретного ключа $d$. Как известно,  эта  задача является трудной. Для подтверждения этого можно привести следующий факт. Был поставлен следующий эксперимент: было выбрано число $p = 2^{97},$ и 1200 персональных компьютеров с тактовой частотой процессоров 200 МГц в 16 странах мира работали, чтобы решить эту задачу. Задача была решена за 53 дня круглосуточной работы. Если взять $p = 2^{256}$, то на решение такой задачи при наличии одного компьютера с частотой процессора 2 ГГц потребуется $10^{22}$ лет.