Полный пример MD5

Отличия MD5 от MD4

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

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

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

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

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

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

Разделим блок на 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.

Если t - это номер операции (от 1 до 80), W_t представляет собой t-ый подблок расширенного сообщения, а <<<s - это циклический сдвиг влево на s битов.

В начале основного цикла блок хэшируемого текста расширяется до 80 слов по 32 бита по правилу: для слово совпадает с -тым подблоком исходного блока; для полагают , где -- промежуточные значения слов.

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

TEMP;

;

;

;

TEMP;

Здесь, как и прежде, символ "" обозначает циклический сдвиг. Основной цикл завершается суммированием , , , , и , , , , . Выходом алгоритма является конкатенация , , , , .

В качестве интересного замечания, в первоначальной спецификации SHA не было циклического сдвига влево. Изменение "исправляет технический изъян, который делал стандарт менее безопасным, чем предполагалось. NSA отказалось уточнить истинную причину изъяна.

Сведения об успешных криптографических вскрытиях SНА отсутствуют.

SНА - это МD4 с добавлением расширяющего преобразования, дополнительного этапа и улучшенным лавинным эффектом. МD5 - это МD4 с улучшенным битовым хэшированием, дополнительным этапом и улучшенным лавинным эффектом.

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