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


Компьютеры - HAVAL

16 июня 2011
Хавал дарго: лучшее предложение на рынке tts.haval.ru.

Оглавление:
1. HAVAL
2. HAVAL — хеши
3. Криптоанализ



однонаправленная хеш-функция, разработанная Yuliang Zheng  , Josef Pieprzyk  и Jennifer Seberry  в 1992 году. Для произвольного входного сообщения функция генерирует хеш-значение, называемое дайджестом сообщения, которое может иметь длину 128, 160, 192, 224 или 256 бит. Количество итераций — переменное, от 3 до 5. Количество раундов на каждой итерации — 32. Является модификацией MD5.

Алгоритм

Определим булевы функции, которые используются для выполнения побитовых операций над словами.
1-я итерация F_1=x_1 x_4\oplus x_2 x_5\oplus x_3 x_6\oplus x_0 x_1\oplus x_0
2-я итерация F_2=x_1 x_2 x_3\oplus x_2 x_4 x_5\oplus x_1 x_2\oplus x_1 x_4\oplus x_2 x_6 \oplus x_3 x_5\oplus x_4 x_5\oplus x_0 x_2\oplus x_0
3-я итерация F_3=x_1 x_2 x_3\oplus x_1 x_4\oplus x_2 x_5\oplus x_3 x_6\oplus x_0 x_3\oplus x_0
4-я итерация F_4=x_1 x_2 x_3\oplus x_2 x_4 x_5\oplus x_3 x_4 x_6\oplus x_1 x_4\oplus x_2 x_6 \oplus x_3 x_4\oplus x_3 x_5\oplus x_3 x_6\oplus x_4 x_5 \oplus x_4 x_6\oplus x_0 x_4\oplus x_0
5-я итерация F_5=x_1 x_4\oplus x_2 x_5\oplus x_3 x_6\oplus x_0 x_1 x_2 x_3\oplus x_0 x_5\oplus x_0
На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Этот поток делится на блоки, каждый длиной в 1024 бита. Ниже приведены 3 шага алгоритма.


Шаг 1. Расширение сообщения

Сначала сообщение расширяется так, чтобы его длина в битах стала равной 944 по модулю 1024. Для этого в конец сообщения записывается единичный бит, а затем необходимое число нулевых бит. В оставшиеся 80 бит дописывают 64-битное представление количества бит в сообщении до выравнивания, 10-битное представление длины дайджеста сообщения,3-битное представление числа итераций и 3-битное представление версии HAVAL.


Шаг 2. Обработка сообщения блоками по 1024 бит

Запишем расширенное сообщение в виде: B_{n-1} B_{n-2} \ldots B_0, где ~B_{i} — 1024-битный блок и n — количество блоков в расширенном сообщении.
Далее, для i от 0 до n-1 проводим следующее вычисление:
~D_{i+1} = H , где H — функция сжатия, описанная ниже, и ~D_0 — 256-битная константа.

Функция сжатия H

Функция сжатия H

H обрабатывает блок сообщения в течение 3, 4 или 5 итераций. Обозначим функции сжатия, использующиеся в итерациях, через H1,H2,H3,H4 и H5. Пусть ~D_{in} — некоторая 256-битная константа, а ~D_{out} — 256-битный выход функции H. Тогда H может быть описана следующим образом:

~E_0 = D_{in};
~E_1 = H_1;
~E_2 = H_2;
~E_3 = H_3;
~E_4 = H_4;\qquad \mbox{if PASS=4, 5}
~E_5 = H_5;\qquad \mbox{if PASS=5}
D_{out} = \begin{cases} E_3 \boxplus E_0, & \mbox{if PASS=3} \\ E_4 \boxplus E_0, & \mbox{if PASS=4} \\ E_5 \boxplus E_0, & \mbox{if PASS=5} \end{cases}


Обозначим номер итерации через j. Итерации под номером j соответствует функция сжатия Hj. На вход каждой функции Hjподаётся ~B и ~E_{j-1}, где ~B — это 1024-битный блок сообщения, состоящий из 32 слов ~W_{31}W_{30} \dots W_0, a ~E_{j-1} состоит из 8 слов ~E_{j-1,7}E_{j-1,6} \dots E_{j-1,0}. Тогда Hj может быть записана следующим образом:

1. Пусть T_{0,i} = E_{j-1,i} , 0\leqslant i\leqslant 7
2. Повторяем следующие действия для i от 0 до 31:
P = \begin{cases} F_j \circ \phi_{3,j}, & \mbox{if PASS=3} \\ F_j \circ \phi_{4,j}, & \mbox{if PASS=4} \\ F_j \circ \phi_{5,j}, & \mbox{if PASS=5} \end{cases}
R =\boxplus\boxplus W_{ord_j} \boxplus K_{j,i}, где ~K_{j,i} — 32-битные константы
~T_{i+1,7} = T_{i,6} ;\ T_{i+1,6} = T_{i,5} ;\ T_{i+1,5} = T_{i,4} ;\ T_{i+1,4} = T_{i,3};
~T_{i+1,3} = T_{i,2} ;\ T_{i+1,2} = T_{i,1} ;\ T_{i+1,1} = T_{i,0} ;\ T_{i+1,0} = R.
3. Пусть E_{j,i} = T_{32,i} , 0\leqslant i\leqslant 7   и ~E_j = E_{j,7}E_{j,6} \dots E_{j,0} является 256-битным выходом Hj.

Обозначения: ~f \circ g — композиция двух функций,

~\boxplus — сложение по модулю 2,
~\phi_{3,j}, \phi_{4,j}, \phi_{5,j} — перестановки, описанные в Таблице 2.

Замечания: на 1-ой итерации константы не используются.

В отличие от итерации 1, во 2-ой и в последующих итерациях ~B обрабатывается не в пословном порядке, а в порядке, определённом Таблицей 1.

Таблица 1. Порядок обработки слов
ord1   0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
ord2  5 14 26 18 11 28 7 16 0 23 20 22 1 10 4 8 30 3 21 9 17 24 29 6 19 12 15 13 2 25 31 27
ord3  19 9 4 20 28 17 8 22 29 14 25 12 24 30 16 26 31 15 7 3 1 0 18 27 13 6 21 10 23 11 5 2
ord4  24 4 0 14 2 7 28 23 26 6 30 20 18 25 19 3 22 11 31 21 8 27 12 9 1 29 5 15 17 10 16 13
ord5  27 3 21 26 17 11 20 29 19 0 12 7 13 8 31 10 5 9 14 30 18 6 28 24 2 23 16 22 4 1 25 15


Таблица 2. Перестановки
~x_6

\downarrow

 ~x_5

\downarrow

 ~x_4

\downarrow

 ~x_3

\downarrow

 ~x_2

\downarrow

 ~x_1

\downarrow

 ~x_0

\downarrow

~\phi_{3,1}

 ~x_1 ~x_0 ~x_3 ~x_5 ~x_6 ~x_2 ~x_4

~\phi_{3,2}

 ~x_4 ~x_2 ~x_1 ~x_0 ~x_5 ~x_3 ~x_6

~\phi_{3,3}

 ~x_6 ~x_1 ~x_2 ~x_3 ~x_4 ~x_5 ~x_0

~\phi_{4,1}

 ~x_2 ~x_6 ~x_1 ~x_4 ~x_5 ~x_3 ~x_0

~\phi_{4,2}

 ~x_3 ~x_5 ~x_2 ~x_0 ~x_1 ~x_6 ~x_4

~\phi_{4,3}

 ~x_1 ~x_4 ~x_3 ~x_6 ~x_0 ~x_2 ~x_5

~\phi_{4,4}

 ~x_6 ~x_4 ~x_0 ~x_5 ~x_2 ~x_1 ~x_3

~\phi_{5,1}

 ~x_3 ~x_4 ~x_1 ~x_0 ~x_5 ~x_2 ~x_6

~\phi_{5,2}

 ~x_6 ~x_2 ~x_1 ~x_0 ~x_3 ~x_4 ~x_5

~\phi_{5,3}

 ~x_2 ~x_6 ~x_0 ~x_4 ~x_3 ~x_1 ~x_5

~\phi_{5,4}

 ~x_1 ~x_5 ~x_3 ~x_2 ~x_0 ~x_4 ~x_6

~\phi_{5,5}

 ~x_2 ~x_5 ~x_0 ~x_6 ~x_4 ~x_3 ~x_1

Шаг 3. Формирование дайджеста сообщения

На этом шаге используется D_n = D_{n,7}D_{n,6}\dots D_{n,0} длиной в 256 бит, полученный на шаге 2. Если требуемый размер хэша — 256 бит, то ~D_n и есть дайджест сообщения. Рассмотрим остальные 4 случая.

1. Размер хеша — 128 бит

Представим ~D_{n,7}, D_{n,6},D_{n,5} и ~D_{n,4} в следующем виде:

D_{n,7} = X_{7,3}^{}X_{7,2}^{}X_{7,1}^{}X_{7,0}^{}
D_{n,6} = X_{6,3}^{}X_{6,2}^{}X_{6,1}^{}X_{6,0}^{}
D_{n,5} = X_{5,3}^{}X_{5,2}^{}X_{5,1}^{}X_{5,0}^{}
D_{n,4} = X_{4,3}^{}X_{4,2}^{}X_{4,1}^{}X_{4,0}^{}     

Тогда дайджестом сообщения является 128-битовое ~Y_3Y_2Y_1Y_0, где

Y_3 = D_{n,3}\boxplus
Y_2 = D_{n,2}\boxplus
Y_1 = D_{n,1}\boxplus
Y_0 = D_{n,0}\boxplus

2. Размер хеша — 160 бит

Представим ~D_{n,7}, D_{n,6} и ~D_{n,5} в следующем виде:

D_{n,7} = X_{7,4}^{}X_{7,3}^{}X_{7,2}^{}X_{7,1}^{}X_{7,0}^{}
D_{n,6} = X_{6,4}^{}X_{6,3}^{}X_{6,2}^{}X_{6,1}^{}X_{6,0}^{}
D_{n,5} = X_{5,4}^{}X_{5,3}^{}X_{5,2}^{}X_{5,1}^{}X_{5,0}^{}

Тогда дайджестом сообщения является 160-битовое ~Y_4Y_3Y_2Y_1Y_0, где

Y_4 = D_{n,4}\boxplus
Y_3 = D_{n,3}\boxplus
Y_2 = D_{n,2}\boxplus
Y_1 = D_{n,1}\boxplus
Y_0 = D_{n,0}\boxplus

3. Размер хеша — 192 бит

Представим ~D_{n,7} и ~D_{n,6} в следующем виде:

D_{n,7} = X_{7,5}^{}X_{7,4}^{}X_{7,3}^{}X_{7,2}^{}X_{7,1}^{}X_{7,0}^{}
D_{n,6} = X_{6,5}^{}X_{6,4}^{}X_{6,3}^{}X_{6,2}^{}X_{6,1}^{}X_{6,0}^{}

Пусть

Y_5 = D_{n,5}\boxplus
Y_4 = D_{n,4}\boxplus
Y_3 = D_{n,3}\boxplus
Y_2 = D_{n,2}\boxplus
Y_1 = D_{n,1}\boxplus
Y_0 = D_{n,0}\boxplus

~Y_5Y_4Y_3Y_2Y_1Y_0 — дайджест сообщения.

4. Размер хеша — 224 бит

Представим ~D_{n,7} в следующем виде:

D_{n,7} = X_{7,6}^{}X_{7,5}^{}X_{7,4}^{}X_{7,3}^{}X_{7,2}^{}X_{7,1}^{}X_{7,0}^{}

Тогда дайджестом сообщения является 224-битовое ~Y_6Y_5Y_4Y_3Y_2Y_1Y_0, где

Y_6 = D_{n,6}\boxplus
Y_5 = D_{n,5}\boxplus
Y_4 = D_{n,4}\boxplus
Y_3 = D_{n,3}\boxplus
Y_2 = D_{n,2}\boxplus
Y_1 = D_{n,1}\boxplus
Y_0 = D_{n,0}\boxplus


Константы, использующиеся в алгоритме

В данном алгоритме используются 136 32-битовых константы. Запишем их в следующем порядке:

1.D_{0,7},D_{0,6},\dots,D_{0,0}
2.K_{2,31},K_{2,30},\dots,K_{2,0}
3.K_{3,31},K_{3,30},\dots,K_{3,0}
4.K_{4,31},K_{4,30},\dots,K_{4,0}
5.K_{5,31},K_{5,30},\dots,K_{5,0}

243F6A88 85A308D3 13198A2E 03707344 A4093822 299F31D0 082EFA98 EC4E6C89

452821E6 38D01377 BE5466CF 34E90C6C C0AC29B7 C97C50DD 3F84D5B5 B5470917
9216D5D9 8979FB1B D1310BA6 98DFB5AC 2FFD72DB D01ADFB7 B8E1AFED 6A267E96
BA7C9045 F12C7F99 24A19947 B3916CF7 0801F2E2 858EFC16 636920D8 71574E69
A458FEA3 F4933D7E 0D95748F 728EB658 718BCD58 82154AEE 7B54A41D C25A59B5

9C30D539 2AF26013 C5D1B023 286085F0 CA417918 B8DB38EF 8E79DCB0 603A180E
6C9E0E8B B01E8A3E D71577C1 BD314B27 78AF2FDA 55605C60 E65525F3 AA55AB94
57489862 63E81440 55CA396A 2AAB10B6 B4CC5C34 1141E8CE A15486AF 7C72E993
B3EE1411 636FBC2A 2BA9C55D 741831F6 CE5C3E16 9B87931E AFD6BA33 6C24CF5C

7A325381 28958677 3B8F4898 6B4BB9AF C4BFE81B 66282193 61D809CC FB21A991
487CAC60 5DEC8032 EF845D5D E98575B1 DC262302 EB651B88 23893E81 D396ACC5
0F6D6FF3 83F44239 2E0B4482 A4842004 69C8F04A 9E1F9B5E 21C66842 F6E96C9A
670C9C61 ABD388F0 6A51A0D2 D8542F68 960FA728 AB5133A3 6EEF0B6C 137A3BE4

BA3BF050 7EFB2A98 A1F1651D 39AF0176 66CA593E 82430E88 8CEE8619 456F9FB4
7D84A5C3 3B8B5EBE E06F75D8 85C12073 401A449F 56C16AA6 4ED3AA62 363F7706
1BFEDF72 429B023D 37D0D724 D00A1248 DB0FEAD3 49F1C09B 075372C9 80991B7B
25D479D8 F6E8DEF7 E3FE501A B6794C3B 976CE0BD 04C006BA C1A94FB6 409F60C4

Первые 8 констант D_{0,0},D_{0,1},\dots,D_{0,7}  представляют собой первые 256 бита дробной части числа ~\pi. Константы K_{2,0},D_{2,1},\dots,K_{2,31} соответствуют следующим 1024 битам дробной части ~\pi и т. д.

Функции F1, F2, F3, F4 и F5

Булевы функции ~F_1, ~F_2, ~F_3, ~F_4 и ~F_5, использующиеся в алгоритме, обладают рядом полезных свойств в случае предварительной перестановки их аргументов :

1) Они сбалансированы по 0 и 1. Это значит, что выходом функции при произвольном наборе входных данных с равной вероятностью может быть либо 0, либо 1.
2) Они сильно нелинейные.
3) Они удовлетворяют критерию строгого лавинного эффекта, т.е при изменении значения любой из входных переменных значение функции меняется с вероятностью 1/2.
4) Они не могут быть получены одна из другой посредством применения линейных преобразований к входным переменным.
5) Этот набор функций — взаимно некоррелирующий по выходу, то есть любая пара функций взаимно не коррелирует по выходу




Просмотров: 3233


<<<


Компьютерное аппаратное обеспечение   
Вычислительные комплексы   
Компьютерные данные   
Компьютерные журналы   
Классы компьютеров   
Компьютеры   
Программное обеспечение   
Производители компьютеров   
Профессии в ИТ   
Системное администрирование   
Компьютерный сленг   
Списки компьютерных терминов   
Человеко-компьютерное взаимодействие