เป็นไปได้ไหมที่จะคำนวณค่าผกผันของโมดูลาร์ของคีย์สาธารณะ secp256k1

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

ฉันไม่ได้รับการศึกษาเป็นอย่างดีเป็นพิเศษในวิชาคณิตศาสตร์หรือวิทยาการเข้ารหัสลับ แต่ฉันพบว่ามันน่าสนใจ ดังนั้นฉันอาจจะไม่รู้คำศัพท์ที่ถูกต้องในการค้นคว้าด้วยตนเอง

มีวิธี (นอกเหนือจากกำลังเดรัจฉาน) ในการค้นหาจำนวนเต็มที่ให้ผลลัพธ์เป็น 1 เมื่อคีย์สาธารณะคูณด้วยจำนวนเต็มนั้นหรือไม่

ที่จริงได้รับรหัสสาธารณะ $H$เป็นเรื่องง่ายที่จะหาจำนวนเต็มที่น้อยที่สุด $x > 0$ ดังนั้น $xH = 1$. สำหรับ secp256k1 (และถ้า $H$ ไม่ใช่องค์ประกอบที่เป็นกลาง) ดังนั้น $x = 115792089237316195423570985008687907852837564279074904382605163141518161494337$. นี่เป็นความจริงไม่ว่าประเด็นใด $H$ เป็น; จุดทั้งหมดบนเส้นโค้งนั้น (นอกเหนือจากองค์ประกอบที่เป็นกลาง) มีลำดับนั้น

อย่างไรก็ตาม นั่นไม่ใช่สิ่งที่เรามักจะหมายถึงหากเราอ้างถึง 'the mod inverse'; ที่ฟังดูเหมือน "ให้ $xG$ค้นหาจุด $x^{-1}G$" ซึ่งเป็นที่ทราบกันดีว่าเทียบเท่ากับปัญหา CDH (ซึ่งเราหวังว่าจะยาก)

นี่เป็นคำตอบเพิ่มเติมเล็กน้อย

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

ชุมชน bitcoin มักจะเรียกการคูณแบบสเกลาร์ว่าเป็นการคูณ¹. สิ่งที่เรากำหนดให้เป็นการคูณสเกลาร์เป็น

$$[k]G : = \underbrace{G + G + \cdots + G}_{k-ครั้ง}$$ กล่าวอีกนัยหนึ่งคือการเพิ่มจุด $k$ ครั้ง.

มีปัญหาที่กำหนดไว้สำหรับสิ่งนี้แล้ว (โดยใช้เวอร์ชัน EC $r$ เป็นลำดับขององค์ประกอบฐาน $G$เส้นโค้งเป็นลำดับเฉพาะและ $E(K)$ เป็นเซตของจุดโค้ง)

คำจำกัดความ;

• ซีดีเอช : ให้สาม $(ก,[a]ก,[b])$ หา $[ab]G$.
• ผกผัน-DH : ให้คู่ $(G, [a]G) \in E(K) - \{\mathcal{O}\}$ ขององค์ประกอบในการสั่งซื้อที่สำคัญ $r$ ใน $E(K)$ เพื่อคำนวณ $[a^{-1}]G$.
• สแควร์-DH: โจทย์การคำนวณ Square-DH คือ: ให้ $(ก, [a]ก )$ ที่ไหน $G \ใน E(K)$ มีคำสั่งสำคัญ $r$ เพื่อคำนวณ $[a^2]G$.

ลด;

• $\text{ผกผัน-DH} \leq_R \text{CDH}$.

  สมมติว่าเรามีออราเคิล $O$ ที่แก้ $\text{CDH}$. เราได้รับ $(ก,[ก]ก)$ เป็น $\text{ผกผัน-DH}$ ตัวอย่างและเราต้องการหา $P = [a]G$. จากนั้นเราก็มี $$G = [a^{-1}]P = [a^{-1}a]G = G$$

  ตอนนี้โทรหาออราเคิล $O$ กับ $O(P,G,G) = O(P,[a^{-1}]P,[a^{-1}]P) $ และเอาต์พุตของออราเคิล $[a^{-2}]P$. แทนที่ $พี$ ที่จะได้รับ $$[a^{-2}]P = [a^{-2}a]G = [a^{-1}]G$$ นี่แสดงให้เห็นถึงการลดลง

• $\text{Square-DH} \leq_R \text{ผกผัน-DH}$.

  สมมติว่า $O$ เป็นออราเคิลที่แก้ปัญหา $\text{ผกผัน-DH}$ และปล่อยให้ $(G, P = [a]G )$ จะได้รับ ถ้า $P = \mathcal{O}$ แล้วกลับ $\mathcal{O}$ อื่น $$O(P, G) = O(P , [a^{-1}]P) = [a]P = [a\cdot a]P = [a^2]P.$$ นี่แสดงให้เห็นถึงการลดลง

ดังนั้นเราจึงมี $\text{Square-DH} \leq_R \text{ผกผัน-DH} \leq_R \text{CDH}$. ถ้าเราสามารถแสดงได้ว่า $\text{CDH} \leq_R \text{Square-DH}$ แล้วเราจะมีความเท่าเทียมกัน

• $\text{CDH} \leq_R \text{Square-DH}$

  อนุญาต $O$ เป็นออราเคิลที่จะแก้ปัญหา $\text{Square-DH}$ และเราได้รับ $(ก,[a]ก, [b]ก)$ เป็น ก $\text{CDH}$ ตัวอย่าง.

  • เรียก $O$ สองครั้งด้วย $O(G,[a]G)$ และ $O(G,[b]G)$ ที่จะได้รับ $P= [a^2]G$ และ $Q= [b^2]G$ตามลำดับ

  • ตอนนี้อีกหนึ่งสาย $O(G, P+Q) = O(G, [a+b]G)$ และได้รับ $$R = [(a+b)^2]G = [a^2+2ab+b^2]G.$$

  • ในที่สุดก็คำนวณ $$[2^{-1}](R - (P+Q)) = [2^{-1} (a^2+2ab+b^2 -a^2 -b^2)]G = [ ab]G$$ นี่แสดงให้เห็นถึงการลดลง

ดังนั้นเราจึงมีความเท่าเทียมกัน ดังนั้นหาก $\text{CDH}$ ก็ยากแล้ว $\text{ผกผัน-DH}$ ก็ยากเหมือนกัน เราหวังว่านี่จะเป็นสำหรับฝ่ายตรงข้ามที่ไม่ใช่ควอนตัม

มีวิธี (นอกเหนือจากกำลังเดรัจฉาน) ในการค้นหาจำนวนเต็มที่ให้ผลลัพธ์เป็น 1 เมื่อคีย์สาธารณะคูณด้วยจำนวนเต็มนั้นหรือไม่

ฉันสามารถอ่านสิ่งนี้ได้สองวิธี

• $1$ เป็นเอกลักษณ์ของเส้นโค้งที่เราเขียน $\mathcal{O}$แล้วเรามีตัวตน $[r]P = \mathcal{O}$ สำหรับทุกองค์ประกอบของเส้นโค้งลำดับเฉพาะ $r$. นี่คือคำจำกัดความของ ลำดับขององค์ประกอบในทฤษฎีกลุ่ม.

• $1$ เป็น $[a\cdot a^{-1}]G = [\color{red}{1}]G = G$ แล้วนี่คือ $\text{ผกผัน-DH}$ ตามที่เราคุยกัน

_{¹เราสามารถ (กำหนด | เรียก) การเพิ่มจุดเป็นการคูณจุดได้ อย่างไรก็ตาม การบวกเป็นประวัติศาสตร์และหนังสือโค้ง Elliptic ที่สำคัญทั้งหมดใช้การบวกจุด เหนือจำนวนเชิงซ้อน เส้นโค้งวงรีใดๆ สามารถรับรู้ได้ดังนี้ $\mathbb C/\Gamma$ สำหรับขัดแตะ $\แกมม่า$. ในกรณีนี้ การบวกมาจากการบวกของจำนวนเชิงซ้อนมาตรฐาน}