Тем не менее есть надежда, что грядущие пять лет напряженных практических поисков кандидата на наилучшую хеш-функцию приведут и к заметным сдвигам в общей теории.
«Рабочая лошадка» криптографии
В отличие от более привычных терминов «шифр» или «ключ» словосочетание «однонаправленная хеш-функция» по сию пору может звучать замысловато даже для людей, достаточно близко знакомых с принципами работы компьютера и его программ. Однако суть этой конструкции прозрачна. Хеш-функция - это (с точностью до деталей) такое математическое преобразование, которое на входе получает файл или «сообщение» произвольной длины и вычисляет для него подающийся на выход «дайджест» (иначе именуемый также «хеш» или «цифровой отпечаток»), то есть последовательность фиксированной (сравнительно небольшой) длины и уникального вида. В принципе, все хеш-функции устроены примерно одинаково - как многократное повторение итераций (циклов) некоторого хитрого преобразования, постепенно ужимающего файл до длины дайджеста с одновременным мощным перемешиванием битов содержимого.
Всякая хорошая хеш-функция действует так, что даже единственное изменение байта или бита в файле на входе приводит на выходе к хеш-значению совершенно иного вида. Иногда даже требуют, чтобы при изменении единственного бита на входе менялось не менее половины битов на выходе - это условие называют лавинным свойством (avalanche property). Кроме того, чтобы быть полезной в криптографии, хеш-функция должна обладать еще двумя важнейшими свойствами.
Во-первых, криптографические хеш-функции должны быть однонаправленными. Под этим принято понимать легкое вычисление в одну сторону и невозможность вычисления в обратную. Иначе говоря, всегда можно и удобно подать нечто на вход и быстро получить соответствующее хеш-значение на выходе, однако нет никакой возможности за разумное время по выходному значению хеш-функции вычислить, что подавалось на вход.
Во-вторых, криптографические хеш-функции не должны иметь коллизий. Это означает, что хотя для каждого хеш-значения в принципе имеется бесконечное число вариантов входных последовательностей, нельзя отыскать два разных входа, дающих одинаковый дайджест (образующих «коллизию»). «Нельзя» здесь понимается опять-таки в вычислительном смысле - «невозможно за приемлемое в реальных условиях время».
Наиболее типичный и повсеместно распространенный способ применения криптографического хеширования - это проверка целостности сообщений. Для простой проверки того, были ли внесены какие-то изменения или искажения в файл на этапе доставки, очень удобно сравнивать дайджесты, вычисляемые до и после передачи информации (или извлечения файла из хранилища, или любого другого события). Другая, близко связанная с первой область - цифровая подпись. Из соображений общей безопасности и для существенного ускорения обработки подавляющее большинство алгоритмов цифровой подписи устроены так, что всегда «подписывается» только дайджест сообщения, а не весь файл.
