Много близких столкновений, но нет полного столкновения

Позднее важное дополнение: теперь я понимаю, что код пытается найти коллизии для 64-битного $\имя_оператора{хэш}$ прием 64-битных сообщений. Если это $\имя_оператора{хэш}$ была биекцией, она не сталкивалась. Существует континуум между биекцией и случайной функцией, и нет гарантии, что $\имя_оператора{хэш}$ ведет себя в основном как позже. Наоборот, это внутренняя функция $f(x)=C\,x\oplus D\,x\bmod2^{64}$ не имеет правой диффузии. Это, $x\equiv x'\pmod{2^i}\предполагает f(x)\equiv f(x')\pmod{2^i}$, таким образом $f$ это плохая хеш-функция раунда. Это может объяснить, по крайней мере частично, трудности обнаружения коллизий методами, разработанными для случайных функций. В более позднем я предполагаю одно из:

• место для сообщений $х$ является $b$-бит с $b$ значительно больше, чем (64-битный вывод)
• мы пытаемся найти столкновения $х,х'$ такой, что $\operatorname{хэш}(p\mathbin\|x)=\operatorname{хэш}(p'\mathbin\|x')$ куда $р$ и $р'$ фиксированные различные префиксы, $х,х'$ находятся $b=64$-кусочек, $x\nex'$.

Я подозреваю, что еще одна важная проблема заключается в том, что в

Я заполняю (массивы) хешированием значений Int

это хэш постепенный Внутренние значения. Вполне возможно сделать такую ​​функцию, чтобы инкрементальные значения на большом интервале не сталкивались, и вполне возможно, что функция $\имя_оператора{хэш}$ поиск коллизий ведет себя так, поэтому любая попытка найти коллизии среди последовательных значений терпит неудачу.

В качестве примера функции без коллизий для ввода на небольшом интервале рассмотрим $H(x)=\left(263x+\left(\operatorname{MD5}(x)\bmod256\right)\right)\bmod2^{64}$. Он держит $H(x)-H(x')\equiv263(x-x')+(r-r')\pmod{2^{64}}$, с $r,r'\in[0,255]$ так как они получены как последний байт MD5; таким образом $\lvert r-r'\rvert<256$. Следовательно, если $x\nex'$, единственный способ получить $Н(х)=Н(х')$ в том, что $\lvert x-x'\rvert$ большой, по крайней мере $\lэтаж 2^{64}/263\rэтаж$, что не будет иметь место для последовательных $х$ в небольшом промежутке.

При попытке найти коллизии для такой недостаточно случайной хеш-функции $Ч$, простое решение состоит в том, чтобы найти коллизии для более случайной функции $x\mapstoH(G(x))$, построенный с помощью некоторой псевдослучайной вспомогательной биекции $G$, например $G(x)=G_2(G_1(G_0(x)))$ с $G_i(x)=k_i(x\oplus(x\gg\lceil b/3+1\rceil))\bmod2^b$ за $k_i$ случайный странный $b$-битовые константы [где $\гг$ правый сдвиг, и $b$ битовый размер $х$]. Однажды столкновение $х,х'$ находится с $ Н (G (х)) = Н (G (х')) $ но $x\nex'$, столкновение за $Ч$ является $G(х),G(х')$.

Одним из преимуществ поиска столкновений с помощью ро Полларда с выделенными точками (в отличие от метода в коде вопроса) является то, что его итеративный характер часто решает проблему недостаточно случайной функции, искомой для столкновений, без вспомогательного $G$; или относительно простой $G$ подойдет (здесь я думаю, что 1-битный поворот в обратной связи ро Полларда должен сделать, компенсируя отсутствие правильной диффузии). Кроме того, ро Полларда использует меньше памяти, поэтому работает для больших хэшей; а для быстрых хэш-функций это быстрее, потому что это удобно для кэширования.