ชนใกล้แต่ไม่ชนเต็มจำนวน

การเพิ่มที่สำคัญในภายหลัง: ตอนนี้ฉันรู้แล้วว่าโค้ดพยายามค้นหาการชนกันของ 64 บิต $\operatorname{hash}$ ยอมรับข้อความ 64 บิต ถ้าอย่างนั้น $\operatorname{hash}$ เป็นการคัดค้านมันจะไม่ชนกัน มีความต่อเนื่องระหว่าง bijection และฟังก์ชั่นสุ่มและไม่มีการประกัน $\operatorname{hash}$ พฤติกรรมส่วนใหญ่เหมือนในภายหลัง ตรงกันข้าม มันเป็นหน้าที่ภายใน $f(x)=C\,x\oplus D\,x\bmod2^{64}$ ไม่มีการแพร่กระจายที่ถูกต้อง นั่นคือ, $x\equiv x'\pmod{2^i}\หมายถึง f(x)\equiv f(x')\pmod{2^i}$, ดังนั้น $f$ เป็นฟังก์ชันรอบแฮชที่ไม่ดี สิ่งนี้อาจอธิบายความยากในการค้นหาการชนด้วยวิธีการที่ออกแบบมาสำหรับฟังก์ชันสุ่ม ในภายหลังฉันถือว่าหนึ่งใน:

• พื้นที่ข้อความสำหรับ $x$ เป็น $ข$-บิตด้วย $ข$ มีขนาดใหญ่กว่า (เอาต์พุต 64 บิต)
• เราพยายามหาการชนกัน $x,x'$ ดังนั้น $\operatorname{hash}(p\mathbin\|x)=\operatorname{hash}(p'\mathbin\|x')$ ที่ไหน $p$ และ $p'$ ได้รับการแก้ไขคำนำหน้าที่แตกต่างกัน $x,x'$ เป็น $b=64$-นิดหน่อย, $x\ne x'$.

ฉันสงสัยว่าประเด็นสำคัญอีกอย่างคือใน

ฉันเติมข้อมูล (อาร์เรย์) โดยแฮชค่า Int

มันถูกแฮช เพิ่มขึ้น ค่า Int ค่อนข้างเป็นไปได้ที่จะสร้างฟังก์ชันในลักษณะที่ค่าที่เพิ่มขึ้นในช่วงเวลาใหญ่ๆ ไม่ชนกัน และเป็นไปได้ทีเดียวที่ฟังก์ชัน $\operatorname{hash}$ การค้นหาการชนกันจะทำงานเช่นนั้น ดังนั้นความพยายามใด ๆ ที่จะค้นหาการชนกันระหว่างค่าที่ต่อเนื่องกันจึงล้มเหลว

พิจารณาตัวอย่างฟังก์ชันที่ไม่มีการชนกันของอินพุตในช่วงเวลาสั้นๆ $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\ne x'$วิธีเดียวที่จะได้รับ $H(x)=H(x')$ คือว่า $\lvert x-x'\rvert$ มีขนาดใหญ่เป็นอย่างน้อย $\lfloor 2^{64}/263\rfloor$ซึ่งจะไม่เกิดขึ้นติดต่อกัน $x$ ในช่วงเวลาเล็กน้อย

เมื่อพยายามค้นหาการชนกันของฟังก์ชันแฮชแบบสุ่มที่ไม่เพียงพอ $H$การแก้ไขง่ายๆ คือการค้นหาการชนกันของฟังก์ชันที่สุ่มมากขึ้น $x\mapsto H(G(x))$สร้างขึ้นโดยใช้ bijection เสริมแบบสุ่มหลอก $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$ จับจด แปลก $ข$- ค่าคงที่บิต [โดยที่ $\gg$ เป็นกะขวาและ $ข$ คือขนาดบิตของ $x$]. เมื่อเกิดการชนกัน $x,x'$ พบกับ $H(G(x))=H(G(x'))$ แต่ $x\ne x'$, การชนกันเพื่อ $H$ เป็น $ก(x),ก(x')$.

ข้อดีประการหนึ่งของการค้นหาการชนกันของ Pollard's rho ที่มีจุดแตกต่าง (แทนที่จะเป็นวิธีการในรหัสของคำถาม) คือลักษณะการวนซ้ำมักจะแก้ปัญหาของฟังก์ชันสุ่มที่ไม่เพียงพอซึ่งค้นหาการชนกันโดยไม่มีตัวช่วย $G$; หรือค่อนข้างง่าย $G$ จะทำ (ที่นี่ฉันคิดว่าการหมุน 1 บิตในข้อเสนอแนะของ Pollard's rho ควรทำเพื่อชดเชยการขาดการแพร่กระจายที่ถูกต้อง) นอกจากนี้ โรของพอลลาร์ดยังใช้หน่วยความจำน้อยกว่า ดังนั้นจึงใช้ได้กับแฮชที่ใหญ่ขึ้น และสำหรับฟังก์ชันแฮชที่รวดเร็ว ก็ยิ่งเร็วขึ้นเนื่องจากเป็นมิตรกับแคช