Парадокс хеширования дня рождения

Итак, я работаю над фрагментом кода, который вычисляет хэши 2^4 наборов из 3 случайных простых чисел (менее 2 ^ 8). Затем продолжайте выбирать наборы из 3 составных чисел (меньше 2 ^ 8), пока не появится набор {c1, c2, c3} со значением хеш-функции, совпадающим с одним из предыдущих хэшей (простых), этот набор будет известен как {p1,p2,p3}.

Насколько я понимаю, атака на день рождения в основном заключается в поиске двух функций, дающих один и тот же результат. Итак, я бы создал 2 функции? Один для простых чисел, а другой для составных? Как лучше всего это сделать? Я думаю PHP как язык.

Любая помощь будет принята с благодарностью.


c++ php hash birthday-paradox
person LifeofBob    schedule 20.11.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, что предпосылка ищет набор из любых 3 чисел ‹ 2 ^ 8, который дает то же значение хеш-функции, что и набор из 3 простых чисел, используя ту же хеш-функцию.

Не указан диапазон значения хеш-функции.

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

Программа может создать гистограмму всех возможных значений хеш-функции. Поскольку имеется только 54 простых числа ‹ 2^8, создание гистограммы для всех допустимых входных данных (3 простых числа) займет 54^3 = 157464 цикла.

Проверка коллизий с использованием всех наборов из 3 чисел ‹ 2^8 займет 2^24 = 16777216 циклов, что не должно занять слишком много времени в зависимости от алгоритма хеширования.

person rcgldr    schedule 20.11.2015