Алгоритм обработки одного блока сообщения (шаговая функция хеширования)

A, b, c, d, e, f, g, h

Основой алгоритма является модуль, состоящий из 64 циклических обработок каждого блока M⁽ⁱ⁾:

T₁ = h + Σ₁^{256}(e) + Ch(e, f, g) + K_t^{256} + W_t

T₂ = Σ₀^{256}(a) + Maj(a, b, c)

h = g

g = f

f = e

e = d + T₁

d = c

c = b

b = a

a = T₁ + T₂

где: K_i^{256} – шестьдесят четыре 32-битных константы, каждая из которых является первыми 32-мя битами дробной части кубических корней первых 64 простых чисел.

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

W_t = M_t⁽ⁱ⁾, 0 ≤ t ≤ 15

W_t = σ₁^{256}(W_t-2) + W_t-7 + σ₀^{256}(W_t-15) + W_t-16,

16 ≤ t ≤ 63

i -ое промежуточное значение хэш-кода H^(t) вычисляется следующим образом:

H₀⁽ⁱ⁾ = a + H₀^(i-1)

H₁⁽ⁱ⁾ = b + H₁^(i-1)

H₂⁽ⁱ⁾ = c + H₂^(i-1)

H₃⁽ⁱ⁾ = d + H₃^(i-1)

H₄⁽ⁱ⁾ = e + H₄^(i-1)

H₅⁽ⁱ⁾ = f + H₅^(i-1)

H₆⁽ⁱ⁾ = g + H₆^(i-1)

H₇⁽ⁱ⁾ = h + H₇^(i-1)

Схожим образом вычисляются значения хэш-функций SHA-384 и SHA-512.

Функция хэширования ГОСТ Р 34.11 – 94

Алгоритм ГОСТ 34.11 является отечественным стандартом для хэш-функций. Его структура довольно сильно отличается от структуры алгоритмов SHA-1, 2 или MD5, в основе которых лежит алгоритм MD4.

Длина хэш-кода, создаваемого алгоритмом ГОСТ 3411, равна 256 битам. Алгоритм разбивает сообщение на блоки, длина которых также равна 256 битам. Кроме того, параметром алгоритма является стартовый вектор хэширования Н – произвольное фиксированное значение длиной также 256 бит.

Сообщение обрабатывается блоками по 256 бит справа налево.

Каждый блок сообщения обрабатывается по следующему алгоритму:

1. Генерация четырех ключей длиной 256 бит каждый.

2. Шифрование 64-битных значений промежуточного хэш-кода H на ключах K_i(i = 1, 2, 3, 4) с использованием алгоритма ГОСТ 28147 в режиме простой замены.

3. Перемешивание результата шифрования.

Этап 1. Генерация ключей

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

· промежуточное значение хэш-кода Н длиной 256 бит (на первой итерации – стартовый вектор хеширования;

· текущий обрабатываемый блок сообщения М длиной 256 бит;

· параметры – три значения С₂, С₃ и С₄ длиной 256 бит следующего вида: С₂ и С₄ состоят из одних нулей, а С₃ равно

1⁸ 0⁸ 1¹⁶ 0²⁴ 1¹⁶ 0⁸ (0⁸ 1⁸)² 1⁸ 0⁸ (0⁸ 1⁸)⁴ (1⁸ 0⁸)⁴

где степень обозначает количество повторений 0 или 1 (длина - 256 бит).

Используются две формулы, определяющие перестановку и сдвиг.

Перестановка Р битов определяется следующим образом: каждое 256-битное значение рассматривается как последовательность тридцати двух 8-битных значений. Перестановка Р элементов 256-битной последовательности выполняется по формуле y = φ (x), где x – порядковый номер 8-битного значения в исходной последовательности; y – порядковый номер 8-битного значения в результирующей последовательности.

φ (i +1 +4(k-1)) = 8i +k где i = 0 ÷ 3, k = 1 ÷ 8

Преобразование (сдвиг) А определяется по формуле:

A (x) = (x₁ Å x₂) ║ x₄║ x₃ ║ x₂,

где x_i – соответствующие 64 бита 256 – битного значения x;

║- обозначение конкатенации.

Присваиваются следующие начальные значения: i = 1, U = H, V = M

Вычисляются: W = U Å V, K₁ = Р (W)

Ключи K₂, K₃, K₄ вычисляются последовательно по следующему алгоритму:

U = A(U) Å С_i,

V = A(A(V)),

W = U Å V,

K_i = Р(W)

В результате получили ключи: K₁, K₂, K₃ и K₄.

Этап 2. Шифрующее преобразование

Выполняется шифрование 64-битных элементов текущего значения хэш-кода Н с ключами K₁, K₂, K₃ и K₄ по алгоритму ГОСТ 28147-89 в режиме простой замены. При этом хэш-код Н рассматривается как последовательность 64-битных значений:

H = h₄ || h₃ || h₂ || h₁

s_i = E_Ki [h_i] i = 1, 2, 3, 4

S = s₁ || s₂ || s₃ || s₄ в результате получили последовательность S.

Этап 3. Перемешивающее преобразование

На заключительном этапе обработки очередного блока выполняется перемешивание полученной последовательности. 256-битное значение рассматривается как последовательность шестнадцати 16-битных значений. Сдвиг обозначается Ψ и определяется следующим образом:

η₁₆ || η₁₅ ||... || η₁ – исходное значение

Ψ = η₁ Å η₂ Å η₃ Å η₄ Å η₁₃ Å η₁₆ || η₁₆ ||... || η₂ – результирующее значение; (циклический сдвиг вправо с оперцией XOR над байтами 1, 2, 3, 4, 13, 16 исходного слова).   η₁₆ η₁₅ η₁₄ η₁₃ η₁₂ η₅ η₄ η₃ η₂ η₁

η₁₆ η₁₅ η₁₄ η₁₃ η₁₂ η₄ η₃ η₂ η₁

Рис. 9.10. Функция перемешивающего преобразования (ψ)

Результирующее значение пошаговой функции хэширования определяется следующим образом:

Χ(M_q, H_q+1) =ψ⁶¹ (H_q Å ψ (M_q Å ψ ¹²(S_q)))

где:

H_q– предыдущее значение хэш-кода,

М_q – текущий обрабатываемый блок,

Ψⁱ – i-ая степень преобразования Ψ.

Дата добавления: 2014-01-07