Построение хеш-функции на основе вычислительно трудной математической задачи
В качестве примера хеш-функций, построенных на основе вычислительно трудной математической задачи, можно привести функцию из рекомендаций МККТТ Х.509. Криптографическая стойкость функции основана на сложности решения следующей труднорешаемой теоретико- числовой задачи. Задача умножения двух больших (длиной в несколько сотен битов) простых чисел является простой с вычислительной точки зрения, в то время как факторизация (разложение на простые множители) полученного произведения является труднорешаемой задачей для указанных размерностей.
Следует отметить, что задача разложения числа на простые множители эквивалентна следующей труднорешаемой математической задаче.
Пусть n= pq произведение двух простых чисел р и q. В этом случае можно легко вычислить квадрат числа по модулю n: x2(modn), однако вычислительно трудно извлечь квадратный корень по этому модулю.
Таким образом, хеш-функцию МККТТ Х.509 можно записать следующим образом:
Hi = [(Hi-1ÅМi)2] (mod n),
где i = 1,n; H0 = I = 0; М = М1, М2,..., Мn.
Длина блока Mi представляется в октетах, каждый октет разбит пополам и к каждой половине спереди приписывается полуоктет, состоящий из двоичных единиц: n — произведение двух больших (512- битных) простых чисел р и q.
|
Построение хеш-функции «с нуля»
По-видимому, наиболее эффективным на сегодня с точки зрения программной реализации и условий применения оказываются хеш-функции, построенные «с нуля».
Наиболее известные алгоритмы получения хеш-образов сообщений – MD4, MD5, SHA, TIGER.
Алгоритм MD4 (Message Digest) был разработан Р. Ривестом. Размер вырабатываемого хеш-кода — 128 битов. По заявлениям самого разработчика при создании алгоритма он стремился достичь следующих целей:
· безопасность (для построения коллизий не существует алгоритма эффективнее метода, основанного на «парадоксе дня рождения»);
· алгоритм построен без использования каких-либо предположительно трудных задач, т. е. его стойкость должна, подобно шифру, обеспечиваться собственной конструкцией;
· скорость (алгоритм допускает эффективную программную реализацию на 32-разрядном процессоре);
· простота и компактность (алгоритм MD4 не использует сложных структур данных и подпрограмм);
· алгоритм оптимизирован с точки зрения его реализации на микропроцессорах типа Intel.
После того, как алгоритм был впервые опубликован, несколько криптоаналитиков построили коллизии для последних двух из трех раундов, используемых в MD4. Несмотря на то, что ни один из предложенных методов построения коллизий не приводит к успеху для полного MD4, автор усилил алгоритм и предложил новую схему хеширования MD5.
Алгоритм MD5 является доработанной версией алгоритма MD4. Аналогично MD4 в алгоритме MD5 размер хеш-кода равен 128 битам. После ряда начальных действий MD5 разбивает текст на блоки длиной 512 битов, которые, в свою очередь, делятся на 16 подблоков по 32 бита. Выходом алгоритма являются 4 блока по 32 бита, конкатенация которых образует 128-битовый хеш-код.
В 1993 г. Национальный институт стандартов и технологий (NIST) США совместно с Агентством национальной безопасности США выпустил «Стандарт стойкой хеш-функции» (Secure Hash Standard), частью которого является алгоритм SHA. Предложенная процедура вырабатывает хеш-код длиной 160 битов для произвольного текста длиной менее 264 битов. Разработчики считают, что для SHA невозможно предложить алгоритм, имеющий разумную трудоемкость, который строил бы два различных сообщения, дающих один и тот же хеш-код (т.е. алгоритм, находящий коллизии). Алгоритм SHA основан на тех же самых принципах, которые использовал Р. Ривест при разработке MD4. Более того, алгоритмическая процедура SHA очень похожа на структуру MD4. Процедура дополнения хешируемого текста до кратного 512 битам полностью совпадает с процедурой дополнения алгоритма MD5.
В 1995 г. стандарт был пересмотрен (FIPS 180-1) в пользу версии SHA-1. Позднее стандарт был пересмотрен вновь и были определены четыре новые версии: SHA-224, SHA-256, SHA-384, SHA-512. Все версии имеют одинаковую структуру, поэтому часто их называют общим именем SHA-2. В таблице приведены характеристики этих версий.
Обобщая сказанное ранее, следует отметить, что при выборе практически стойких и высокоэффективных хеш-функций можно руководствоваться следующими эвристическими принципами, сформулированными Р. Ривестом:
· любой из известных алгоритмов построения коллизий не должен быть эффективнее метода, основанного на «парадоксе дня рождения»;
· алгоритм должен допускать эффективную программную реализацию на 32-разрядном процессоре;
· алгоритм не должен использовать сложных структур данных и подпрограмм;
· алгоритм должен быть оптимизирован с точки зрения его реализации на микропроцессорах типа Intel.