คำถามเกี่ยวกับลำดับความยาว/จำนวน/ความปลอดภัยของ $x\mapsto x^\alpha \mod (N=Q\cdot R)$ กับ $Q=2q_1q_2+1$ และ $R=2r_1r_2+1$ และ $\alpha = 2q_2r_2$

กำหนดหมายเลข $N$ กับ $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ ที่มีช่วงเวลาต่างกัน $P,Q,q_1,q_2,r_1,r_2$.

ถ้าตอนนี้เราเลือกเลขยกกำลัง $\alpha$ ประกอบด้วยปัจจัยสำคัญของ $คิว,อาร์$ กับ $$\alpha=2 \cdot q_2 \cdot r_2$$ เราสามารถสร้างลำดับ $S$ ด้วยองค์ประกอบ $$s_{i+1} = s_i^\alpha \mod N$$ เริ่มต้นที่ค่า $s_0$ $$s_0 = x^\alpha \mod N\textbf{ }\text{ กับ}\textbf{ }x\in [1,N-1]$$ เราสามารถสร้างลำดับที่มีความยาวคงที่ (ในกรณีส่วนใหญ่) $|S|_{\max}$.

เป้าหมาย: ฉันกำลังหาวิธีลดขนาด $|S|_{\max}$ โดยที่ยังคงรักษาความปลอดภัยและสามารถสร้างค่าสุ่มได้ $\ในสกุลเงิน S$ โดยไม่มีการรั่วไหลของพารามิเตอร์ที่เกี่ยวข้องกับความปลอดภัยการรักษาความปลอดภัยขึ้นอยู่กับการรักษาขนาดของ $|S|$ และด้วยสิ่งนี้การแยกตัวประกอบของ $N$ ซ่อนตัวจากศัตรูที่อาจเกิดขึ้นเพื่อหลีกเลี่ยงขั้นตอนใหญ่ ๆ นอกจากนี้ ฝ่ายตรงข้ามไม่ควรสามารถระบุช่องว่างของดัชนีได้ $i-j$ ระหว่างสององค์ประกอบลำดับที่สร้างขึ้นแบบสุ่ม $s_i,s_j \ใน S$

การแก้ปัญหาการทดลอง: ส่วนต่อไปนี้อาจมีสมการที่ไม่สมบูรณ์/ไม่ถูกต้อง นอกจากนี้ยังอาจต้องใช้สมมติฐานข้างต้น

จำนวนของค่าที่ไม่ซ้ำ $x^\alpha \mod N$ เป็น $$N_{\alpha} = (1+q_1) \cdot (1+r_1)$$

ขนาดของลำดับ:

เพื่อกำหนดความยาวของลำดับที่พบบ่อยที่สุดและใหญ่ที่สุด $S_{\max}$ ก่อนอื่นเราต้องกำหนดความยาวของลำดับระหว่างปัจจัยสำคัญ $q_1,r_1$ กับ $$ g_q \equiv \alpha \mod q_1$$ $$ L_{q_1} = |\{g_q^k \mod q_1\text{, }\text{ สำหรับ } k\in [1,q_1-1]\}|$$ $$ g_r \equiv \alpha \mod r_1$$ $$ L_{r_1} = |\{g_r^k \mod r_1\text{, }\text{ สำหรับ } k\in [1,r_1-1]\}|$$

อนุญาต $C$ เป็นผลคูณจากเซตของตัวประกอบเฉพาะร่วมระหว่างการแยกตัวประกอบของ $L_{q_1}$ และ $L_{p_1}$ (จึงไม่มีอำนาจนายกรัฐมนตรีใน $C$)
รู้สิ่งนี้เราสามารถกำหนดได้ $|S|_{\max}$ (โดยส่วนใหญ่) ด้วย $$|S|_{\max} = \frac{L_{q_1} \cdot L_{r_1}}{C}$$ (หนึ่งรู้ปัญหา: มันไม่ได้ผลถ้า $L_{q_1}$ เป็นตัวแบ่งเต็มของ $L_{r_1}$ หรือในทางกลับกัน)

จำนวนลำดับ:

แล้วแต่จะเลือก $s_0$ สามารถเป็นส่วนหนึ่งของ $1$ ออกจาก $N_S$ ลำดับที่ต่างกันด้วยความยาว $|S_{\max}|$ หรือในบางกรณีที่พบได้ยากก็เป็นส่วนหนึ่งของลำดับที่มีความยาวด้วย $q_1-1$,$r_1-1$ หรือ $1$.
จำนวนลำดับทั้งหมด $N_S$ จะเป็น (ในกรณีส่วนใหญ่) $$N_S = \frac{\frac{q_1-1}{L_{q_1}}\cdot \frac{r_1-1}{L_{r_1}}}{\gcd(L_{q_1},L_{r_1}) }$$ (ตามด้านบนนี้จะไม่ทำงานถ้า $L_{q_1}$ เป็นตัวแบ่งเต็มของ $L_{r_1}$ หรือในทางกลับกัน)
จำนวนลำดับต่างๆ เสมอกัน เป็นอย่างน้อย $N_S > 2$. เป้าหมายคือทำให้สิ่งนี้มีขนาดเล็กที่สุดเท่าที่จะทำได้

เราต้องดูแลเกี่ยวกับเลขยกกำลังด้วย $\alpha$ มีขนาดใหญ่พอที่จะหลีกเลี่ยงการแยกตัวประกอบ

คำถาม:

เมื่อรู้สิ่งนี้แล้ว เราสามารถหาการแยกตัวประกอบได้ยาก $N$ กับ $\alpha$ และขนาดเล็ก $|S|_{\max}$. แต่จะเล็กแค่ไหน $|S|_{\max}$ เพื่อรักษาความปลอดภัย?

เราเรียกมันว่าปลอดภัยเพียงพอหากศัตรูสร้างองค์ประกอบลำดับแบบสุ่มสององค์ประกอบ $s_i, s_j$ ความต้องการในทางที่ผิด $2^{100}$ ขั้นตอนการคำนวณเพื่อคำนวณช่องว่างระหว่างดัชนี $i$ และ $เจ$ (สมมุติ $s_i,s_j$ เป็นส่วนหนึ่งของลำดับเดียวกัน)

ไตรมาสที่ 1: จะ $\ประมาณ 102$-นิดหน่อย $|S|_{\max}$ เพียงพอ? ถ้าไม่มี ต้องใหญ่ขนาดไหน?
ไตรมาสที่ 2: มีการแยกตัวประกอบของ $|S|_{สูงสุด}$ กระทบต่อความมั่นคง? เช่น. เลือกดีกว่า $|S|_{สูงสุด} = d\cdot p$ ด้วยขนาดเล็ก $d$ และนายกใหญ่ $p$?
ไตรมาสที่ 3: ถ้าเราเลือก $|S|_{max} = A\cdot B \cdot C$ กับ $A,B,C$ เป็นไพรม์และคล้ายกันมากที่สุดเท่าที่จะเป็นไปได้และแทนที่ด้วย $\alpha$ กับ $$\alpha_A = \alpha^{BC} \mod \phi(N)$$ $$\alpha_B = \alpha^{AC} \mod \phi(N)$$ $$\alpha_C = \alpha^{AB} \mod \phi(N)$$ องค์ประกอบที่สร้างขึ้นแบบสุ่มจะมี $3$- ดัชนีเช่น $s_{abc}$. ต้องใช้กี่ขั้นตอนในการคำนวณช่องว่างของดัชนี $s_{def}$?
เช่น. ช่องว่างดัชนี $a-d$ จะถูกคำนวณด้วย $\alpha_A$.
ไตรมาสที่ 3: จะเร็วกว่า $O(AB+C)$ (ผิวทางตัดกับเส้น)?

โบนัส-Q: มีสูตรที่สมบูรณ์/ถูกต้อง/ง่ายกว่าสำหรับ $|S|_{สูงสุด}$ และ $N_S$?

ตัวอย่าง: เราเลือก ก $2048$-นิดหน่อย $N = P \cdot Q$ ด้วยปัจจัยสำคัญ $q_2 \gg q_1$ และ $r_2 \gg r_1$. ด้วยสิ่งนี้ $\alpha = q_2\cdot r_2$ อาจจะเป็น $\ประมาณ1800$-bit และสิ่งที่เกี่ยวข้อง $|S|_{\max}$ อาจจะเป็น $100/200/300$-นิดหน่อย

ตัวอย่างของเล่น:

*ตัวอย่างข้อผิดพลาด สมการที่ทำนาย $1560$ แทน

คำถามและคำตอบที่เกี่ยวข้อง: เกี่ยวกับ $N_\อัลฟ่า$ ,$\พื้นที่$ เกี่ยวกับลำดับเหล่านั้น