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

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

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

Шаг 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.