https://nsucrypto.nsu.ru/archive/2021/round/2/task/4/#data
แนวคิดหลักของแบบฝึกหัด: ค้นหารหัสลับ $k$, มีการเข้าถึง $Enc(x, d) = Enc(x^d \bmod n), n = 1060105447831$.
ฉันจะถือว่า $0 < k < n.$
$Enc$ เป็นแฮชปกติ โดยจะส่งกลับเอาต์พุตเดียวกันกับอินพุตที่เกี่ยวข้อง
ฉันต้องการหาการชนแบบนั้น $แฮช(k, 1) = แฮช(x, d)$นี่จะหมายความว่าฉันพบ $k = x^d \bmod n.$
ความคิดแรกของฉันคือการค้นหาตัวกำเนิดของกลุ่มวัฏจักรของ $Z_{1060105447831}$แต่ฉันพบว่า 2 และ 3 และไม่มีอะไรใน 20,000 หมายเลขแรกที่ใช้ได้ ฉันจะใช้เครื่องกำเนิดไฟฟ้าเพื่อตรวจสอบการชนกัน $k$. ฉันรู้ $2^{40} > n$. นอกจากนี้ยังช่วยให้ใช้ตัวสร้างสำหรับคำนวณลอการิทึมแยกและหาค่า k ได้เร็วขึ้น ฉันต้องการทดสอบ แต่รู้สึกว่าปัญหาเกิดจากการตรวจสอบด้วยตนเองในใจ
การโจมตีวันเกิดใช้ไม่ได้กับแฮช 128 บิต ถ้าฉันต้องการความน่าจะเป็นและประสิทธิภาพที่ดี
ฉันยังพยายามรับค่าแฮชของค่าเล็กน้อย Enc(2,1), Enc(3,1) ... Enc(10, 1) เพื่อดูว่าแฮชมีความสัมพันธ์ที่ซ่อนอยู่ระหว่างเอาต์พุตหรือไม่
นอกจากนี้ $\phi(n)$ มีตัวประกอบที่ดีของจำนวนน้อย
ฉันจะเพิ่มรายละเอียดที่สำคัญใหม่ ๆ
ควรเลือกค่าอะไรเพื่อช่วยหาค่า k? พวกเขามีความสำคัญหรือไม่? ตัวสร้างไม่มีประโยชน์ ฉันไม่สามารถใช้อัลกอริทึมที่เร็วกว่าสำหรับการยกกำลังแบบแยกส่วนได้ เพราะทั้งหมดที่ฉันได้รับคือสตริง 128 บิต สิ่งที่ฉันทำได้คือตรวจสอบว่าตัวเลขหรือพลังของตัวเลขมีการเข้ารหัสเท่ากับจำนวนลับหรือไม่ $k$