ค้นหาการชนกันของแฮชกลิ้งพหุนาม

ก แฮชพหุนาม กำหนดแฮชเป็น $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, โมดูโล่ทั้งหมด $2^n$ (นั่นคือใน $GF(2^n)$).

เพื่อความกระชับ ให้ $ค$ เป็น $k$ เวกเตอร์มิติ (ห่อหุ้มบุคคลทั้งหมด $c_n$ ค่า).

มีค่าเฉพาะสำหรับ $ค$ ที่ทำให้ความน่าจะเป็นของการชนกันระหว่างสองรายการที่สุ่มเลือก $a$ มากกว่า $k/2^n$?

ฉันจะเถียงว่าไม่มี สำหรับ $H(ค, ก)$ เท่ากับการประเมินพหุนาม (ของดีกรีมากที่สุด $k$) ที่ $a$. ดังนั้น, $H_c(x)$ กำหนดพหุนามที่มีดีกรีเป็นส่วนใหญ่ $k$. อนุญาต $H_{c,a}(x) = H_c(x) - H_c(a)$; เลขศูนย์ของ $H_{c,a}$ เป็นจุดที่แน่นอน $H_c(x) = H_c(ก)$และสามารถมีได้ไม่เกิน $k$ เลขศูนย์ดังกล่าว ดังนั้นสำหรับค่าที่ไม่ใช่ศูนย์ $ค$สองคนสุ่มเลือก $a,a'$ มี $H(a) = H(a')$ ด้วยความน่าจะเป็น $\le k/2^n $.

อย่างไรก็ตาม, ความท้าทาย crypto CTF นี้ ดูเหมือนจะโต้แย้งบางอย่าง $ค$ ทำให้เกิดการชนกันและ วิธีนี้จะอธิบาย และสาธิตให้ดู (ขออภัย คำอธิบายส่วนใหญ่เป็นภาษาจีน) ความผิดพลาดของฉันอยู่ที่ไหน

วงแหวนนี้มีตัวหารเป็นศูนย์ ดังนั้นคำตอบจึงแตกต่างจากช่องอื่นๆ

อนุญาต $H(a)-H(a')=c_1 a^{k-1}+c_2 a^{k-2}+\cdots+c_k,$ และปล่อยให้ $เจ$ เป็นจำนวนเต็มที่ไม่เป็นลบที่มากที่สุดเช่นนั้น $2^j$ แบ่ง $gcd(c_1,\ldots,c_k).$

เรียกร้อง: อนุญาต $เจ$ เป็นไปตามข้างต้น จากนั้นเป็นพหุนาม $H(a)-H(a')$ สามารถมี $k\คูณ 2^{j}$ รากที่นำไปสู่ความน่าจะเป็นของการชนกันของ $$\frac{k}{2^{n-j}}.$$

การพิสูจน์: หากค่าสัมประสิทธิ์ของผลต่างพหุนามมี gcd หารด้วย $2^j$ จากนั้นค่าทั้งหมดของพหุนามจะอยู่ในเซตย่อย (ซึ่งเป็นอุดมคติ) $$2^j \mathbb{Z}_{2^n}=\{2^j u: u \in \mathbb{Z}_{2^n}\}.$$ ซึ่งหมายความว่าพหุนามความแตกต่างอยู่ในรูปแบบ $2^j g(a)$ สำหรับพหุนามบางตัวที่มี gcd เท่ากับ 1 ดังนั้นจึงเพียงพอสำหรับ $ก(ก)$ เพื่อรับค่าใน $2^{n-j}\mathbb{Z}_{2^n}$ สำหรับ $2^j g(a)$ เพื่อรับค่าเป็นศูนย์ ซึ่งหมายความว่าแต่ละศูนย์ของ $ก(ก)$ มีการทำซ้ำ $2^j$ ครั้งเป็นศูนย์ของผลต่างพหุนาม ดังนั้นความน่าจะเป็นที่ผลต่างพหุนามจะมีค่าเป็นศูนย์คือ $$ \frac{k 2^j}{2^n}=\frac{k}{2^{n-j}} $$

ตัวอย่าง จาก [Magma Calculator][1] ในระดับหนึ่ง $k=2$ พหุนามซึ่งมี 2 รากและอีกหนึ่งตำแหน่ง $j=2,$ ซึ่งมี $k 2^j=8$ ราก.

รหัส:

Z2to6:=IntegerRing(2^6); Z2to6;
R<a>:=PolynomialRing(Z2to6); ร;
{* Z2to6!(a^2+63*a): a ใน Z2to6 *};
{* Z2to6!(4*(a^2+63*a)): a ใน Z2to6 *};}

เอาต์พุต:

วงแหวนโพลิโนเมียลเดียวใน IntegerRing มากกว่า (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(a^2+63a)$ มี gcd เท่ากับ 4 ดังนั้นจึงมี 8 รูท ไม่ใช่ 2

สัญกรณ์รายการหินหนืด 0^^8 หมายถึงองค์ประกอบ 0 ปรากฏขึ้น 8 ครั้งในรายการ




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