ГОСТ Р 34.11-94

Вспомогательные функции

Введем три функции для $X$ длины 256 бит:

Регистр сдвига с линейной обратной связью:

$A(X)\equiv A(X_1||X_2||X_3||X_4)=(X_1\oplus X_2)||X_4||X_3||X_2$ ,

Регистр сдвига с линейной обратной связью:

$\psi(X)\equiv \psi(\eta_{16}||\eta_{15}||\ldots||\eta_{2}||\eta_{1})=(\eta_1\oplus\eta_2\oplus\ldots\oplus\eta_{15})||\eta_{16}||\eta_{15}||\ldots||\eta_{2}$ ,

Функция перестановки:

$P(X)\equiv P(\xi_{32}||\xi_{31}||\ldots ||\xi_{2}||\xi_{1})=\xi_{\varphi(32)}||\xi_{\varphi(31)}||\ldots||\xi_{\varphi(2)}||\xi_{\varphi(1)}$ ,

где $\varphi(s)$ - перестановка байта $s$ - номер байта.

Число $s$ уникально представляется через целые числа $i,k$ и правило перестановки $\varphi(s)$ записывается:

$s=i+4(k-1)+1,~0\leqslant i\leqslant 3,~1\leqslant k\leqslant 8$ ,

$\varphi(s)=8i+k$ .

Функция компрессии

Функция компрессии двух 256-битовых блоков сообщения $M_{i}$ и результата хэширования предыдущего блока $H_{i-1}$ имеет вид:

$H_{i}=\chi(M_{i},H_{i-1})=\varphi^{61}(H_{i-1}\oplus\varphi(M_{i}\oplus\varphi^{12}(S(H_{i-1}))))$

Вычисление $S$ :

$H_{i-1}=h_4||h_3||h_2||h_1$ ,

$S=E_{K_4}(h_4)||E_{K_3}(h_3)||E_{K_2}(h_2)||E_{K_1}(h_1)$ .

Вычисления ключей $K_1,K_2,K_3$ и $K_4$ производятся через вспомогательные функции:

$U_1=H$ ,

$V_1=M$ ,

$U_i=A(U_{i-1})\oplus C_i,~~i=2,3,4$ ,

$V_i=A(A(V_{i-1})),~~i=2,3,4$ .

$K_i=P(U_i\oplus V_i),~~i=1,2,3,4.$

где

$C_2=C_4=0^{256}$

$C_3=1^80^81^{16}0^{24}1^{16}0^{8}(0^81^8)^21^80^8(0^81^8)^4(1^80^8)^4$ .

SHA

Сообщение дополняется, чтобы его длина была кратной 512 битам.

Используется дополнение: сначала добавляется 1, а затем нули так, чтобы длина полученного сообщения была на 64 бита меньше числа, кратного 512, а затем добавляется 64-битовое представление длины оригинального сообщения.

Инициализируется пять 32-битовых переменных

$A=0x67452301$

$B=0xefcdab89$

$C=0x98badcfe$

$D=0x10325476$

$E=0xc3d2e1f0$

Затем начинается главный цикл алгоритма.
Он обрабатывает сообщение 512-битовыми блоками и продолжается, пока не исчерпаются все блоки сообщения.

Сначала пять переменных копируются в другие переменные:

a=A, b=B, c=C, d=D, e=E;

Главный цикл состоит их четырех этапов по 20 операций в каждом. Каждая операция представляет собой нелинейную функцию над тремя из $a$ , $b$ , $c$ , $d$ и $e$ , а затем выполняется сдвиг и сложение. В SHA используется следующий набор нелинейных функций:

$f_t(X,Y,Z)=(X\and Y)\lor((\lnot X)\and Z),~~t=0\ldots 19$

$f_t(X,Y,Z)=X\oplus Y\oplus Z,~~t=20\ldots 39$

$f_t(X,Y,Z)=(X\and Y)\lor(X\and Z)\lor(Y\and Z),~~~t=40\ldots 59$

$f_t(X,Y,Z)=X\oplus Y\oplus Z,~~t=60\ldots 79$

в алгоритме используются следующие четыре константы:

$K_t=0x5a827999,~~t=0\ldots 19$

$K_t=0x6ed9eba1,~~t=20\ldots 39$

$K_t=0x8f1bbcdc,~~t=40\ldots 59$

$K_t=0xca62c1d6,~~t=60\ldots 79$

Блок сообщения превращается из 16 32-битовых слов ( $M_0$ по $M_{15}$ ) в 80 32-битовых слов ( $W_0$ по $W_{79}$ ) с помощью следующего алгоритма:

$W_t=M_t,~~t=0\ldots 15$

$W_t=(W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16}\oplus) <<< 1,~~t=16\ldots 79$

Если $t$ - это номер операции ( $1\ldots 80$ ), $W_t$ представляет собой $t$ -ый подблок расширенного сообщения, $a<<< s$ - это циклический сдвиг влево на $s$ битов, то главный цикл выглядит следующим образом:

for t=0 to 79
TEMP=(a<<<5)+f_t(b,c,d)+e+W[t]+K[t]
e=d
d=c
c=b<<<30
b=a
a=TEMP

После всего этого $a,b,c,d$ и $e$ добавляются к $A,B,C,D$ и $E$ , соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение $A,B,C,D$ и $E$ .

A=A+a;B=B+b;C=C+c;D=D+d;E=E+e;

Шнайер 329

Сказать "Спасибо"

Свойства, принципы построения криптографически стойких хэш-функций

ГОСТ Р 34.11-94

Вспомогательные функции

Функция компрессии

SHA

Стрибог

Комментарии