เส้นโค้งวงรีมีคุณสมบัติอะไรบ้างที่ทำให้มีประโยชน์?

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

RSA รุ่นก่อนดูเหมือนจะค่อนข้างใช้งานง่ายและสมเหตุสมผลกว่าที่จะค้นพบ

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

ในตอนแรก Elliptic Curves ได้รับการศึกษาโดยนักคณิตศาสตร์มานานก่อนที่จะมีการใช้ในการเข้ารหัส ฉันเชื่อว่างานพื้นฐานส่วนใหญ่เสร็จสิ้นในปี 1800 ดังนั้น สิ่งที่ Koblitz และ Miller (นักวิจัยสองคนที่เสนอโดยอิสระ) ไม่ได้ประดิษฐ์เส้นโค้งวงรี แต่ควรสังเกตว่าพวกเขามีศักยภาพในการเข้ารหัส

ทำไมถึงเป็นเช่นนี้? เส้นโค้งวงรีมี "โครงสร้าง" น้อยกว่ากลุ่มฟิลด์จำกัด ด้วยกลุ่มฟิลด์ที่มีขอบเขตจำกัด มีอัลกอริทึมที่สามารถรับองค์ประกอบใดก็ได้ และมีความน่าจะเป็นเล็กน้อยที่จะสามารถแสดงองค์ประกอบนั้นเป็นชุดขององค์ประกอบคงที่ชุดเล็กๆ ปรากฎว่าอัลกอริทึมค่อนข้างมีประโยชน์สำหรับการคำนวณลอการิทึมแบบไม่ต่อเนื่อง และเป็นเหตุผลสำคัญที่เราต้องทำให้กลุ่มเหล่านั้นมีขนาดใหญ่มาก ไม่มีอัลกอริทึมที่รู้จักซึ่งแก้ปัญหานี้สำหรับเส้นโค้งวงรี ดังนั้นเราจึงสามารถใช้กลุ่มเส้นโค้งวงรีที่เล็กกว่ามากได้

ฉันสงสัยว่าแรงจูงใจหรือกระบวนการคิดใดที่อาจนำไปสู่ ​​(ECDSA)

ECDSA วิวัฒนาการมาจาก ลายเซ็น ElGamal. เดิมถูกกำหนดไว้ใน กลุ่มคูณ $\mathbb Z_p^*$ สำหรับนายกรัฐมนตรี $p$. สิ่งนี้ค่อนข้างคล้ายกับกลุ่มการคูณ $\mathbb Z_n^*$ สำหรับคอมโพสิต $n$ ใช้โดย RSA มีขั้นตอนวิวัฒนาการแยกจากกันสองขั้นตอน:

1. อสส (ประมาณ พ.ศ. 2534). ที่ใช้กลุ่มย่อยของ $\mathbb Z_p^*$ ด้วยลำดับที่น้อยกว่า ทำให้ลายเซ็นสั้นกว่าใน ElGamal มาก กลุ่มย่อยดังกล่าวถูกใช้โดยสิ่งที่คล้ายกัน ลายเซ็น Schnorr (ประมาณ พ.ศ. 2532) เพื่อจุดประสงค์เดียวกันนั้น และเป็นที่รู้จักในชื่อ ก กลุ่มชนอร์.
2. ECDSA (ประมาณปี 2543) สิ่งนี้แทนที่กลุ่ม Schnorr โดยหลักแล้วด้วยกลุ่มเส้นโค้งวงรี เพื่อเพิ่มความเร็วในการคำนวณและทำให้คีย์สาธารณะสั้นลง การใช้กลุ่มดังกล่าวมากกว่า (กลุ่มย่อยบางกลุ่มของ) $\mathbb Z_p^*$ ถูกแนะนำ โดยมิลเลอร์ และเป็นอิสระ โดย Koblitz เร็วที่สุดเท่าที่ 1985 ครั้งแรกในบริบทของ การแลกเปลี่ยนคีย์ Diffie-Hellman. คำพูดของมิลเลอร์ การแยกตัวประกอบเส้นโค้งวงรีของ Lentra เป็นแรงบันดาลใจในการใช้กลุ่มเส้นโค้งวงรี Lentra ใช้เส้นโค้งวงรีเป็นเครื่องมือในการโจมตี RSA ซึ่งนำเส้นโค้งวงรีเข้าสู่สนามการเข้ารหัส เป็นที่รู้จักกันมานานกว่าศตวรรษว่าเส้นโค้งวงรีบน สนาม สามารถนำไปสร้างก กลุ่ม. หากฟิลด์มีขอบเขตจำกัด แสดงว่ากลุ่มนั้นจำกัด (ลักษณะเฉพาะที่จำเป็นสำหรับใช้ในวิทยาการเข้ารหัสลับ)

เส้นโค้งวงรีมีคุณสมบัติอะไรบ้างที่ทำให้ยืดหยุ่นต่อการถูกโจมตี?

เส้นโค้งวงรีคือ ไม่ ต้านทานการโจมตีได้ดีกว่ากลุ่ม Schnorr ที่มีขนาดกลุ่มเท่ากัน หากเป็นเพียงขนาดลายเซ็นและความปลอดภัย เราคงไม่ต้องการเส้นโค้งวงรี และจะใช้ DSA ที่ง่ายกว่ามากแทน ECDSA เหตุผลที่นิยมใช้เส้นโค้งวงรีคือช่วยให้การแสดงองค์ประกอบกลุ่มสั้นลง คีย์สาธารณะจึงสั้นลง และการคำนวณเร็วขึ้น (โดยค่าใช้จ่ายของความซับซ้อน) ที่ขนาดกลุ่ม/ลายเซ็นและความปลอดภัยที่เท่ากัน

เหตุผลที่กลุ่มเส้นโค้งวงรีสามารถหลีกเลี่ยงได้ด้วยการแสดงองค์ประกอบกลุ่มที่สั้นกว่ากลุ่ม Schnorr คือกลุ่มเหล่านี้ไม่ได้ฝังอยู่ในบางฟิลด์ (ตามกฎของกลุ่มคือกฎข้อที่สองของฟิลด์) กล่าวอีกนัยหนึ่ง ไม่มีการดำเนินการในกลุ่ม Elliptic Curve ที่คล้ายกับโมดูโลการบวก $p$ เป็นไปในหมู่ $\mathbb Z_p^*$. ดังนั้นจึงไม่มีอะนาล็อกที่รู้จักทำงานในกลุ่ม Elliptic Curve ถึง แคลคูลัสดัชนี อัลกอริทึมซึ่งช่วยให้สามารถคำนวณลอการิทึมแบบไม่ต่อเนื่องใน $\mathbb Z_p^*$ เร็วกว่าวิธีทั่ว ๆ ไปที่ทำงานในกลุ่มใด ๆ เช่น ขั้นตอนทารก / ขั้นตอนยักษ์ หรือ โรของพอลลาร์ด.