Самостоятельные хэш – алгоритмы.

Краткое описание наиболее распространенных алгоритмов

 

• MD2

       Самая медленная хэш-функция. Оптимизирована для 8-битных машин.

• MD4

   Самая быстрая хэш-функция. Оптимизирована для 32-битных машин. Не так давно взломана.

• MD5

        Наиболее распространенная из семейства MD хэш-функция. Считается очень стойкой и безопасной. Похожа на MD4, но имеет несколько дополнительных средств для повышения безопасности, что замедляет ее примрно на треть по сравнению с MD4. Обеспечивает целостность данных.

• RIPEMD

• SHA1

       Secure Hash Algorithm. Создает 160-битовое значение хэш-функции из исходных данных переменного размера. Предложена NIST и принята правительством США как стандарт. Используется в стандарте DSS.

• Snefru

• Tiger

• Yarrow

• ГОСТ Р34.11-94

 

 

Алгоритм MD2

 

Предполагает:

· дополнение текста до длины, кратной 128 битам;

· вычисление 16-битной контрольной суммы (старшие разряды отбрасываются);

· добавление контрольной суммы к тексту;

· повторное вычисление контрольной суммы.

 

МD2 - это другая 128-битовая однонаправленная хэш-функция, разработанная Роном Ривестом. Она, вместе с МD5, используется в протоколах РЕМ. Безопасность МD2 опирается на слу­чайную перестановку байтов. Эта перестановка фиксирована и зависит от разрядов п. S₀, S₁, … S₂₅₅ и яв­ляются перестановкой.

Хэширование сообщения М MD2:

(1) Дополнение сообщения i байтами, значение i  должно быть таким, чтобы длина полученного сообщения была кратна 16 байтам.

(2) Добавление к сообщению 16 байтов контрольной суммы.

(3) Инициализация 48-байтового блока: Х₀, Х₁, Х₂,..., Х₄₇. Заполнение первых 16 байтов X нулями, во вторые 16 байтов X копирование первых 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X.

(4) Вот как выглядит функция сжатия:
t = 0

For j  = О to  17

For k =  О  to 47
t = X_t XOR S_t
t = (t +j)mod 256

(5) Копирование во вторые 16 байтов X вторых 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X. Выполнение этапа (4). Повторение этапов (5) и (4) по очереди для каждых 16 байтов сообщения.

(6) Выходом являются первые 16 байтов X.

Хотя в МD2 пока не было найдено слабых мест, она работает медленнее большинства других предлагаемых хэш- функций.

 

Алгоритм МD3

Имела ряд недостатков и нико­гда не выходила за пределы лаборатории.

Была предложена Роном Ривестом.

Группа исследователей из Университета Ватерлоо предложила однонаправленную хэш-функцию на базе итеративного возведения в степень в GF(2⁵⁹³).

По этой схеме сообщение разбивается на 593-битовые блоки.
Начиная с первого блока блоки последовательно возводятся в степень.
Показатель степени - это результат вычислений для предыдущего блока, первый показатель задается с помощью N.

 

Алгоритм MD4

Алгоритм MD4 (Message Digest) был разработан Ривестом. Размер вырабатываемого хэш-кода -- 128 битов. По заявлениям самого разработчика при создании алгоритма он стремился достичь следующих целей:

• Безопасность. Для построения коллизий не существует алгоритма эффективнее метода "грубой силы" (т. е. метода, основанного на "парадоксе дня рождения").
• Алгоритм построен без использования каких-либо предположительно трудных задач, т. е. его стойкость должна, подобно шифраторам, обеспечиваться его собственной конструкцией.
• Скорость. Алгоритм допускает эффективную программную реализацию на 32-разрядном процессоре.
• Простота и компактность. Алгоритм MD4 не использует сложных структур данных и подпрограмм.
• Алгоритм оптимизирован с точки зрения его реализации на микропроцессорах типа Intel.

Алгоритм MD 4 предусматривает:

· дополнение текста до длины, равной 448 бит по модулю 512;

· добавляется длина текста в 64-битном представлении;

·  512-битные блоки подвергаются процедуре Damgard-Merkle[1], причем каждый блок участвует в трех разных циклах.

 

Алгоритм MD5

MD5 является доработанной версией алгоритма MD4. Аналогично MD4, в алгоритме MD5 размер хэш-кода равен 128 битам.

После ряда начальных действий MD5 разбивает текст на блоки длиной 512 битов, которые, в свою очередь, делятся на 16 подблоков по 32 бита. Выходом алгоритма являются 4 блока по 32 бита, конкатенация которых образует 128-битовый хэш-код.

Сначала текст дополняется таким образом, чтобы длина получаемого текста, выраженная в битах, стала на 64 меньше числа, кратного 512. Дополнение осуществляется приписыванием к концу сообщения единицы и затем необходимого числа нулей (в бинарном представлении). Затем к тексту приписывается 64-битовое представление длины исходного сообщения. Таким образом получается текст, длина которого кратна 512 битам.

 

Описание МD5

После некоторой первоначальной обработки МD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, кото­рые объединяются в единое 128-битовое хэш-значение.

Во первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до конца сообщения следует столько нулей, сколько нужно. Затем, к результату добавляется 64-битовое представление длины сообщения (истинной, до дополнения). Эти два дейст­вия служат для того, чтобы длина сообщения была кратна 512 битам (что требуется для оставшейся части алго­ритма), и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения. Ини­циализируются четыре переменных:

А = 0x01234567

В = Оx89abcdef

С = Оxfedcba98

D = 0x76543210

 

Они называются переменными сцепления.

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

Четыре переменных копируются в другие переменные: А в а, В в b, С в с и D в d.

Главный цикл состоит из четырех очень похожих этапов (у МD4 было только три этапа). На каждом этапе 16 раз используются различные операции. Каждая операция представляет собой нелинейную функцию над тре­мя из а, b, с и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе. Далее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из переменных а, b, с и d. Наконец результат заменяет одну из переменных а, b, с и d. См. 13-й и 12-й. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая функция).

 

Каждый основной цикл состоит из 4 раундов (в MD4 было всего 3 раунда). В свою очередь, каждый раунд состоит из 16 операторов. Все операторы однотипны и имеют вид: . Здесь:

, , и суть , , и в зависимости от номера раунда и номера оператора в раунде (в оригинале эта подстановка записана в явном виде).

обозначает -тый подблок обрабатываемого блока. В каждом раунде порядок обработки очередным оператором подблоков определяется задаваемой в явном виде подстановкой на множестве всех подблоков (их, также как и операторов, 16).

обозначают зафиксированные случайные константы, зависящие от номера раунда и номера оператора в раунде (Ривест положил для -того () оператора в -том () раунде константу равной целой части от .

обозначает левый циклический сдвиг аргумента на битов. Величины сдвигов также зависят от номера раунда и номера оператора в раунде.

-- некоторая функция (фиксированная для каждого раунда), действующая покоординатно на биты своих трех аргументов.

 

Рис. Основной цикл алгоритма MD5.

Рис. Одна операция МD5

 

На первом этапе действует функция .

На втором этапе действует функция .

На третьем этапе действует функция .

На четвертом этапе действует функция .

После всего этого а, b, с и d добавляются к А, В, С и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение А, В, С и D.

 

Отличия MD5 от MD4

- в основной цикл был добавлен еще один дополнительный раунд (четвертый);

- в каждом операторе при суммировании используется уникальная константа;

- изменена функция, использованная во втором раунде с целью сделать ее менее
 симметричной.

- к промежуточным результатам каждого шага прибавляются результаты предыдущих шагов, что позволяет усилить эффект распространения ошибки;

- изменен порядок считывания слов во втором и третьем раундах;

- величина циклического сдвига в каждом раунде u1086 оптимизирована с точки зрения усиления эффекта распространения ошибки. Сдвиги от раунда к раунду
различаются.

 

ПОЛНЫЙ ПРИМЕР MD5

 

Разделим блок на 16 блоков длиной по 32 бита.
Инициализация массива. Массив состоит из 4х блоков по 32 бита, A, B, C и D.
Они инициализируются следующим образом:

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

Обработка 16ти битовых блоков.
Определим 4 вспомогательных функции: F, G, H, I.
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
Еще нам понадобится 64х битовая таблица T. Пусть T[i] =
4294967296*abs(sin(i)), i - в радианах.

Каждый 16-ти битовый блок изменит массив таким образом (алгоритм):
Сохраним значения A, B, C, D: AA=A, BB=B, CC=C, DD=D.

Раунд первый. Пусть [abcd k s i] обозначает операцию:
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s).
Произведем 16 операций:

[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

Раунд второй. [abcd k s i] обозначает:
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s)
Операции:

[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

Раунд третий: a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s)

[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

Раунд четвертый: a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s)

[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]

Дальше увеличиваем A, B, C и D на значения, которые они имели до раундов:
A=A+AA
B=B+BB
C=C+CC
D=D+DD

Последний шаг - вывод. Результат - слова с A по D в порядке младший
бит-первый.

Значения элементов таблицы T:

0xd76aa478 0xe8c7b756 0x242070db 0xc1bdceee 0xf57c0faf 0x4787c62a 0xa8304613
0xfd469501 0x698098d8 0x8b44f7af 0xffff5bb1 0x895cd7be 0x6b901122 0xfd987193
0xa679438e 0x49b40821 0xf61e2562 0xc040b340 0x265e5a51 0xe9b6c7aa 0xd62f105d
0x2441453 0xd8a1e681 0xe7d3fbc8 0x21e1cde6 0xc33707d6 0xf4d50d87 0x455a14ed
0xa9e3e905 0xfcefa3f8 0x676f02d9 0x8d2a4c8a 0xfffa3942 0x8771f681 0x6d9d6122
0xfde5380c 0xa4beea44 0x4bdecfa9 0xf6bb4b60 0xbebfbc70 0x289b7ec6 0xeaa127fa
0xd4ef3085 0x4881d05 0xd9d4d039 0xe6db99e5 0x1fa27cf8 0xc4ac5665 0xf4292244
0x432aff97 0xab9423a7 0xfc93a039 0x655b59c3 0x8f0ccc92 0xffeff47d 0x85845dd1
0x6fa87e4f 0xfe2ce6e0 0xa3014314 0x4e0811a1 0xf7537e82 0xbd3af235 0x2ad7d2bb
0xeb86d391

 

 

SECURE HASH ALGORITHM (SHA)

В переводе «Алгоритм безопасного хэширования».

SHA разработан в 1993 году Национальным институтом стандартов и технологий (NIST) США совместно с Агентством национальной безопасности США. Разработчики считают, что для SHA невозможно найти алгоритм, не требующий больших вычислительных ресурсов, который позволил бы найти коллизии.

В результате применения алгоритма получается хэш-код длиной 160 бит. Процедура дополнения хэшируемого текста до кратного 512 битам аналогична подобной процедуре алгоритма MD5.

 

Назначаются 5 переменных по 32 бита (в алгоритме MD5 таких переменных было 4):

A = 67 45 23 01;  

B = EF CD AB 89;

C = 98 BA DC FE;

D= 10 32 54 76;

У = С3 D2 E1 F0.

Также как и в MD5 создаются копии этих переменных AA, BB, CC, DD и EE. Основный цикл данного алгоритма состоит из 4 раундов, каждый из которых состоит из 20 операторов.

SHA скорее является модификацией MD4, нежели новой разработкой. Сравним изменения

MD4, сделанные при разработке MD5, и изменения, сделанные в MD4 при разработке

SHA.

1. В каждом из алгоритмов используется 4 раунд. В SHA функция, используемая в 4

раунде аналогично функции из 2 раунда.

2. В SHA используется тот же принцип аддитивной константы для каждого оператора в

раунде, что и в MD4. (в MD5 константа каждого оператора отличается от других).

3. Во втором раунде SHA используется та же функция что и в MD4, тогда как в MD5 она

была изменена, чтобы сделать ее менее симметричной.

4. Для усиления эффекта распространения ошибки в SHA добавлена 5-я переменная по

которой идет "зацепление", в результате этого метод ден Бура -- Босселэра, эффективный

для MD5, перестает работать в случае SHA.

5. Если в MD5 изменен порядок считывания слов во втором и третьем раундах, то в SHA

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

ошибки.

6. В MD5 величина циклического сдвига меняется от раунда к раунду и от оператора к

оператору, а в SHA используют простые циклические сдвиги.

 

Одна операция SHA.