Общая схема подписывания и проверки подписи с использованием хэш-функции.

Открытый канал

Отправитель А Получатель В

S, М'

М

Вычисляет хэш-

значение Получает из канала

m = h (M) сообщения М сообщение М',

и подписывает своим вычисляет хэш

секретным ключом d. значение m' = h (М'),

Подпись S = D (m,d). проверяет подпись.

D-преобразование В случае RSA, проверка

подписывания. В случае подписи состоит в:

RSA, подпись S=m^d mod n. получении m=S^e (mod n),

сравнении m= m'.

e – открытый ключ А.

Составляет пару с

ключом d.

Хэш-функциейв криптографии называется преобразование информации, переводящее строку битов произвольной длины в строку битов фиксированной длины.

Хэшфункция должна обладать двумя основными свойствами:

• для данного значения h(M) должно быть невозможно найти аргумент M. Такая хэш-функция называется стойкой в смысле обращения или стойкой в сильном смысле;

• для данного аргумента M должно быть невозможно найти другой аргумент M^'такой, что h(M)= h(M^').Такая хэш-функция называется стойкой в смысле вычисления коллизийили стойкой в слабом смысле.

Хэш-функция может использоваться:

• для создания сжатого образа сообщения, применяемого в механизме цифровой подписи;

• для защиты пароля;

• для построения кода аутентификации сообщений.

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

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

Хорошая хэш-функция равномерно и случайно отображает множество всех возможных входных сообщений во множество результирующих хэшей.

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

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

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

Похожие требования предъявляются к функциям вычисления контрольных сумм (Cyclical Redundancy Check, CRC), таким как CRC32 или Adler32. Но контрольные суммы призваны, в первую очередь, обнаруживать случайные нарушения целостности. Так что задача подбора двух сообщений, контрольные суммы для которых будут совпадать, или нахождения сообщения с заданным значением контрольной суммы может быть решена эффективно. Например, достаточно откорректировать всего 4 идущих подряд байта, расположенных в любом месте изменяемого сообщения, чтобы значение CRC32 для этого сообщения осталось таким же, как до внесения изменений. Поэтому контрольные суммы (обычно очень простые в реализации) не стоит использовать в криптографии.

Если на выходе хэш-функции, реализующей идеально слулайное равновероятное отображение, получается, например, 128-битовое значение и хэш-функция была вычислена от 2128 разных сообщений, это не значит, что каждое из 2128 возможных выходных значений получилось ровно один раз. Действительно, предположим, что мы вычислили хэш ровно от половины (2127) входных сообщений, и получили 2127 разных выходных значений, т. е. не было ни одного повторения. Учитывая тот факт, что отображение случайно и равновероятно значение хэш-функции от следующего сообщения с вероятностью будет совпадать с одним из уже полученных значений. И с каждым новым значена хэша вероятность возникновения коллизии будет только возрастать.

Известные хэш-функции: MD2, MD4 и MD5, SHA, SHS, ГОСТ Р 34.11-94