Нахождение коллизий полиномиальных скользящих хэшей

А полиномиальный хэш определяет хэш как $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, все по модулю $2^n$ (то есть в $GF(2^n)$).

Для краткости пусть $с$ быть $к$ размерный вектор (инкапсулирующий все отдельные $c_n$ ценности).

Существуют ли особые значения для $с$ которые делают вероятность столкновения между двумя случайно выбранными $а$ больше чем $к/2^п$?

Я бы сказал, что нет. За $Н(с, а)$ равно вычислению многочлена (степени не выше $к$) в $а$. Таким образом, $Н_с(х)$ определяет многочлен степени не выше $к$. Позволять $H_{c,a}(x) = H_c(x) - H_c(a)$; нули $H_{c,a}$ именно те точки, где $H_c(x) = H_c(a)$, и их может быть не более $к$ такие нули. Таким образом, для любого ненулевого $с$, два случайно выбранных $а,а'$ имеют $Н(а) = Н(а')$ с вероятностью $\le k/2^n $.

Однако, этот крипто вызов CTF кажется, спорит с определенным $с$ действительно производят столкновения, и это решение объясняет и демонстрирует это (к сожалению, большая часть объяснений на китайском языке). Где моя ошибка?

Это кольцо имеет делители нуля, поэтому ответ отличается от ответа над полями.

Позволять $H(a)-H(a')=c_1 a^{k-1}+c_2 a^{k-2}+\cdots+c_k,$ и разреши $j$ — наибольшее неотрицательное целое число такое, что $2^j$ делит $gcd(c_1,\ldots,c_k).$

Требовать: Позволять $j$ как указано выше, то многочлен $H(а)-H(а')$ может иметь $к\раз 2^{j}$ корней, что приводит к вероятности столкновения $$\frac{k}{2^{nj}}.$$

Доказательство: Если коэффициенты разностного многочлена имеют НОД, кратное $2^j$ тогда все значения многочлена находятся в подмножестве (которое является идеалом) $$2^j \mathbb{Z}_{2^n}=\{2^j u: u \in \mathbb{Z}_{2^n}\}.$$ Это означает, что разностный полином имеет вид $2^j г(а)$ для некоторого многочлена с НОД, равным 1. Поэтому достаточно для $г(а)$ принимать значения в $2^{nj}\mathbb{Z}_{2^n}$ за $2^j г(а)$ принять нулевое значение. Это означает, что каждый ноль $г(а)$ дублируется $2^j$ раз, чтобы стать нулем разностного полинома, поэтому вероятность того, что разностный полином примет нулевое значение, теперь равна $$ \frac{k 2^j}{2^n}=\frac{k}{2^{nj}}. $$

Пример из [Калькулятора магмы][1] градуса $к=2$ многочлен, который имеет 2 корня и один, где $j=2,$ который имеет $к 2^j=8$ корни.

код:

Z2to6:=Целоекольцо(2^6); Z2to6;
R<a>:=Многочленное кольцо(Z2to6); Р;
{* Z2to6!(a^2+63*a): a в Z2to6 *};
{* Z2to6!(4*(a^2+63*a)): a в Z2to6 *};}

вывод:

Одномерное полиномиальное кольцо в более целочисленном кольце (64)
{* 0^^2, 2^^2, 4^^2, 6^^2, 8^^2, 10^^2, 12^^2, 14^^2, 16^^2, 18^^ 2, 20^^2,
22^^2, 24^^2, 26^^2, 28^^2, 30^^2, 32^^2, 34^^2, 36^^2, 38^^2, 40^^2, 42^^2,
44^^2, 46^^2, 48^^2, 50^^2, 52^^2, 54^^2, 56^^2, 58^^2, 60^^2, 62^^2 * }`
{* 0^^8, 8^^8, 16^^8, 24^^8, 32^^8, 40^^8, 48^^8, 56^^8 *}```

Второй многочлен $4(а^2+63а)$ имеет НОД 4, поэтому у него 8 корней, а не 2.

Обозначение списка магмы 0 ^ ^ 8 означает, что элемент 0 появляется в списке 8 раз.




  [1]: http://magma.maths.usyd.edu.au/calc/