Xэш-функции

Основные понятия

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

,

где М некоторое множествою.

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

1) для данного легко вычислить

2) для данного трудно вычислить такое, что

3) для данного трудно вычислить , , такое, что .

Отображение , удовлетворяющее требованиям 1) и 2), является однонаправленным. Иногда вместо 3) требуют выполнения более сильного свойства.

трудно вычислить пару , для которой .

Пара элементов множества (пара сообщений), о которой идет речь в называется коллизией для отображения . Т.к. мощность больше мощности , то допускает коллизии.

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

Как правило, в качестве берут множество I всех слов конечной длины в некотором алфавите I = {i ,...,i }, а в качестве множество I всех слов длины L алфавита. На практике, чаще всего I=F₂, I = – множество слов конечной длины в двоичном алфавите F₂={0,1}. От функции H: I ®I^L, требуют, чтобы она обладала свойством: значения H на словах, которые даже имеют отличие друг от друга только в одном знаке, дают значительно отличающиеся хэш-значения. Тогда, получив на приемном конце сообщение и его хэш (), можно вычислить значение хэш от сообщения, сравнить с полученным хэш по каналу связи, и подтвердить или опровергнуть, что сообщение не искажено.

Если функция H зависит также от ключа kÎK, то помимо проверки целостности добавление значения хэш к сообщению подтверждает истинность сообщения. Такой способ подтверждения истинности называется кодом аутентификации (Message Autentification Code – MAC). Однако, такое подтверждение истинности еще не является электронной подписью. Подтверждение истины называется подписью, если ее могут проверить все, не знающие ключи. Например, в суде можно поверить истинность, не раскрывая ключи. Приведенный выше способ проверки подлинности сообщения непригоден, так как влечет раскрытие ключа. Для того, чтобы код аутентификации стал электронной подписью сообщения, необходимо использовать хэш-функции с дополнительными свойствами. Например, использовать систему с открытым ключом. Напомним вкратце суть электронной подписи. Пусть у корреспондента В имеются два алгоритма Е и D , каждый из которых преобразует слово из в слово из и каждый определен на . Первый алгоритм известен всем, а второй – только владельцу В. Обладание алгоритмом D однозначно (юридически) определяет корреспондента В. Считаем, что Е и D удовлетворяют соотношениям для любого a Î

Е D (a) = a, D Е (a) = a.

Тогда электронной подписью документа МÎ А называется

С = D (h(М)).

Проверка подписи под документом М возможна любым лицом, у которого есть Е . Для этого проверяющий вычисляет H (М) (Н() – известна всем, М проверяющий получает вместе с подписью С). Второй шаг проверки – вычисление

Е (С) = Е D (H(М)) = H(М).

Если вычисленное значение хэш от Мсовпало с результатом применения алгоритмов Е к С, то подпись В считается подтвержденной (даже в суде).

Пример. Обычно хэш h() строится следующим образом. Выбирается функция h: ´ ® , удовлетворяющая свойствам 1-3. Например, когда длина L хэш была 64 бита, то брали следующую схему

х k

DES

ключ

Z

z = h(x,k) = DES (x).

2) " a Î А , a = a ...a ,

где длина блока a равна L, а блок a дополнен до блока длины L (если это необходимо). Н(a) вычисляется по следующему алгоритму.

b = h(a ,a )

b =h(b ,a )

………………..

b =h(b ,a ).

Известно следующее

УТВЕРЖДЕНИЕ. Пусть – конечные множества, и . Задано произвольное отображение . Пусть для любого имеется эффективный алгоритм вычисления такого, что (если существует), при этом алгоритм задает равномерное распределение на множестве таких при всех . Тогда имеется эффективный алгоритм вычисления коллизии для функции H.

ДОКАЗАТЕЛЬСТВО. Обозначим через алгоритм обращения , о котором идет речь в формулировке леммы. То есть для некоторого такого, что . Сформулируем алгоритм вычисления коллизии.

Входные данные алгоритма: хэш-функция , алгоритм . Выходные данные алгоритма: коллизия для H.

Шаг 1. Выбрать случайное , вычислить .

Шаг 2. Вычислить .

Шаг 3. Если , то перейти к шагу 1; в противном случае – коллизия для H. Алгоритм заканчивает работу.

Оценим среднее число прохождений алгоритма через шаг 1. Имеем вероятностную схему, исходами которой являются пары , где . Обозначим через множество , для которых . Заметим, что число классов не больше . Тогда вероятность исхода равна . Благоприятными являются исходы , где . Найдем вероятность неблагоприятного исхода. Она равна

.

Отсюда вероятность благоприятного исхода не меньше . Следовательно, среднее число прохождений алгоритма через шаг 1 не превосходит 2, то есть этот алгоритм эффективен.