Алгоритм безопасного хэширования SНА

Алгоритм MD5

Алгоритм MD5 (Message Digest №5) разработан Роналдом Риверсом. MD5 использует 4 многократно повторяющиеся преобразования над тремя 32-битными величинами U, V и W:

f(U,V,W)=(U AND V) OR ((NOT U) AND W)

g(U,V,W)=(U AND W) OR (V AND (NOT W))

h(U,V,W)=U XOR V XOR W

k(U,V,W)=V XOR (U OR (NOT W)).

В алгоритме используются следующие константы:

· начальные константы промежуточных величин -

H[0]=67452301₁₆, H[1]=EFCDAB89₁₆, H[2]=98BADCFE₁₆, H[3]=10325476₁₆;

· константы сложения в раундах -

y[j]=HIGHEST_32_BITS(ABS(SIN(j+1))) j=0...63,

где функция HIGHEST_32_BITS(X) отделяет 32 самых старших бита из двоичной записи дробного числа X, а операнд SIN(j+1) считается взятым в радианах;

· массив порядка выбора ячеек в раундах -

· z[0...63] = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,

· 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,

· 5, 8, 11, 4, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,

0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9);

· массив величины битовых циклических сдвигов влево -

· s[0...63] = (7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,

· 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,

· 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,

6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21).

На первоначальном этапе входной блок данных дополняется одним битом "1". Затем к нему добавляется такое количество битов "0", чтобы остаток от деления блока на 512 составлял 448. Наконец, к блоку добавляется 64-битная величина, хранящая первоначальную длину документа. Получившийся входной поток имеет длину кратную 512 битам.

Каждый 512-битный блок, представленный в виде 16 32-битных значений X[0]...X[15], проходит через сжимающую функцию, которая перемешивает его со вспомогательным блоком (H[0],H[1],H[2],H[3]):

(A,B,C,D) = (H[0],H[1],H[2],H[3])

цикл по j от 0 до 15

T = (A + f(B,C,D) + x[z[j]] + y[j]) ROL s[j]

(A,B,C,D) = (D,B+T,B,C)

конец_цикла

цикл по j от 16 до 31

T = (A + g(B,C,D) + x[z[j]] + y[j]) ROL s[j]

(A,B,C,D) = (D,B+T,B,C)

конец_цикла

цикл по j от 32 до 47

T = (A + h(B,C,D) + x[z[j]] + y[j]) ROL s[j]

(A,B,C,D) = (D,B+T,B,C)

конец_цикла

цикл по j от 48 до 63

T = (A + k(B,C,D) + x[z[j]] + y[j]) ROL s[j]

(A,B,C,D) = (D,B+T,B,C)

конец_цикла

(H[0],H[1],H[2],H[3]) = (H[0]+A,H[1]+B,H[2]+C,H[3]+D)

После того, как все 512-битные блоки прошли через процедуру перемешивания, временные переменные H[0],H[1],H[2],H[3], а 128-битное значение подается на выход хэш-функции.

Алгоритм MD5, основанный на предыдущей разработке Роналда Риверса MD4, был призван дать еще больший запас прочности к криптоатакам. MD5 очень похож на MD4. Отличие состоит в простейших изменениях в алгоритмах наложения и в том, что в MD4 48 проходов основного преобразования, а в MD5 - 64. Несмотря на большую популярность, MD4 "медленно, но верно" был взломан. Сначала появились публикации об атаках на упрощенный алгоритм. Затем было заявлено о возможности найти два входных блока сжимающей функции MD4, которые порождают одинаковый выход. Наконец, в 1995 году было показано, что найти коллизию, т.е. "хэш-двойник" к произвольному документу, можно менее чем за минуту, а добиться "осмысленности" фальшивого документа (т.е. наличия в нем только ASCII-символов с определенными "разумными" законами расположения) - всего лишь за несколько дней.

Алгоритм безопасного хэширования SНА (Secure Hash Algorithm) разработан НИСТ и АНБ США в рамках стандарта безопасного хэширования SHS (Secure Hash Standard) в 1992 г. Алгоритм хэширования SНА предназначен для использования совместно с алгоритмом цифровой подписи DSА.

При вводе сообщения М произвольной длины менее 2⁶⁴ бит алгоритм SНА вырабатывает 160-битовое выходное сообщение, называемое дайджестом сообщения МD (Message Digest). Затем этот дайджест сообщения используется в качестве входа алгоритма DSА, который вычисляет цифровую подпись сообщения М. Формирование цифровой подписи для дайджеста сообщения, а не для самого сообщения повышает эффективность процесса подписания, поскольку дайджест сообщения обычно намного короче самого сообщения.

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

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

Рассмотрим подробнее работу алгоритма хэширования SНА. Прежде всего исходное сообщение М дополняют так, чтобы оно стало кратным 512 битам. Дополнительная набивка сообщения выполняется следующим образом: сначала добавляется единица, затем следуют столько нулей, сколько необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, и наконец добавляют 64-битовое представление длины исходного сообщения.

Инициализируется пять 32-битовых переменных в виде:

А = 0х67452301

В = 0хЕFСDАВ89

С = 0х98ВАDСFЕ

D = 0x10325476

Е = 0хС3D2Е1F0

Затем начинается главный цикл алгоритма. В нем обрабатывается по 512 бит сообщения поочередно для всех 512-битовых блоков, имеющихся в сообщении. Первые пять переменных А, В, С, D, Е копируются в другие переменные a, b, с, d, е:

а = А, b = В, с = С, d = D, е = Е

Главный цикл содержит четыре цикла по 20 операций каждый. Каждая операция реализует нелинейную функцию от трех из пяти переменных а, b, с, d, е, а затем производит сдвиг и сложение.

Алгоритм SНА имеет следующий набор нелинейных функций:

f_t (Х, Y, Z) = (X ^Ù Y) Ú ((Ø X) ^Ù Z) для t = 0...19,

f_t (Х, Y, Z) =Х Å Y Å Z для t = 20...39,

f_t (Х, Y, Z) = (X ^Ù Y) Ú (X ^Ù Z) Ú (Y ^Ù Z) для t = 40...59,

f_t (Х, Y, Z) = Х Å Y Å Z для t = 60...79,

где t - номер операции.

В алгоритме используются также четыре константы:

К_t = 0х5А827999 для t = 0...19,

К_t = 0х6ЕD9ЕВА1 для t = 20...39,

К_t = 0х8F1ВВСDС для t = 40...59,

К_t = 0хСА62С1D6 для t = 60...79.

Блок сообщения преобразуется из шестнадцати 32-битовых слов (М₀...М₁₅) в восемьдесят 32-битовых слов (W₀...W₇₉) с помощью следующего алгоритма:

W_t = М_t для t = 0...15,

W_t = (W_t-3 Å W_t-8 Å W_t-14 Å W_t-16) <<< 1 для t = 16...79,

где t - номер операции, W_t - t-й субблок расширенного сообщения, <<< S - циклический сдвиг влево на S бит.

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

цикл по t от 0 до 79

ТЕМР = (а <<< 5) + f_t (b, c, d) + е + W_t + К_t

е = d

d = с

с = (b <<< 30)

b = а

а = ТЕМР

конец_цикла

Схема выполнения одной операции показана на рис.5.

Рис.5. Схема выполнения одной операции алгоритма SHA

После окончания главного цикла значения а, b, с, d, е складываются с А, В, С, D, Е соответственно, и алгоритм приступает к обработке следующего 512-битового блока данных. Окончательный выход формируется в виде конкатенации значений А, В, С, D, Е.

Отличия SHA от MD5 состоят в следующем:

· SНА выдает 160-битовое хэш-значение, поэтому он более устойчив к атакам полного перебора и атакам "дня рождения", чем MD5, формирующий 128-битовые хэш-значения.

· Сжимающая функция SHA состоит из 80 шагов, а не из 64 как в MD5.

· Расширение входных данных производится не простым их повторение в другом порядке, а рекуррентной формулой.

· Усложнен процесс перемешивания

Дата добавления: 2015-05-09