Содержание
Криптографические xэш - функции
Хэшированием называется преобразование исходного информационного массива произвольной длины в битовую строку фиксированной длины. Криптографическая хэш-функция — хэш-функция, являющаяся криптографически стойкой, то есть удовлетворяющая ряду требований, специфичных для криптографических приложений.
Требования к криптографически стойким хэш-функциям :
- Для заданного значения хэш-функции
должно быть невозможно вычислить блок данных 
, для которого 
. - Стойкость к коллизиям первого рода: для заданного сообщения должно быть вычислительно невозможно подобрать другое сообщение
, для которого 
. - Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений
, имеющих одинаковый хэш.
Математически хэш функцию можно записать в виде:
,
где X – исходное сообщение, называемое иногда прообразом, а M – результат, называемый значением хеш-функции.
Для криптографических хэш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект).
Принципы построения
Итеративная последовательная схема
Для построения хэш-функций используется cтруктура Меркля-Дамгарда (рис. 1). Cжимающая функция преобразует k входных в n выходных бит, где 
— разрядность хэш-функции, а 
— произвольное число большее . Сжимающая функция должна быть криптографически стойкой.
Входной поток разбивается на блоки по 
бит. В качестве начального значения временной переменной используется произвольное число. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Значением хэш-функции являются выходные n бит последней итерации.
Сжимающая функция
Односторонняя функция сжатия преобразует два входных блока фиксированной длины в выходной блок фиксированной длины. В качестве сжимающей функции можно расмотреть одностороннюю функцию сжатия Миагучи-Пренеля (Miyaguchi–Preneel)
КатегорияКриптография