ความยากของปัญหาลอการิทึมไม่ต่อเนื่องเกี่ยวข้องกับการเข้ารหัสเส้นโค้งวงรีอย่างไร

ตามคำนิยาม ปัญหาลอการิทึมที่ไม่ต่อเนื่องคือการแก้ความสอดคล้องกันต่อไปนี้สำหรับ $x$ และเป็นที่ทราบกันดีว่าโดยทั่วไปแล้วไม่มีอัลกอริทึมที่มีประสิทธิภาพสำหรับสิ่งนั้น

$$\begin{จัด*} b^x\equiv r&\pmod p\quad(1)\end{align*}$$ คือการตามหา $x$ (ถ้ามี) สำหรับที่กำหนด $r,b$ เป็นจำนวนเต็มที่น้อยกว่าจำนวนเฉพาะ $p$.

ฉันถูกต้องแล้วหรือยัง? โปรดแก้ไขฉันหากฉันเข้าใจอะไรผิด

ในการเข้ารหัสแบบวงรี (elliptic curve cryptography) กล่าวกันว่าใน $P=a\คูณ G$ เราไม่สามารถคำนวณได้ $a$ โดยรู้ $พี$ และ $G$ เพราะปัญหาลอการิทึมไม่ต่อเนื่องแก้ยาก ฉันไม่เข้าใจว่าสิ่งนี้เกี่ยวข้องกับสมการ 1 อย่างไร ฉันหมายความว่ามีเพียงคำศัพท์ที่คล้ายกันในทั้งสองปัญหาหรือไม่

เพื่อชี้แจงคำถามของฉัน ลองจินตนาการว่าอัจฉริยะจากคนรุ่นหลังสามารถแนะนำวิธีแก้ปัญหาสมการ 1 ซึ่งทำได้ในเวลาที่เป็นไปได้โดยใช้การตั้งค่าฮาร์ดแวร์โดยเฉลี่ยของเวลานั้น อัลกอริทึมที่พวกเขาเสนอสามารถค้นหาได้ $x$ (ถ้ามี) สำหรับจำนวนเฉพาะที่กำหนด $p$ และใด ๆ ที่กำหนด $r, b$. ตอนนี้ ฉันต้องการทราบว่าสิ่งประดิษฐ์นี้เป็นภัยคุกคามต่อความปลอดภัยของการเข้ารหัสแบบ elliptic curve หรือไม่ กล่าวอีกนัยหนึ่ง ความรู้เกี่ยวกับอัลกอริทึมดังกล่าวจะช่วยในการดึงข้อมูลหรือไม่ $a$ จาก $พี$?

ถ้าใช่ โปรดอธิบายว่าความสัมพันธ์นี้ถูกกำหนดอย่างไร และโฟลว์ทางคณิตศาสตร์คืออะไรที่เราสามารถคำนวณได้ $a$ จาก $พี$ซึ่งผมเดาว่าจะต้องผ่านการแก้สมการที่คล้ายกับสมการ 1

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

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

กลุ่มสามารถเขียนด้วยสัญกรณ์การคูณ (เช่นเดียวกับโมดูโลกลุ่มการคูณ $p$) เพื่อให้การทำงานของกลุ่มถูกเขียนเป็น $*$, $\times$, $\cdot$ หรือโดยปริยาย ในกรณีทั้งหมดเหล่านี้ เราจะใช้สัญกรณ์ธรรมชาติสำหรับการใช้ซ้ำๆ ของการดำเนินการกลุ่มด้วยองค์ประกอบเดียว เช่น $b^2:=b*b$ และภาพรวมที่คล้ายคลึงกัน ดังนั้นปัญหาลอการิทึมแบบไม่ต่อเนื่องทั่วไปสำหรับกลุ่มวัฏจักร $C$ เขียนด้วยสัญกรณ์การคูณที่สร้างโดย $ข$ จะได้รับ $r\ ใน C$ หาจำนวนเต็ม $x$ ดังนั้น $b^x=r$.

กลุ่มอื่นเขียนด้วยสัญกรณ์เพิ่มเติม (โดยปกติจะสงวนไว้สำหรับกลุ่มอาเบเลียน รวมทั้งกลุ่มเส้นโค้งวงรี) ในกรณีนี้การดำเนินการกลุ่มจะแสดงแทน $+$ (แต่ไม่ควรอ่านเป็นการเพิ่มเติมในความหมายปกติ) และอีกครั้ง มีสัญกรณ์ธรรมชาติสำหรับการใช้ซ้ำๆ ของการดำเนินการกลุ่มด้วยองค์ประกอบเดียว เช่น $2G=G+G$ และอื่น ๆ เมื่อเขียนด้วยวิธีนี้ ปัญหาลอการิทึมที่ไม่ต่อเนื่องสำหรับกลุ่มวัฏจักร $C$ ที่สร้างขึ้นโดย $G$ กลายเป็น: ให้ $P\ใน C$ หาจำนวนเต็ม $x$ ดังนั้น $xG=P$.

ไม่เชื่อว่าจะเป็นการแปลที่ชัดเจนระหว่างปัญหาลอการิทึมที่ไม่ต่อเนื่องในกลุ่มต่างๆ มีบางกลุ่มที่ปัญหาลอการิทึมไม่ต่อเนื่องเป็นเรื่องง่าย (เช่น โมดูโลกลุ่มบวก $p$, โมดูโลกลุ่มคูณ $2^n$ และแม้กระทั่ง (ในความหมายกึ่งพหุนาม) กลุ่มการคูณของ $GF(2^n)$).

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

โปรดทราบว่าปัญหาลอการิทึมที่ไม่ต่อเนื่องทั้งหมดสามารถแก้ไขได้ในเวลาพหุนาม (ควอนตัม) โดย อัลกอริทึมของชอร์.

อนุญาต $E$ เป็นเส้นโค้งวงรีที่กำหนดบนเขตข้อมูลจำกัด $\mathbb{F}_p$:

$$E : y^2 = x^3 + Ax + B \text{ กับ } A, B \in \mathbb{F}_p$$

อนุญาต $พี$ และ $T$ เป็นจุดใน $E(\mathbb{F}_p)$. ค้นหาจำนวนเต็ม $a$ ดังนั้น นั่น

$$P =aG$$

นี่คือปัญหาสำหรับเส้นโค้งวงรี ปัญหาสามารถเขียนใหม่ได้โดยใช้ลอการิทึม:

$$a = log_G (P)$$

คุณสามารถเปรียบเทียบกับลอการิทึมแยก "มาตรฐาน":

$$ b^x \equiv r \mod p \ลูกศรขวา x = log_b(r)$$

ตอนนี้คุณเห็นความคล้ายคลึงกันหรือไม่?

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