Tìm va chạm của băm cán đa thức

Một hàm băm đa thức định nghĩa một hàm băm là $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, tất cả theo modulo $2^n$ (nghĩa là trong $GF(2^n)$).

Để cho ngắn gọn, hãy để $c$ là một $k$ vectơ chiều (gói gọn tất cả các cá nhân $c_n$ các giá trị).

Có giá trị cụ thể cho $c$ làm cho xác suất va chạm giữa hai lựa chọn ngẫu nhiên $a$ lớn hơn $k/2^n$?

Tôi sẽ tranh luận rằng không có. Vì $H(c, a)$ bằng với việc đánh giá một đa thức (tối đa là bậc $k$) tại $a$. Như vậy, $H_c(x)$ định nghĩa một đa thức có bậc nhiều nhất $k$. Để cho $H_{c,a}(x) = H_c(x) - H_c(a)$; số không của $H_{c,a}$ chính xác là những điểm mà $H_c(x) = H_c(a)$, và không thể có nhiều hơn $k$ số không như vậy. Do đó, đối với mọi khác không $c$, hai được chọn ngẫu nhiên $a,a'$ có $H(a) = H(a')$ với xác suất $\le k/2^n $.

Tuy nhiên, thử thách CTF tiền điện tử này dường như tranh luận nhất định $c$ làm tạo ra va chạm, và giải pháp này giải thích và chứng minh điều đó (không may là hầu hết các lời giải thích đều bằng tiếng Trung Quốc). Đâu là sai lầm của tôi?

Chiếc nhẫn này không có ước số nào nên câu trả lời khác với trên các trường.

Để cho $H(a)-H(a')=c_1 a^{k-1}+c_2 a^{k-2}+\cdots+c_k,$ và để cho $j$ là số nguyên không âm lớn nhất sao cho $2^j$ phân chia $gcd(c_1,\ldots,c_k).$

Yêu cầu: Để cho $j$ như trên thì đa thức $H(a)-H(a')$ có thể có $k\times 2^{j}$ rễ, dẫn đến xác suất va chạm của $$\frac{k}{2^{n-j}}.$$

Bằng chứng: Nếu các hệ số của đa thức hiệu có gcd chia hết cho $2^j$ thì tất cả các giá trị của đa thức đều nằm trong tập hợp con (là một lý tưởng) $$2^j \mathbb{Z}_{2^n}=\{2^j u: u \in \mathbb{Z}_{2^n}\}.$$ Điều này có nghĩa là đa thức sai phân có dạng $2^j g(a)$ đối với một số đa thức với gcd bằng 1. Do đó, nó là đủ cho $g(a)$ lấy các giá trị trong $2^{n-j}\mathbb{Z}_{2^n}$ vì $2^j g(a)$ để nhận giá trị bằng không. Điều này có nghĩa là mỗi số không của $g(a)$ được nhân đôi $2^j$ lần bằng 0 của đa thức sai phân nên xác suất để đa thức sai phân nhận giá trị bằng 0 bây giờ là $$ \frac{k 2^j}{2^n}=\frac{k}{2^{n-j}}. $$

Ví dụ từ [Máy ​​tính Magma][1] độ $k=2$ đa thức, có 2 gốc và một trong đó $j=2,$ trong đó có $k 2^j=8$ rễ.

mã số:

Z2to6:=IntegerRing(2^6); Z2to6;
R<a>:=Đa thứcRing(Z2to6); R;
{* Z2to6!(a^2+63*a): a trong Z2to6 *};
{* Z2to6!(4*(a^2+63*a)): a trong Z2to6 *};}

đầu ra:

Vòng đa thức đơn biến trong một IntegerRing trên (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 *}```

đa thức thứ hai $4(a^2+63a)$ có gcd là 4 nên nó có 8 gốc chứ không phải 2.

Ký hiệu danh sách magma 0^^8 có nghĩa là phần tử 0 xuất hiện 8 lần trong danh sách.




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