การตั้งค่าเฟรมเวิร์กลอการิทึมแบบไม่ต่อเนื่อง

ปัญหาลอการิทึมไม่ต่อเนื่องเหนือกลุ่มวัฏจักรไพรม์ประกอบด้วยการค้นหา $x$ น่าพอใจ $g^x\equiv h\bmod p$ ที่ไหน $g$ เป็นตัวกำเนิดของกลุ่มการคูณ $\mathbb Z/p\mathbb Z$ ที่นายกใหญ่ $p$.

ไม่มีอัลกอริทึมที่รู้จักในการค้นหา $g$ ในเวลาพหุนาม

1. แล้วระบบลอการิทึมแบบไม่ต่อเนื่องที่ใช้งานได้จริงจะตั้งค่าได้อย่างไร?

2. เราจะรู้ได้อย่างไร $g$ ในความเป็นจริงสร้างกลุ่มคูณ?

ฉันใช้ภาษาไพทอน

แพ็คเกจที่ดีในการระบุคืออะไร $g$ ในกลุ่ม $\mathbb Z/p\mathbb Z$? มีแพ็คเกจเบอร์ใหญ่ไหม?

คำตอบนี้จำกัดเฉพาะกลุ่มภายใต้การดำเนินการคูณโมดูโลไพรม์ขนาดใหญ่ $p$เนื่องจากคำถามเป็นเช่นนั้น (กลุ่มอื่นๆ แพร่หลายมากขึ้นในการเข้ารหัส รวมถึงกลุ่ม Elliptic Curve)

ดังนั้นเราจะทำงานภายในกลุ่ม $\mathbb Z_p^*$, สัญกรณ์สำหรับเซตย่อยของวงแหวน $\mathbb Z/p\mathbb Z$ เกิดจากองค์ประกอบที่มีการคูณผกผันซึ่งสามารถแสดงเป็นกลุ่มได้ เนื่องจาก $p$ เป็นนายก $\mathbb Z/p\mathbb Z$ เป็นสนามและ $\mathbb Z_p^*$ ฟิลด์นั้นมีค่าความเป็นกลางน้อยกว่าสำหรับการบวกหรือไม่ $\mathbb Z_p^*$ สามารถหลอมรวมกับจำนวนเต็มได้ $\{1,2,\ldots,p-2,p-1\}$. มันมี $p-1$ องค์ประกอบ กฎภายในของกลุ่มนี้คือโมดูโลการคูณ $p$.

เราต้องการกลุ่ม $\mathbb Z_p^*$ (หรือกลุ่มย่อยของมัน) ซึ่งการคำนวณลอการิทึมแบบไม่ต่อเนื่องนั้นทำได้ยาก เงื่อนไขสำหรับสิ่งนี้ (ทั้งจำเป็นและเพียงพอต่อการคาดเดาเมื่อเป็นไปตามเงื่อนไขทั้งสอง):

• ลำดับของกลุ่ม (นั่นคือจำนวนองค์ประกอบ) ต้องมีตัวประกอบเฉพาะที่มากพอ $คิว$ เพื่อบล็อก โพลิก-เฮลล์แมน รวมกับ โรของพอลลาร์ดซึ่งสามารถคำนวณลอการิทึมได้ด้วยความพยายาม $\mathcal O\,\left(\sqrt q(\ln n)^3\right)$ และหน่วยความจำปานกลาง ครั้งเดียว $p$ และ $คิว$ เป็นที่รู้จัก. ดังนั้นเราต้องการ $คิว$ ความปลอดภัยอย่างน้อย 256 บิตจาก 128 บิต
• $p$ ต้องใหญ่พอที่จะบล็อกอัลกอริทึมของ ครอบครัวแคลคูลัสดัชนี. ที่จะต้องมี $p$ จาก 2048 ถึง 4096 บิต (ขึ้นอยู่กับการอนุรักษ์ สมมติฐาน และแหล่งที่มา) สำหรับการรักษาความปลอดภัย 128 บิต สมมติว่า $p$ ไม่ใกล้ยกกำลังของจำนวนเต็มน้อยเกินไป

ระบบลอการิทึมแบบไม่ต่อเนื่องในทางปฏิบัติได้รับการตั้งค่าอย่างไร

สิ่งแรกคือการตัดสินใจว่าเราต้องการตั้งค่ากรอบงานลอการิทึมแยกประเภทใด และขึ้นอยู่กับสิ่งที่เราวางแผนจะใช้ มีสามประเภทที่ใช้กันทั่วไป:

1. กลุ่มเต็ม $\mathbb Z_p^*$,กับการสั่งซื้อ $2q=p-1$ และ $คิว$ นายกรัฐมนตรี อันนั้นใช้เมื่อมีบางสิ่งกำหนดให้ตัวกำเนิดของกลุ่มเต็ม (ในฐานะ "ตัวกำเนิดของกลุ่มการคูณ" ของคำถาม $\mathbb Z/p\mathbb Z$"นำไปที่ตัวอักษรไม่)
2. กลุ่มย่อยของเศษซากกำลังสองที่มีลำดับเฉพาะ $q=(p-1)/2$. มันเป็นองค์ประกอบที่เป็น $y$ ใน $\mathbb Z_p^*$ ที่สามารถเขียนได้เป็น $y=u^2$ สำหรับองค์ประกอบบางอย่าง $u$ ของ $\mathbb Z_p^*$ (แล้วก็สำหรับ $u'=p-u$, แน่นอน). มีกลุ่มมาตรฐานดังกล่าวพร้อมเครื่องกำเนิดไฟฟ้า $g=2$, ดู RFC3526. สามารถใช้สำหรับการใช้งานส่วนใหญ่ที่ไม่ต้องการเครื่องกำเนิดไฟฟ้าของกลุ่มเต็ม
3. เซตย่อยที่เล็กกว่าของเซตย่อยของเศษซากกำลังสองที่มีลำดับเฉพาะ $q=(p-1)/r$ สำหรับบางคน (แม้) $r$. สิ่งเหล่านี้เรียกว่ากลุ่ม Schnorr ใช้ในลายเซ็น Schnorr ดั้งเดิมและ DSA

มักมีเหตุผลที่จะไม่ใช้ (1.): if $g$ เป็นตัวสร้าง (นั่นคือ องค์ประกอบใดๆ ของกลุ่มสามารถแสดงเป็น $ก^x$ ) แล้วจากค่าของ $ก^x$ เป็นเรื่องง่ายที่จะบอกได้ว่า $x$ เป็นคู่หรือคี่ (โดยการคำนวณ สัญลักษณ์เลเจนเดร). ซึ่งขัดแย้งกับสมมติฐานที่ต้องการสำหรับการพิสูจน์ความปลอดภัยอย่างง่าย เทียบกับวัตถุประสงค์ในการพิสูจน์ที่ไม่มีความรู้ และอาจเปิดโอกาสให้มีการโจมตี (เช่น การเข้ารหัส ElGamal ล้มเหลว ส.ส.ท).

บางครั้งมีเหตุผลที่จะไม่ใช้ (2.) และชอบ (3.): อย่างน้อยในแอปพลิเคชันลายเซ็น หนึ่งในส่วนประกอบของลายเซ็นมีขนาดบิตเท่ากับ $คิว$ที่ต้องใหญ่แต่เล็กกว่ามากก็ได้ $p$. จึงใช้ขนาดเล็ก $คิว$ ช่วยให้ลายเซ็นสั้นลง นั่นเป็นเหตุผลที่กลุ่ม Schnorr ได้รับการแนะนำ

สำหรับ (1.) และ (2.) การสร้าง $p$ และ $คิว$ เดือดลงเพื่อสร้างนายกรัฐมนตรี $คิว$ กับ $p=2q+1$ ยังเป็นนายกรัฐมนตรี การทดสอบที่ค่อนข้างรวดเร็วนั้นมีประสิทธิภาพ $คิว$ ไม่ใช่แบบผสม (เช่น การทดสอบแฟร์มาต์กับฐาน 2: ตรวจสอบว่า $2^{q-1}\bmod q=1$) แล้วทดสอบอย่างละเอียดว่า $p=2q+1$ เป็นนายก; จากนั้นทดสอบอย่างละเอียดว่า $คิว$ เป็นนายก นอกจากนี้สำหรับนายกรัฐมนตรีขนาดเล็ก $s$มันถือ $q\bmod s\not\in\{0,(s-1)/2\}$. ดังนั้น $q\bmod3=2$, $q\bmod5\in\{1,3,4\}$, ดังนั้น $q\bmod30\in\{11,23,29\}$ซึ่งจำกัดการค้นหาให้แคบลง พิจารณาขนาดใหญ่ขึ้นเล็กน้อย $s$ สามารถนำไปใช้กับตะแกรงหรือสารเพิ่มความเร็วอื่นๆ

นอกจากนี้ยังสามารถแสดงได้ว่าสำหรับ $p$ และ $คิว$ สำหรับ (1.) หรือ (2.) $g=2$ เป็นตัวสร้างสำหรับ (1.) ถ้าและก็ต่อเมื่อ $q\bmod4=1$ (เท่ากับ $p\bmod8=3$ ); และเครื่องกำเนิดไฟฟ้าสำหรับ (2.) มิฉะนั้น จึงจะใช้ $g=2$ (ตัวสร้างที่เล็กที่สุดเท่าที่จะเป็นไปได้ และตัวที่ทำให้การคำนวณบางอย่างง่ายขึ้นเล็กน้อย) ที่เราต้องการ $q\bmod60\in\{29,41,53\}$ สำหรับ (1.) และ $q\bmod60\in\{11,23,59\}$ สำหรับ (2.)

สำหรับ (3.) เราสามารถเลือกจำนวนเฉพาะแบบสุ่มได้ $คิว$ ของขนาดที่ต้องการแล้วสุ่มคู่ $r$ ขนาดพอเหมาะที่จะมี $p=q\,r+1$ นายกรัฐมนตรี เครื่องกำเนิดไฟฟ้าคือ $g=2^r$ (เว้นแต่ว่า $1$ซึ่งอย่างน้อยก็ไม่น่าเป็นไปได้อย่างท่วมท้น ฉันสงสัยว่ามันจะเป็นไปได้ไหม):

หากเราต้องการตัวสร้างแบบสุ่ม เราสามารถเลือกความลับแบบสุ่มได้ $x$ ใน $[1,q-1]$ และใช้ $g$ ดังนี้

• สำหรับ (1.) และ $p\bmod8=3$: $g\gets2^{2x+1}$
• สำหรับ (1.) และ $p\bmod8=7$: จากการลองผิดลองถูก เราพบ $y$ กับ $y^{(p-1)/2}\bmod p\ne 1$ (เทียบเท่ากับ $y^{(p-1)/2}\bmod p=p-1$ ); จำนวนความพยายามที่คาดไว้คือประมาณสองครั้งหากสำรวจเลขคี่ติดต่อกัน $u$ เริ่มต้น $u=3$; แล้ว $g\gets u^{2x+1}$.
• สำหรับ (2.) $g\gets2^{2x}$
• สำหรับ (3.) $g\gets2^{((p-1)/q)\,x}$

ไม่มีอัลกอริทึมที่รู้จักในการค้นหา $g$ ในเวลาพหุนาม

นั่นเป็นความจริงหากไม่ทราบการแยกตัวประกอบของลำดับกลุ่ม หรือหากเราจำกัดไว้ กำหนด อัลกอริทึม แต่ในทางปฏิบัติ ลำดับนั้นเป็นที่รู้จัก บางครั้งเราสามารถทำนายตัวสร้างได้ และอัลกอริธึมความน่าจะเป็นอย่างง่ายจะให้ผลเป็นอย่างอื่นอย่างรวดเร็ว

มีแพ็คเกจเบอร์ใหญ่ไหม?

Python มีการสนับสนุนแบบเนทีฟสำหรับตัวเลขจำนวนมาก และเป็นแบบฝึกหัดง่ายๆ ในการสร้างพารามิเตอร์ $(p,g)$ ใน Python บริสุทธิ์ ปัญหาเพียงเล็กน้อยเท่านั้นคือการทดสอบเฉพาะและการสร้างเฉพาะแบบสุ่ม แต่สามารถทำได้ด้วย Python ล้วนๆ และมีการสนับสนุนสำหรับสิ่งเหล่านี้ในแพ็คเกจต่างๆ รวมถึง SymPy เนื่องจาก $(p,g)$ มักจะเป็นสาธารณะ ช่องด้านข้างไม่ใช่ปัญหา