GOST_R_34.11-94.tex

\section{ГОСТ Р 34.11-94}\index{хэш-функция!ГОСТ Р 34.11-94|(}
\selectlanguage{russian}

Представим описание устаревшего российского стандарта хэш-функции ГОСТ Р 34.11-94~\cite{GOST-94}.

Пусть $X$ -- последовательность длины 256 бит. Запишем $X$ тремя способами в виде конкатенации 4, 16 и 32 блоков:
\[ \begin{array}{ll}
    X & = X_4 ~\|~ X_3 ~\|~ X_2 ~\|~ X_1 = \\
    & = ~ \eta_{16} ~\|~ \eta_{15} ~\|~ \dots ~\|~ \eta_2 ~\|~ \eta_1 = \\
    & = ~ \xi_{32} ~\|~ \xi_{31} ~\|~ \dots ~\|~ \xi_2 ~\|~ \xi_1,
\end{array} \]
с длинами 64, 16 и 8 бит соответственно.

Введём три функции:
\[ \begin{array}{ll}
    A(X) & \equiv A(X_4 ~\|~ X_3 ~\|~ X_2 ~\|~ X_1) = \\
        & = \left( X_1 \oplus X_2 \right) ~\|~ X_4 ~\|~ X_3 ~\|~ X_2, \\
    & \\
    \psi(X) & \equiv \psi(\eta_{16} ~\|~ \eta_{15} ~\|~ \dots ~\|~ \eta_2 ~\|~ \eta_1) = \\
        & = \left( \eta_1 \oplus \eta_2 \oplus \dots \oplus \eta_{15} \right) ~\|~
            \eta_{16} ~\|~ \eta_{15} ~\|~ \dots ~\|~ \eta_3 ~\|~ \eta_2, \\
    & \\
    P(X) & \equiv P(\xi_{32} ~\|~ \xi_{31} ~\|~ \dots ~\|~ \xi_2 ~\|~ \xi_1) = \\
        & = \xi_{\varphi(32)} ~\|~ \xi_{\varphi(31)} ~\|~ \dots ~\|~ \xi_{\varphi(2)} ~\|~ \xi_{\varphi(1)},
\end{array} \]
где $\varphi(s)$ -- перестановка байта, $s$ -- номер байта. Функции $A(X)$ и $\psi(X)$ -- регистры сдвига с линейной обратной связью.

Число $s$ однозначно представляется через целые числа $i$ и $k$, а правило перестановки $\varphi(s)$ записывается:
\[ \begin{array}{c}
    s = i + 4 (k - 1) + 1, ~~ 0 \leq i \leq 3, ~ 1 \leq k \leq 8, \\
    \varphi(s) = 8 i + k. \\
\end{array} \]
Приведём пример. Пусть $s = 7$, тогда $i=2$, $k=2$. Находим перестановку $\varphi(7) = 8 \cdot 2 + 2 = 18$. Седьмой байт переместился на 18-е место.

В российском стандарте функция компрессии двух 256-битовых блоков сообщения $M$ и результата хэширования предыдущего блока $H$ имеет вид
\[
    H' = \chi(M, H) = \psi^{61}(H \oplus \psi(M \oplus \psi^{12}(S))),
\]
где $\psi^j(X)$ -- суперпозиция $j$ функций $\psi( \psi( \dots ( \psi( X)) \dots ))$, ~ 256-битовый блок $S$ определяется ниже.

256-битовые блоки $H$ и $S$ представляются конкатенацией четырёх 64-битовых блоков
\[ \begin{array}{l}
    H = h_4 ~\|~ h_3 ~\|~ h_2 ~\|~ h_1, \\
    S = s_4 ~\|~ s_3 ~\|~ s_2 ~\|~ s_1, \\
    s_i = E_{K_i}( h_i), ~ i = 1, 2, 3, 4, \\
\end{array} \]
где $E_{K_i}( h_i)$ -- криптографическое преобразование 64-битового блока $h_i$ стандарта блочного шифрования ГОСТ 28147-89 с помощью ключа шифрования $K_i$.

Вычисление ключей $K_i$ производится через вспомогательные функции:
\[ \begin{array}{c}
    U_1 = H, ~~ V_1 = M, \\
    U_i = A(U_{i-1}) \oplus C_i, ~~ V_i = A(A(V_{i-1})), ~~ i = 2, 3, 4, \\
\end{array} \]
где $C_2, C_3, C_4$ -- 256-битовые блоки:
\[ \begin{array}{c}
    C_2 = C_4 = 0^{256}, \\
    C_3 = 1^8 0^8 1^{16} 0^{24} 1^{16} 0^8 (0^8 1^8)^2 1^8 0^8 (0^8 1^8)^4 (1^8 0^8)^4. \\
\end{array} \]
Окончательно получаем ключи:
\[
    K_i = P(U_i \oplus V_i), ~ i = 1,2,3,4.
\]

%Ключевая хэш-функция определяется в виде $h_{K} (X)=h(KXK)$, где $h(X)$ -- некоторая стандартная хэш-функция, $K$ -- секретный ключ.
\index{хэш-функция!ГОСТ Р 34.11-94|)}