Система Orphus

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

ГОСТ Р 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

Стрибог


Система Orphus

Комментарии