Хэшинг парадокс дня рождения
Так что я работаю над куском кода, который вычисляет хэши 2^4 наборы из 3 случайных простых чисел (менее 2 ^ 8). Затем продолжайте выбирать наборы из 3 составных чисел (менее 2 ^ 8), пока не появится набор {c1, c2, c3} со значением хеша, совпадающим с одним из предыдущих хешей (простыми), этот набор будет известен как {p1,p2,p3},
Из моего понимания атака на день рождения — это в основном поиск двух функций, которые дают одинаковый результат. Так я бы создал 2 функции? Один для простых чисел, а затем другой для составного? Каков наилучший способ сделать это? Я думаю, что PHP как язык.
Любая помощь будет принята с благодарностью.
Решение
Я думаю, что помещение ищет набор из любых 3 номеров < 2 ^ 8, который выдает то же значение хеш-функции, что и набор из 3 простых чисел, используя ту же хеш-функцию.
Не указан диапазон значений хеш-функции.
Атака на день рождения основана на том факте, что, поскольку диапазон значений хеша ограничен, метод грубой силы, который пытается хэшировать все комбинации из 3 чисел < 2 ^ 8 может привести к некоторым коллизиям с действительными значениями хеша задолго до того, как будут пробоваться все возможные комбинации. Однако в этом случае пробуют все комбинации из 3 чисел < 2 ^ 8 занимает всего 16777216 циклов, поэтому можно использовать полный метод грубой силы.
Программа может создать гистограмму всех возможных значений хеш-функции. Так как есть только 54 простых < 2 ^ 8, для генерации гистограммы для всех допустимых входных данных (3 простых числа) потребуется 54 ^ 3 = 157464 цикла.
Проверка на столкновения с использованием всех наборов из 3 чисел < 2 ^ 8 будет занимать 2 ^ 24 = 16777216 циклов, что не должно занять слишком много времени в зависимости от алгоритма хеширования.
Другие решения
Других решений пока нет …