Хэш-функции | MetodPro.ru

Реклама на сайте

Хэш-функции


Использование цифровой сигнатуры предполагает использование некоторых функций шифрования:

S = H(k, T),

где S - сигнатура, k - ключ, T - исходный текст.

Функция H(k, T) - является хэш-функцией, если она удовлетворяет следующим условиям:

1) исходный текст может быть произвольной длины;

2) само значение H(k, T) имеет фиксированную длину;

3) значение функции H(k, T) легко вычисляется для любого аргумента;

4) восстановить аргумент по значению с вычислительной точки зрения  - практически невозможно;

5) функция H(k, T) - однозначна[1].

Из определения следует, что для любой хэш-функции есть тексты-близнецы - имеющие одинаковое значение хэш-функции, так как мощность множества аргументов неограниченно больше мощности множества значений. Такой факт получил название «эффект дня рождения».[2]

Наиболее известные из хэш-функций - MD2, MD4, MD5 и SHA.

Три алгоритма серии MD разработаны Ривестом в 1989-м, 90-м и 91-м году соответственно. Все они преобразуют текст произвольной длины в 128-битную сигнатуру.

Алгоритм MD2 предполагает:

  • дополнение текста до длины, кратной 128 битам;
  • вычисление 16-битной контрольной суммы (старшие разряды отбрасываются);
  • добавление контрольной суммы к тексту;
  • повторное вычисление контрольной суммы.

Алгоритм MD4 предусматривает:

  • дополнение текста до длины, равной 448 бит по модулю 512;
  • добавляется длина текста в 64-битном представлении;
  • 512-битные блоки подвергаются процедуре Damgard-Merkle[3], причем каждый блок участвует в трех разных циклах.

В алгоритме MD4 довольно быстро были найдены «дыры», поэтому он был заменен алгоритмом MD5, в котором каждый блок участвует не в трех, а в четырех различных циклах.

Алгоритм SHA (Secure Hash Algorithm) разработан NIST  (National Institute of Standard and Technology) и повторяет идеи серии MD. В SHA используются тексты более 264 бит, которые закрываются сигнатурой длиной 160 бит. Данный алгоритм предполагается использовать в программе Capstone[4].



[1] При этом разделяют слабую и сильную однозначность. При слабой однозначности для заданного значения T практически невозможно отыскать другой текст Т’, для которого H(k, T) = H(k, T’). При сильной однозначности для любого текста T невозможно найти другой подходящий текст, имеющий то же значение хэш-функции.

[2] Факт теории вероятностей: в группе из 23 человек с вероятностью больше 0.5 два и более человека родились в одно и то же число.

[3] В отличие от хэш-функции - этот класс преобразований предполагает вычисление для аргументов фиксированной длины также фиксированных по длине значений.

[4] Государственная программа США, предполагающая централизованное хранение всех ключей, используемых организациями а частными лицами.



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем