การยกกำลังของ Linear Congruential Generators

Linear Congruential Generators ซึ่งเป็นคลาสของเครื่องกำเนิดแบบสุ่มหลอกที่มีกฎแบบเรียกซ้ำ

$x_{n+1}\equiv a\cdot x_n +b\ \ (\mod m)$, $a,b,x_n\ใน Z/mZ$, $m,n\ใน N$

ถือว่าไม่เหมาะสมสำหรับใช้ในการเข้ารหัส เป็นค่าคงที่ $a$, $ข$ อาจอนุมานได้จากผลลัพธ์ชุดเล็กๆ $x_n$. ตอนนี้เมื่อคุณเลือก $m=p-1$ สำหรับนายกแปลก ๆ $p$ลำดับ $(x_n)_{n\ใน N}$ อาจอยู่เป็นเลขยกกำลังของตัวสร้างบางตัว $g$ ของกลุ่มวงจรทวีคูณ $Z/pZ^*$, เช่น $y_n:=g^{x_n}, n\ใน N$:

$y_{n+1}\equiv g^{x_{n+1}}\equiv g^{a\cdot x_n+b}\equiv (g^{x_n})^a\cdot g^b\equiv y_n ^a\cdot g^b\ (\mod p)$

นี่คือซีรีย์พลังงานที่เทียบเท่ากัน

การกระจายที่เท่าเทียมกันมาพร้อมกับระยะเวลาสูงสุด เงื่อนไขระยะเวลาสูงสุด $m$ ของลำดับ $(y_n)_{n\ใน N}$ กำหนดโดยทฤษฎีบทของ Knuth

1. $gcd(m,b)=1$
2. สำหรับการสลายตัวที่สำคัญ $m=:\prod p_i^{\alpha_i}$ และปัจจัยสำคัญทั้งหมด $p_i$: $\ \ \ p_i/(a-1)$
3. $m\equiv 0\ (\mod 4) \หมายถึง a-1\equiv 0\ (\mod 4)$

เนื่องจาก $m=p-1$ เท่ากันและมีจำนวนเฉพาะที่มีรูปร่างน้อยมาก $p=2^k+1$, องค์ประกอบทั่วไปที่ง่ายที่สุดของ $p-1$ จากจำนวนเฉพาะจะเป็น $p-1=2^k\cdot p'$, $k\geq 1$ กับ $p'$ นายกรัฐมนตรีอีกคน

ตามเงื่อนไขที่ 2 ตัวเลือกที่น้อยที่สุดของ $a$ คือโดย $a-1=2\cdot p'$. เพื่อหลีกเลี่ยงกรณีเล็กน้อย $a-1=m$, $k\geq 2$ เป็นสิ่งที่จำเป็น ด้วยเหตุนี้เราจึงเข้าสู่เงื่อนไขที่ 3 ดังนั้น $a-1$ มีปัจจัยอย่างน้อยสองเท่า $2$. อีกครั้ง จำเป็นต้องหลีกเลี่ยงกรณีเล็กน้อย $k\geq 3$.

ตอนนี้คู่หลัก $(พี,พี')$ สมการเชิงเส้น $p=8p'+1$ ช่วยให้ทางเลือกที่ไม่สำคัญ $a-1=4p'$ และด้วยชุดพลังนี้ $(y_n)$ อาจมีระยะเวลาสูงสุด $m$.

คำถาม: เนื่องจากเรามี 3 พารามิเตอร์ที่ซ่อนอยู่ $g, g^a,g^b$ และการหาลอการิทึมในกลุ่มคูณถือว่ายาก สามารถสุ่มลำดับ $(y_n){n\ใน N}$ ถือว่าปลอดภัยสำหรับใช้ในการเข้ารหัส มีทางเลือกที่ดีกว่าสำหรับค่าคงที่หรือไม่ $a$?

แก้ไข $g$ จริงๆ แล้วไม่สำคัญเท่าพารามิเตอร์ ขณะที่เรายกกำลังให้ $a$ซึ่งนอกจากนี้ $p$ ไม่เป็นที่รู้จักจากเอาต์พุต เช่น พารามิเตอร์ที่ไม่รู้จักคือ $(p, a, g^b)$ .

ข้อสังเกตหลายประการ:

• รักษา $a$ ความลับเป็นสิ่งสำคัญ ถ้าศัตรูรู้และเห็น $y_i, y_{i+1} = (y_i^a) \cdot g^b$เขาสามารถคำนวณได้ $g^b = y_{i+1} \cdot y_i^{-a}$แล้วดำเนินการต่อและคำนวณลำดับที่เหลือ

คุณอาจพูดว่า "แต่เราคิดว่าบันทึกแยกนั้นยาก" - แต่คุณก็แนะนำเช่นกัน $p = 8p'+1$ และ $a-1 = 4p'$, นั่นคือ, $a = (p+1)/2$; ที่จะทำให้ฟื้นตัวได้ $a$ ง่าย.

• การทดสอบความเป็นกรดที่แท้จริงสำหรับ CSRNG คือว่าฝ่ายตรงข้าม (ซึ่งรู้ทุกอย่างยกเว้นค่าลับ) สามารถแยกแยะผลลัพธ์ของ CSRNG จากลำดับสุ่มที่แท้จริงด้วยการกระจายความน่าจะเป็นที่เหมือนกันได้หรือไม่

ทีนี้ ถ้า $g$ เป็นตัวกำเนิดของทั้งกลุ่ม มันกลายเป็นเรื่องง่ายที่จะตัดสินว่า $x$ เป็นคู่หรือคี่จาก $g^x \bmod p$. ด้วยตัวสร้างของคุณ บิตล่างนี้จะสลับระหว่าง 'คู่' และ 'คี่' อย่างต่อเนื่อง $y_i$ คุณค่าจึงทำให้แยกแยะได้

สิ่งที่เรามักจะทำเมื่อใช้เขตข้อมูลจำกัดคือจงใจทำงานในกลุ่มย่อยขนาดเฉพาะ (ซึ่งแน่นอนว่าไม่สามารถเป็นทั้งหมดได้ $\mathbb{Z}_p^*$ กลุ่ม); ที่ป้องกันไม่ให้ผู้โจมตีกู้คืนข้อมูลใดๆ ของ $x$ จาก $ก^x$.

แน่นอนว่าการทำเช่นนี้จะลดขนาดของช่วงเวลา - อย่างไรก็ตาม ตราบใดที่ช่วงเวลานั้นยาวกว่า เช่น $2^{64}$ (ซึ่งมากกว่าจำนวนเอาต์พุตที่เราจะสร้างได้จริง) ซึ่งก็มากเพียงพอ

เมื่อรวมสิ่งนี้เข้าด้วยกัน ฉันขอแนะนำแนวคิดทางเลือกที่คล้ายกันนี้:

• หยด $ข$; ให้ใช้แบบธรรมดาแทน $y_{i+1} = (y_i)^a \bmod p$ เครื่องกำเนิดไฟฟ้า

• เลือกนายก $p = kp' + 1$, ที่ไหน $p'$ เป็นนายกโซฟี-แชร์กแมง นั่นคือ $(p'-1)/2$ ยังเป็นนายกรัฐมนตรี $p$ ควรใหญ่พอที่จะทำให้ปัญหาล็อกแยกยาก (เช่น อย่างน้อย 2048 บิต) และ $p'$ ควรใหญ่พอที่จะทำให้ปัญหาบันทึกแยกภายในกลุ่มย่อยยาก (เช่น อย่างน้อย 256 บิต อย่างไรก็ตาม อาจใหญ่กว่านี้มากได้ เช่น $k=2$ ใช้งานได้จริง)

• เลือก $y_0$ เป็นสมาชิก (นอกเหนือจาก 1) ของกลุ่มย่อยของขนาด $p'$

• เลือก $a > 0$ เพื่อเป็นค่าสุ่มสำหรับ $a^{(p'-1)/2} \bmod p' \ne 1$ (ซึ่งจะเป็นจริงสำหรับค่าที่เป็นไปได้ครึ่งหนึ่งของ $a$)

สิ่งนี้จะสร้างลำดับของช่วงเวลา $p'-1$ (ซึ่งยาวมาก); ดูทฤษฎีบท 3.2.1.2.C จาก Knuth และเพราะว่า $a$ สามารถเลือกจากความเป็นไปได้จำนวนมากไม่สามารถเดาได้

ตอนนี้ไม่มีเวอร์ชันใดที่จะเป็น ใช้ได้จริง CSRNG (การยกกำลังแบบโมดูลาร์ต่อเอาต์พุตค่อนข้างช้า - เรามี CSRNG ที่ดีกว่ามาก) ฉันเชื่อว่ามันตอบคำถามของคุณ