Криптографические xэш - функции

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

Требования к криптографически стойким хэш-функциям :

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

Математически хэш функцию можно записать в виде: ,

где – исходное сообщение, – значение хеш-функции.

Для криптографических хэш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект).

Принципы построения

Итеративная последовательная схема

Для построения хэш-функций используется cтруктура Меркля-Дамгарда. Cжимающая функция преобразует блоков,размер каждого состоит из бит.

В качестве начального значения переменной используется произвольное вектор инициализации . Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Если длина блока < , дополняется длиной сообщения и . Значением хэш-функции являются выходные бит последней итерации.

Сжимающая функция

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

В качестве сжимающей функции можно расмотреть одностороннюю функцию сжатия Миагучи-Пренеля (Miyaguchi–Preneel). Чтобы сделать алгоритм более устойчивым к атаке, исходный текст , блок и зашифрованный текст складываются с помощью и создают новый блок . Эта схема используется в Whirlpool для создания хэш-функции

Криптогафическая хэш-функция Whirlpool

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

Для решения данной задачи Whirlpool использует алгоритм Меркле-Дамгаарда дополнения входного сообщения. Результатом дополнения сообщения является сообщение , длина которого кратна 512. Пусть — длина исходного сообщения. Тогда M' получается в несколько шагов:

1. К концу сообщения M приписать бит «1» ;
2. Приписать x битов «0» так, чтобы длина полученной строки L+1+x была кратна 256 нечетное число раз;
3. Наконец, приписать 256-битное представление числа L.