Глава 39.

Xэш-функции

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

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

,

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

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

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 удовлетворяют соотношениям для любого  

Е D() = , D Е() = .

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

С = D(h(М)).

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

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

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

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

х k

DES

ключ

Z

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

2)    А,  = ...,

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

 = h(,)

 =h(, )

………………..

 =h(,).

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

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

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

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

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

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

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

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

.

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

39.2. Хэш-функция Шаумома, ван Хейста, Пфицмана

Она основана на возведении в степень в конечном простом поле , где и – простое число. Пусть примитивный элемент в , и . Рассмотрим отображение

,

определенное равенством

.

Доказано, что эффективный алгоритм вычисления коллизии для функции H существует тогда и только тогда, когда существует эффективный алгоритм вычисления такого , что .

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

39.3. Хэш-функции и блочные шифры

Рассмотрим один общий метод построения хэш-функций. Пусть – любая функция, V_j – векторное пространство над полем F₂

при некоторых натуральных . Требуется построить функцию

.

Сообщение разбивается на блоки

,

где . Если длина сообщения в битах не кратна , то последний блок дополняется таким образом, что . Тогда , где последовательность вычисляется по следующему правилу. Блок фиксирован, например, . Далее

.

Функцию часто получают применением стойкого блочного шифра. Основная идея использования здесь шифра заключается в том, что трудно вычислить ключ, зная открытый текст и соответствующий ему шифртекст. То есть трудно восстановить из равенства , где известны. Иначе говоря, функция является однонаправленной при фиксированном . Пусть для дальнейшего и имеется блочный шифр . Тогда в качестве при берут

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

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

и

при постоянном это условие не выполняется.