Два основных режима применения хэшфункций

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

В качестве примера хэшфункций, построенных на основе вычислительно трудной математической задачи можно привести функцию из рекомендаций MKKTT X.509.

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

Следует отметить, что задача разложения числа на простые множители эквивалентна следующей труднорешаемой математической задаче. Пусть n=pq произведение двух простых чисел p и q. В этом случае можно легко вычислить квадрат числа по модулю n: x2(mod n), однако вычислительно трудно извлечь квадратный корень по этому модулю.

Таким образом, хэшфункцию МККТТ X.509 можно записать как:

длина блока Mi представляется в октетах, каждый октет разбит пополам и к каждой половине спереди приписывается полуоктет, состоящий из двоичных единиц; n произведение двух больших (512битных) простых чисел p и q.

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

Алгоритм MD4 (Message Digest) был разработан Р. Ривестом [68,69]. Размер вырабатываемого хэшкода 128 битов. По заявлениям самого разработчика при создании алгоритма он стремился достичь следующих целей:

После того, как алгоритм был впервые опубликован, несколько криптоаналитиков построили коллизии для последних двух из трех раундов, используемых в 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.

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

  • любой из известных алгоритмов построения коллизий не должен быть эффективнее метода, основанного на "парадоксе дня рождения";
  • алгоритм должен допускать эффективную программную реализацию на 32разрядном процессоре;
  • алгоритм не должен использовать сложных структур данных и подпрограмм;
  • алгоритм должен быть оптимизирован с точки зрения его реализации на микропроцессорах типа Intel.

Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок