Хэш-функции

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

S = H(k, T),

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

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

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

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

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

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

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

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

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

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

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

· дополнение текста до длины, кратной 128 битам;

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

· добавление контрольной суммы к тексту;

· повторное вычисление контрольной суммы.

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

· дополнение текста до длины, равной 448 бит по модулю 512;

· добавляется длина текста в 64-битном представлении;

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

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

Алгоритм SHA (Secure Hash Algorithm) разработан NIST (National In s titute of Standa r d and Technolo g y) и повторяет идеи серии MD. В SHA используются тексты более 2⁶⁴ бит, которые закрываются сигнатурой длиной 160 бит. Данный алгоритм предполагается использовать в программе Capstone[17].