Хэш-функция

В реализации цифровой электронной подписи для сокращения времени подписывания и размера подписи, в качестве источника для подписи служит не само исходное сообщение М (произвольной длины), а некоторая производная от него (фиксированной длины) Для ее получения используется общеизвестная функция Н, отображающая любое сообщение М в сообщение Н(М) фиксированного малого размера, которое далее преобразуется в цифровую подпись. Функция Н называется функцией хэширования (hash function), в простейшем случае это может быть, например, функция вычисления контрольной суммы текста сообщения по модулю 2³², размер приведенного для электронного подписывания сообщения тогда будет равен 32 двоичным разрядам (четырем байтам)

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

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

2) само значение Н(М) имеет фиксированную длину;

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

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

5) функция Н(М) - однозначна (при этом разделяют слабую и сильную однозначность: при слабой однозначности для заданного значения М практически невозможно отыскать другой текст М', для которого Н(М) = Н(М'); при сильной однозначности для любого текста М невозможно найти другой подходящий текст, имеющий то же значение хэш-функции).

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

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