Хэшинг парадокс дня рождения

Question

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

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

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

Answer 1

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

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

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

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

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