N-Hash - Алгоритм

Интернет магазин китайских планшетных компьютеров

Компьютеры - N-Hash - Алгоритм

27 апреля 2011

Оглавление:
1. N-Hash
2. Использование
3. Особенности N-Hash
4. Цели N-Hash
5. Алгоритм
6. Безопасность хеш-функций
7. Итоги

Алгоритм N-Hash основан на циклическом повторении операций. На входе имеется хеш-код h₀ и он может быть произвольным, на выходе получается хеш-код h сообщения M, которое необходимо хешировать. При этом размер выходящего хеш-кода фиксирован и равен 128 бит, тогда как размер M произволен.

Основные обозначения

M — сообщение, которое необходимо хешировать;
M_i — блок сообщения длиной 128 бит. Для того, чтобы хешировать сообщение M необходимо поделить его на блоки M_i;
h_i — хеш-код i-ого шага;
ν = 1010...1010 — константа, длиной 128 бит;
| | — конкатенация;
V_j = δ | | A_j1 | | δ | | A_j2 | | δ | | A_j3 | | δ | | A_j4 | | , где A_jk = 4 * + k, где k=1, 2, 3, 4; δ = 00..00, длиной 24 бит;
EXG — функция, которая меняет местами старшие и младшие разряды;
PS — преобразующая функция;

Описание алгоритма

На схеме справа представлены схематические обозначения операций, которые присутствуют на нижеследующих схемах.

Покоординатное суммирование означает сложение по модулю 2;
Если x поступает на вход функции f, то на выходе получается f.

Один цикл работы N-Hash

один цикл работы N-Hash

Ниже представлен один цикл работы алгоритма N-Hash.

На вход функции g подается хеш-код-ого шага h_{i − 1} и i-ый блок сообщения M_i. При этом h₀ выбирается произвольно: например, он может быть нулевым. А также h_{i − 1} подается на выход на операцию сложения по модулю 2, то есть результат будет выглядеть так: $h_{i-1}\oplus$ .
Из схемы видно, что M_i подается не только на XOR, но и на выход на операцию сложения по модулю 2. То есть теперь в соответствие с первым пунктом результат выглядит таким образом: $h_{i-1}\oplus M_{i}$ .

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

Функция EXG меняет местами старшие и младшие разряды h_{i − 1} и прибавляет к результату ν, после чего результат складывает по модулю 2 с M_i.
Как видно из схемы, результат подается последовательно на входы j преобразующих функций, вторым аргументом которых является сумма $h_{i-1}\oplus V_{j}$ , где j=1, … , 8.
В результате получается хеш-код i-ого шага h_i:

$h_{i}=M_{i}\oplus g\oplus h_{i-1}$ .

Преобразующая функция

Схема преобразующей функции. Каждый из аргументов разбивается на 4 блока по 32 бит каждый.

Возникает вопрос, как действует преобразующая функция PS.

Рассмотрим верхнюю часть схемы до перекрестья.

Исходное сообщение $~X$ разбивается на блоки по 128 / 4 = 32 бита.

Будем считать промежуточными выходами входы в нижнюю часть схемы. $~X_{1}$ и $~X_{2}$ подаются на промежуточные выходы, а на два других выхода подаются операции $f\oplus X_{2}\oplus X_{4}$ и $f\oplus X_{1}\oplus X_{3}$ . Теперь можно результаты на промежуточных выходах переобозначить и через них, аналогично верхней части, найти результаты на выходе нижней части, то есть и всей схемы в целом.

Сделав все необходимые вычисления, получим, что при подаче на вход ${X=X_{1}\parallel X_{2}\parallel X_{3}\parallel X_{4}}$ сообщение на выходе ${Y=Y_{1}\parallel Y_{2}\parallel Y_{3}\parallel Y_{4}}$ можно представить как конкатенацию сообщений

${Y_{3}=f\oplus X_{1}\oplus X_{3}}$ ;
${Y_{4}=X_{2}\oplus X_{4}\oplus f}$ ;
${Y_{1}=f\oplus X_{1}\oplus Y_{3}}$ ;
${Y_{2}=X_{2}\oplus Y_{4}\oplus f}$ .

Поиск функции f

Схема поиска функции f

Так как функция f работает с аргументами, длина которых составляет 32 бит, то из схемы поиска функции f имеем:

Величину $x\oplus P$ разбиваем на части по 8 бит.
Запишем эти части как , i=1,…,4 и введет новые обозначения:
- ${Z_{1}=x_{1}\oplus P_{1}}$ ;
- ${Z_{2}=x_{2}\oplus P_{2}}$ ;
- ${Z_{3}=x_{3}\oplus P_{3}}$ ;
- ${Z_{4}=x_{4}\oplus P_{4}}$ ;