ระบบเข้ารหัสแบบอสมมาตรขึ้นอยู่กับเส้นโค้งนอกเหนือจากเส้นโค้งวงรี

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

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

ตัวอย่างเช่น หากคุณเลือกจุดสองจุดบนเส้นโค้งวงรีและลากเส้นผ่านจุดเหล่านั้น เส้นนี้จะตัดกับเส้นโค้งวงรีที่อีกจุดหนึ่งพอดี คุณสมบัตินี้ถูกใช้อย่างมากใน ECC

สิ่งที่คุณอธิบายในที่นี้คือการทำงานของกลุ่มบนเส้นโค้งวงรีดังที่ได้กล่าวไปแล้ว เส้นโค้งไฮเปอร์รีลิปติก ซึ่งเป็นลักษณะทั่วไปของเส้นโค้งวงรี ยังมีประโยชน์สำหรับแอปพลิเคชันการเข้ารหัส

เส้นโค้งไฮเปอร์รีลิปติกของสกุล $g$ เหนือขอบเขตที่จำกัด $\mathbb{F}_q$ สามารถอธิบายได้ด้วยสมการของแบบฟอร์ม $$ C: y^2 + h(x)y = f(x) $$ ที่ไหน $ฉ(x)$ เป็นพหุนามดีกรี $2g+1$, $h(x)$ เป็นพหุนามดีกรีสูงสุด $g$ โดยมีเงื่อนไขเพิ่มเติมบางประการ

เส้นโค้งวงรีสามารถมองได้ว่าเป็นเส้นโค้งไฮเปอร์รีลิปติกของสกุล $g=1$คุณอาจจำได้ว่าเส้นโค้งวงรีในรูปแบบไวเออร์สตราสถูกกำหนดโดย $y^2 = x^3 + ขวาน + b$ซึ่งคุณเห็นดีกรีของพหุนามนั้นใน $x$ เป็นจริง $2g +1 = 3$.

ที่นี่ฉันต้องการเน้นเส้นโค้งไฮเปอร์รีลิปติกของสกุล $2$. ฉันจะอธิบายในตอนท้ายว่าทำไมกรณีนี้จึงเป็นทางเลือกที่น่าสนใจสำหรับ ECC ถ้าลักษณะของเขตจำกัด $\mathbb{F}_q$ ไม่ใช่ $2$จากนั้น HEC ของสกุล $2$ ถูกกำหนดโดยสมการ $$ y^2 = x^5 + b_4x^4 + b_3x^3 +b_2x^2 + b_1x + b_0, \quad b_i \in \mathbb{F}_q .$$ เรามีโครงสร้างกลุ่มที่เกี่ยวกับจุดบนเส้นโค้งหรือไม่? คำตอบคือไม่ แต่โดยคร่าวๆ เราสามารถอธิบายโครงสร้างกลุ่มโดยใช้ "คู่ของจุด" บนเส้นโค้ง

ในภาพด้านบน เส้นโค้งสีน้ำเงินเป็นลูกบาศก์เฉพาะที่ผ่าน $P_1, P_2, Q_1, Q_2$ (กำหนดโดยใช้การแก้ไข)

ที่นี่คุณอาจถามตัวเองด้วยคำถามต่อไปนี้:

1. อะไรรับประกันว่าเส้นตรงตัดกับเส้นโค้งวงรีที่จุดสามจุด
2. เส้นหนึ่งมีจุดตัดที่มีเส้นโค้งไฮเปอร์รีลิปติกกี่จุด $2$?

คำตอบอยู่ในทฤษฎีบทของ Bezout สำหรับเส้นโค้งพีชคณิตระนาบ เพื่อให้เข้าใจโครงสร้างกลุ่มที่เกี่ยวข้องกับเส้นโค้งไฮเปอร์รีลิปติก (รู้จักกันในชื่อ Jacobian of hyperelliptic curve) คุณจะต้องเข้าใจเรขาคณิตเชิงพีชคณิตด้วยเช่นกัน ที่นี่ เป็นจุดเริ่มต้นที่ดีสำหรับเส้นโค้งไฮเปอร์รีลิปติก

HEC ของสกุล $2$ น่าสนใจที่สุดสำหรับแอปพลิเคชันการเข้ารหัสที่อิงจาก Discrete Log Problem เนื่องจากสำหรับเส้นโค้งสกุลที่สูงขึ้น คุณมีดัชนีแคลคูลัสโจมตีที่สามารถใช้เพื่อแก้ปัญหา DLP

ดู กระดาษแผ่นนี้ สำหรับการคำนวณทางคณิตศาสตร์ที่มีประสิทธิภาพใน HEC ของสกุล $2$.

มีหลักฐานเท็จในคำถาม - นั่นคือ:

เส้นโค้งตามอำเภอใจอาจมีประโยชน์ในการเข้ารหัส โดยผมอนุมานจากอ้างในคำถามว่า

ได้รับการพิสูจน์/หักล้างแล้วว่าคุณสามารถค้นหาส่วนโค้งอื่นๆ ตามที่คุณสามารถสร้างระบบเข้ารหัสลับได้

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

ตอนนี้ หากเราต้องการแสดงว่าเส้นโค้งที่ไม่ใช่วงรีสามารถใช้ในการเข้ารหัสคีย์สาธารณะได้ เราก็ต้องแสดงว่า

1. พวกเขายังสร้างกลุ่มที่ไม่มีจุดอ่อนมากไปกว่า ECC หรือ
2. สามารถใช้งานได้แตกต่างกันและยอมรับว่าไม่มีรากฐานด้านความปลอดภัยที่แย่ไปกว่า ECC

และตามหลักการแล้ว พวกมันมีประสิทธิภาพมากกว่า ECC

นอกจากเส้นโค้งวงรีแล้ว ภาคตัดกรวย (เหนือเขตข้อมูลจำกัดที่เหมาะสม $\mathbb F_p$) ยังจัดให้มีโครงสร้างกลุ่ม

ดังนั้นจึงสามารถใช้ในการแลกเปลี่ยนคีย์ Diffie-Hellman อย่างไรก็ตาม โปรดทราบว่าเส้นโค้งเหล่านี้ดูเหมือนจะไม่ปลอดภัยที่จะใช้สำหรับการเข้ารหัส เนื่องจากปัญหาลอการิทึมแบบไม่ต่อเนื่องดูเหมือนจะแก้ไขได้ง่ายในกลุ่มของจุดที่อยู่เหนือเส้นโค้งเหล่านี้ โดยทั่วไป DLP สามารถลดลงเป็นฟิลด์พื้นฐานได้

สำหรับตัวอย่างที่เป็นรูปธรรม: สิ่งนี้ กระดาษ ศึกษาเส้นโค้งด้วยสมการ $x^2 ​​- ได^2 = 1$เพื่อเป็นทางเลือกที่เหมาะสมของ $D$. กล่าวอีกนัยหนึ่ง นี่คือเซตของคำตอบของสมการนี้ $\mathbb F_p$. แสดงให้เห็นว่าบันทึกแยกเป็นเรื่องง่าย