Методы вычисления коллизий для хэш-функций

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

Метод опробования. Входные данные алгоритма: множества и отображение . Выходные данные алгоритма: коллизия , где и , или сообщение, что коллизия не найдена.

Шаг 1. Фиксируют и натуральное число ;

Шаг 2. Выбирают случайные различные элементы и вычисляют ;

Шаг 3. Упорядочивают массив пар по второй координате. Если при некоторых , то – коллизия, алгоритм заканчивает работу.
В противном случае алгоритм заканчивает работу с сообщением, что коллизия не найдена.

Алгоритм не всегда вычисляет коллизию. Докажем, что при естественных предположениях вероятность успеха не меньше чем . Справедливы следующие утверждения.

УТВЕРЖДЕНИЕ. Предположим, что при случайном выборе , который реализован на шаге 2, значение есть случайная величина с равномерным распределением на . Тогда вероятность того, что элементы множества попарно различны, не превосходит .

ДОКАЗАТЕЛЬСТВО. Искомая вероятность равна

.

Здесь использовано известное неравенство , которое выполняется при всех действительных . Неравенство эквивалентно неравенству , которое при натуральных выполняется тогда и только тогда, когда

.

Для последнее неравенство, как легко видеть, выполнено. Утверждение доказано.

Из доказанного утверждения следует, что вероятность успешного завершения алгоритма . Оценим сложность алгоритма. Наиболее трудоемким является шаг 3, где требуется, фактически, упорядочить массив из элементов множества . Известно, что это можно осуществить за операций сравнения элементов множества . Отсюда общая сложность алгоритма может быть оценена величиной операций сравнения элементов множества . При этом объем использованной памяти есть ячеек. Представленный алгоритм основан на соображениях, связанных с так называемым «парадоксом дня рождения», который в частном случае заключается в следующем. С вероятностью среди 23 случайных людей найдутся двое, у которых совпадают число и месяц рождения. Рассмотренный метод позволяет противнику построить коллизию для хэш-функции . При этом, если он располагает правильной подписью под сообщением , то он может подделать подпись под сообщением . Однако на практике подписью для противник не располагает.

Метод, использующий косметически отличающийся документ. Опишем ситуацию, которая возникает реально. Пусть противник является секретарем Алисы. Он готовит сообщение , которое Алиса готова подписать. Одновременно противник готовит сообщение , подпись которого Алисой может привести к негативным для нее последствиям. Далее при описании алгоритма будет встречаться выражение «документ косметически отличается от документа ». Это означает, что и имеют только внешние отличия, которые не влияют на содержание. Например, различное число пробелов между словами, некоторые слова переставлены или заменены синонимами и т.д.

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

Шаг 1. Зафиксируют и натуральные числа , для которых .

Шаг 2. Готовят различных вариантов документа , которые косметически отличаются от . Готовят вариантов документа , которые косметически отличаются от .

Шаг 3. Вычисляют и . Упорядочивают массив пар , где , по второй координате. Если , то и , алгоритм заканчивает работу. В противном случае алгоритм заканчивает работу с сообщением, что коллизия не найдена.

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

Пусть r=s=n. Вычислим вероятность p того, что имеется пара сообщений , таких, что .

Сначала вычислим вероятность противоположного события, то есть, что такой пары нет.

1 – p = = = .

Условия, налагаемые на n, при которых данная вероятность мала, приводятся в следующей теореме.

ТЕОРЕМА. Пусть N, n ® ¥, но ® t >0, тогда

р = (1 – e ) (1 + o(1)).

ДОКАЗАТЕЛЬСТВО.Используя формулу Стирлинга, имеем

1 – p = = =

= .

Используя разложение логарифма в ряд, получаем

ln(1- p) = [(2N-2n)ln(1- ) – (N-n)ln(1- )](1+ o(1)) =

= [(2N-2n)(– – + O()) – (N-n)(– - +

+ O()](1+o(1)) = – (1+o(1)) = -t (1+o(1)).

Таким образом,

1 – р = e (1 + o(1)),

и

р = (1 – e ) (1 + o(1)),

-метод Полларда вычисления коллизии. Рассмотрим -метод Полларда вычисления коллизии для отображения конечного множества в себя.

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

Очевидно, что коллизией здесь является пара , т.к. и . Если последовательность является чисто периодической, то коллизий она не содержит.

Входные данные алгоритма. Отображение . Выходные данные алгоритма. Коллизия для .

Шаг 1. Полагают , выбрают случайное , вычисляют и переходят к шагу 3.

Шаг 2. Полагают , вычисляют

.

Шаг 3. Если , то переходят к шагу 2. В противном случае переходят к шагу 4.

Шаг 4. Следующая процедура вычисляет коллизию .

Шаг 4.1. Полагают .

Шаг 4.2. Если , то при коллизии нет, переходят к шагу 1, при вычисляют коллизию . Алгоритм заканчивает работу. В противном случае переходят к шагу 4.3.

Шаг 4.3. Полагают .

Шаг 4.4. Если , то , в противном случае . Переходят к шагу 4.2.

Доказано:

· процедура в шаге 4 действительно вычисляет коллизию , если ;

· с вероятностью справедлива оценка ;

· с вероятностью сложность алгоритма равна ;

· объем использованной памяти равен ячеек.

Очевидно, что алгоритм не всегда сможет построить коллизию. Это так, когда – подстановочное преобразование множества . Тогда коллизий нет.

Эффективный способ распараллеливания -метода Полларда. Укажем значительно более эффективный способ распараллеливания -метода Полларда. Предположим, что для каждого , можно определить , которое обладает следующими свойствами:

1) легко определить принадлежность: ;

2) , то есть вероятность попадания в случайного элемента из равна .

Пусть имеется процессоров, которые работают параллельно, и один центральный процессор (ЦП). Идею алгоритма легко понять из рисунка.

Процессор с номером , вычисляет последовательность по правилу при случайном начальном до тех пор, пока элемент не попадет в . В память ЦП записывают . Набрав достаточно много таких троек, ЦП сортировкой находит и , для которых . Пусть не является элементом последовательности, вычисленной -ым процессором или не является элементом последовательности, вычисленной -ым процессором. Если, напротив, это имеет место, то говорят, что произошел «Робин Гуд». Из рисунка хорошо видно, что если «Робин Гуд» не имел места, то эта последовательность содержит коллизию . Легко понять, что вероятность «Робин Гуда» очень мала, и ею можно пренебречь. Параметр выбирается таким образом, чтобы минимизировать сложность вычислений.

Формальное описание алгоритма. Входные данные алгоритма: преобразование , где . Выходные данные алгоритма: коллизия для или сообщение, что коллизия не найдена.

Шаг 1. Выбирают , , и . Пусть . Определяют множество .

Шаг 2. -ый процессор выбирает случайное , полагает .

Шаг 3. Если , то в память ЦП записывается , переходят к шагу 2. В противном случае и , переходят к шагу 3.

Шаг 4. Когда число шагов (число членов последовательности), выполненных каждым процессором, окажется , ЦП сортирует массив троек по третьей координате. Если для элементов массива троек , , то переходят к шагу 5.

В противном случае алгоритм заканчивает работу с сообщением, что коллизия не найдена.

Шаг 5. ЦП строит коллизию с помощью следующей процедуры.

Шаг 5.1. Полагают .

Шаг 5.2. Полагают , вычисляют .

Шаг 5.3. Если , то переходят к шагу 5.2. Если и , то алгоритм заканчивает работу с сообщением, что коллизия не найдена, или шаг 5 повторяется для другой пары троек, найденной на шаге 4. Если и , то вычисляют . Это коллизия для . Алгоритм заканчивает работу.

Доказано:

сложность алгоритма равна операций;

объем использованной памяти равен ячеек.

Глава 48.