Хэш-функции

Требования к хэш-функциямХэш-функцией называется односторонняя функция, предназначенная для получения дайджеста или "отпечатков пальцев" файла, сообщения или некоторого блока данных. Хэш-код создается функцией Н: h = H (M) Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины. Рассмотрим требования, которым должна соответствовать хэш-функция для того, чтобы она могла использоваться в качестве аутентификатора сообщения. Рассмотрим очень простой пример хэш-функции. Затем проанализируем несколько подходов к построению хэш-функции. Хэш-функция Н, которая используется для аутентификации сообщений, должна обладать следующими свойствами: 1.  Хэш-функция Н должна применяться к блоку данных любой длины. 2.  Хэш-функция Н создает выход фиксированной длины. 3.  Н (М) относительно легко (за полиномиальное время) вычисляется для любого значения М. 4.  Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h. 5.  Для любого данного х вычислительно невозможно найти y  x, что H (y) = H (x). 6.  Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x). Хеширование паролей Для того, чтобы не заставлять человека запоминать ключ – длинную последовательность цифр, были разработаны методы преобразования строки символов любой длины (так называемого пароля) в блок байт заранее заданного размера (ключ). На алгоритмы, используемые в этих методах, накладываются требования, сравнимые с требованиями на сами криптоалгоритмы. От методов, повышающих криптостойкость системы в целом, перейдем к блоку хеширования паролей – методу, позволяющему пользователям запоминать не 128 байт, то есть 256 шестнадцатиричных цифр ключа, а некоторое осмысленное выражение, слово или последовательность символов, называющуюся паролем. Действительно, при разработке любого криптоалгоритма следует учитывать, что в половине случаев конечным пользователем системы является человек, а не автоматическая система. Это ставит вопрос о том, удобно, и вообще реально ли человеку запомнить 128-битный ключ (32 шестнадцатиричные цифры). На самом деле предел запоминаемости лежит на границе 8-12 подобных символов, а, следовательно, если мы будем заставлять пользователя оперировать именно ключом, тем самым мы практически вынудим его к записи ключа на каком-либо листке бумаги или электронном носителе, например, в текстовом файле. Это, естественно, резко снижает защищенность системы. Для решения этой проблемы были разработаны методы, преобразующие произносимую, осмысленную строку произвольной длины – пароль, в указанный ключ заранее заданной длины. В подавляющем большинстве случаев для этой операции используются так называемые хеш-функции (от англ. hashing – мелкая нарезка и перемешивание). Хеш-функцией называется такое математическое или алгоритмическое преобразование заданного блока данных, которое обладает следующими свойствами:1.  хеш-функция имеет бесконечную область определения,2.  хеш-функция имеет конечную область значений,3.  она необратима,4.  изменение входного потока информации на один бит меняет около половины всех бит выходного потока, то есть результата хеш-функции. Эти свойства позволяют подавать на вход хеш-функции пароли, то есть текстовые строки произвольной длины на любом национальном языке и, ограничив область значений функции диапазоном 0. . 2N-1, где N – длина ключа в битах, получать на выходе достаточно равномерно распределенные по области значения блоки информации – ключи. Нетрудно заметить, что требования, подобные 3 и 4 пунктам требований к хеш-функции, выполняют блочные шифры. Это указывает на один из возможных путей реализации стойких хеш-функций – проведение блочных криптопреобразований над материалом строки-пароля. Этот метод и используется в различных вариациях практически во всех современных криптосистемах. Материал строки-пароля многократно последовательно используется в качестве ключа для шифрования некоторого заранее известного блока данных – на выходе получается зашифрованный блок информации, однозначно зависящий только от пароля и при этом имеющий достаточно хорошие статистические характеристики. Такой блок или несколько таких блоков и используются в качестве ключа для дальнейших криптопреобразований.