Схемы построения хэш-функций

Общая идея хэш-функций

Криптографическая хэш-функция (функция хэширования) —.

это функция вида у = h (x), обладающая специальными свойствами:

• • функция преобразует вход х любой длины в выход фиксированной длины — хэш-код (message digest), который согласован со входом на цифровую подпись;
• • функция является однонаправленной, т. е. найти у = h (x) легко, a h~y) — вычислительно невозможно;
• • вычислительно невозможно найти такую пару чисел х и х таких что х не равно х но h (x) = h (x') (эта ситуация называется коллизией).

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

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

Криптографическая хэш-функция с ключом — это функция вида у = h (K, х)_у обладающая специальными свойствами:

• • функция преобразует вход х любой длины в выход фиксированной длины — хэш-код (message digest), который согласован со входом на цифровую подпись;
• • для любых значений К, х вычислить хэш-код h (K, х) просто;
• • по любому заданному значению х значение h (K, х) можно угадать с вероятностью ½″ ;
• • должно быть вычислительно трудно определить К по любому большому набору {(.г,; h (K, х))} или вычислить по этой информации h (K, х') для любого х', не равного ни одному из х_{.

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

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

С целью сокращения длины подписываемого сообщения и одновременного обеспечения целостности и подлинности сообщения.

Рис. 3.6. Схема электронной подписи с функцией хэширования.

схема цифровой подписи, как правило, применяется совместно с хэшфункцией, как показано на рис. 3.6.

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