Găsirea coliziunilor hashurilor polinomiale rulante

A hash polinom definește un hash ca $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, toate modulo $2^n$ (adică în $GF(2^n)$).

Pentru concizie, lăsați $c$ fi a $k$ vector dimensional (încapsulând tot individul $c_n$ valori).

Există valori speciale pentru $c$ care fac probabilitatea de ciocniri între două alese aleatoriu $a$ mai mare ca $k/2^n$?

Aș susține că nu există. Pentru $H(c, a)$ este egal cu evaluarea unui polinom (cel mult de grad $k$) la $a$. Prin urmare, $H_c(x)$ definește un polinom cu grad cel mult $k$. Lăsa $H_{c,a}(x) = H_c(x) - H_c(a)$; zerourile ale $H_{c,a}$ sunt tocmai punctele în care $H_c(x) = H_c(a)$, și nu poate fi mai mult decât $k$ astfel de zerouri. Astfel, pentru orice non-zero $c$, două alese aleatoriu $a,a'$ avea $H(a) = H(a')$ cu probabilitate $\le k/2^n $.

In orice caz, această provocare cripto CTF pare a argumenta sigur $c$ produc coliziuni și această soluție explică și o demonstrează (din păcate, cea mai mare parte a explicației este în chineză). Unde este greșeala mea?

Acest inel are divizori zero, astfel încât răspunsul este diferit de peste câmpuri.

Lăsa $H(a)-H(a')=c_1 a^{k-1}+c_2 a^{k-2}+\cdots+c_k,$ si lasa $j$ să fie cel mai mare număr întreg nenegativ astfel încât $2^j$ desparte $gcd(c_1,\ldots,c_k).$

Revendicare: Lăsa $j$ fi ca mai sus, apoi polinomul $H(a)-H(a')$ poate avea $k\ori 2^{j}$ rădăcini, conducând la o probabilitate de coliziune de $$\frac{k}{2^{n-j}}.$$

Dovada: Dacă coeficienții polinomului de diferență au un mcd divizibil cu $2^j$ atunci toate valorile polinomului sunt în submulțime (care este un ideal) $$2^j \mathbb{Z}_{2^n}=\{2^j u: u \in \mathbb{Z}_{2^n}\}.$$ Aceasta înseamnă că polinomul diferență este de forma $2^j g(a)$ pentru un polinom cu gcd egal cu 1. Prin urmare, este suficient pentru $g(a)$ a lua valori $2^{n-j}\mathbb{Z}_{2^n}$ pentru $2^j g(a)$ pentru a lua valoarea zero. Aceasta înseamnă că fiecare zero de $g(a)$ este duplicat $2^j$ ori pentru a fi zero al polinomului diferență, astfel încât probabilitatea ca polinomul diferențial să ia valoarea zero este acum $$ \frac{k 2^j}{2^n}=\frac{k}{2^{n-j}}. $$

Exemplu de la [Magma Calculator][1] de un grad $k=2$ polinom, care are 2 rădăcini și una unde $j=2,$ care are $k 2^j=8$ rădăcini.

cod:

Z2to6:=Integer(2^6); Z2to6;
R<a>:=PolynomialRing(Z2to6); R;
{* Z2to6!(a^2+63*a): a în Z2to6 *};
{* Z2to6!(4*(a^2+63*a)): a în Z2to6 *};}

ieșire:

Inel polinom univariat într-un inel peste Integer(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 *}```

Al doilea polinom $4(a^2+63a)$ are un mcd de 4, deci are 8 rădăcini nu 2.

Notația 0^^8 a listei de magmă înseamnă că elementul 0 apare de 8 ori în listă.




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