2. Функции хеширования

Варианты задания см. в таблице 1

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

фиксированной длины , называемое сверткой, или сжатым образом сообщения.

Хеш-функция Н должна обладать следующими свойствами:

(Односторонность.) Для заданного задача нахождения , для которого , должна быть вычислительно-трудоемкой (в то время как значение вычисляется относительно легко для любого ).
(Слабая сопротивляемость коллизиям.) При заданном задача нахождения другого сообщения , для которого , должна быть вычислительно-трудоемкой. (Пара сообщений и образуют коллизию, если .) В некоторых приложениях необходимо выполнение дополнительного свойства:
(Сильная сопротивляемость коллизиям.) Задача нахождения двух случайных сообщений и , для которых , должна быть вычислительно-трудоемкой (с экспоненциальным объемом перебора).

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

контроль целостности данных при их передаче и хранении;
аутентификация источника данных.

При решении первой задачи для каждого сообщения (набора данных) вычисляется его свертка ), которая передается и хранится вместе с сообщением как контрольное значение. При получении данных получатель вычисляет значение свертки и сравнивает его с имеющимся контрольным значением. Несовпадение означает, что данные были изменены. Чтобы противник (злоумышленник) не смог самостоятельно вычислить контрольное значение свертки и тем самым осуществить необнаруживаемую подмену данных, свертка должна зависеть от секретного параметра (ключа), известного только отправителю и получателю сообщения. Хеш-функции, зависящие от секретного ключа, называют ключевыми, или кодами аутентификации сообщений (MAC – Message Autentication Code), другие названия – имитовставка, криптографическая контрольная сумма.

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

Как правило, хеш-функцию строят на основе т.н. одношаговых сжимающих функций , где – -битовая, а – ‑битовая переменные, возвращаемое значение является -битовым блокам, причем – длина свертки. (Обычно , поэтому соответствующие функции называют сжимающими.) Для получения значения сообщение предварительно дополняется битовой комбинацией и ‑битовой записью длины исходного сообщения так, чтобы длина сообщения, включая дополнение, была кратна . Затем сообщение разбивается на ‑битовые блоки ,,……, и к ним применяется следующая итерационная схема вычисления свертки (см. рис. 1):