การเข้ารหัสด้วยเส้นโค้งเชิงวงรี

การเข้ารหัสด้วยเส้นโค้งเชิงวงรี (Elliptic-curve cryptography - ECC) เป็นการนำแนวคิดการเข้ารหัสแบบกุญแจสาธารณะมาใช้กับกลุ่มของจุดบนเส้นโค้งเชิงวงรี ทำให้ได้ความปลอดภัยเทียบเท่ากับ RSA หรือ Diffie-Hellman แบบฟิลด์จำกัด แต่ใช้กุญแจที่มีขนาดเล็กกว่ามาก

Definition

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

Scope

หัวข้อนี้ครอบคลุมกฎกลุ่มของเส้นโค้งเชิงวงรีบนฟิลด์จำกัด ปัญหาลอการิทึมไม่ต่อเนื่องของเส้นโค้งเชิงวงรี และรูปแบบการเข้ารหัสที่สร้างขึ้นจากแนวคิดเหล่านี้ ได้แก่ Diffie-Hellman แบบเส้นโค้งเชิงวงรี (ECDH) รูปแบบลายเซ็นดิจิทัล ECDSA และ EdDSA รวมถึงเส้นโค้งสมัยใหม่ เช่น Curve25519 นอกจากนี้ยังกล่าวถึงเหตุผลที่ลอการิทึมไม่ต่อเนื่องของเส้นโค้งเชิงวงรีแก้ไขได้ยากกว่าของฟิลด์จำกัด (ไม่มีการโจมตีแบบ index calculus ที่มีประสิทธิภาพ) และข้อควรพิจารณาในการนำไปใช้งาน เช่น การใช้ nonce ซ้ำใน ECDSA หัวข้อนี้ไม่รวมถึง RSA และรูปแบบลอการิทึมไม่ต่อเนื่องแบบฟิลด์จำกัด ซึ่งครอบคลุมในหัวข้อที่เกี่ยวข้องอื่น ๆ

Core questions

• การบวกจุดทางเรขาคณิตบนเส้นโค้งเชิงวงรีก่อให้เกิดกลุ่มการเข้ารหัสได้อย่างไร?
• เหตุใดลอการิทึมไม่ต่อเนื่องของเส้นโค้งเชิงวงรีจึงแก้ไขได้ยากกว่าแบบฟิลด์จำกัด ทำให้สามารถใช้กุญแจขนาดเล็กกว่าได้?
• Diffie-Hellman และลายเซ็นดิจิทัลถูกนำมาใช้กับเส้นโค้งเชิงวงรีได้อย่างไร?
• อะไรทำให้เส้นโค้งสมัยใหม่เช่น Curve25519 ปลอดภัยกว่าในการนำไปใช้งานเมื่อเทียบกับ NIST curves รุ่นเก่า?
• เหตุใดการใช้ nonce ที่ไม่ซ้ำกันต่อลายเซ็นจึงมีความสำคัญอย่างยิ่งใน ECDSA?

Key concepts

• กฎกลุ่มเส้นโค้งเชิงวงรี
• การคูณสเกลาร์
• ปัญหาลอการิทึมไม่ต่อเนื่องของเส้นโค้งเชิงวงรี
• ECDH
• ECDSA
• EdDSA และ Ed25519
• Curve25519
• ช่องโหว่จากการใช้ nonce ซ้ำ
• ขนาดกุญแจเทียบกับ RSA

Key theories

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

เมื่อกำหนดจุด P และ Q = kP บนเส้นโค้ง การกู้คืนค่าสเกลาร์ k เชื่อกันว่าต้องใช้ความพยายามแบบ exponential อย่างเต็มที่สำหรับเส้นโค้งที่เลือกมาอย่างดี เนื่องจากไม่มีการโจมตีแบบ index-calculus ที่ทำให้ลอการิทึมไม่ต่อเนื่องแบบฟิลด์จำกัดอ่อนแอลง

กุญแจขนาดเล็กกว่าเพื่อความปลอดภัยที่เท่าเทียมกัน

เนื่องจากการโจมตีที่ดีที่สุดต่อลอการิทึมไม่ต่อเนื่องของเส้นโค้งเชิงวงรีเป็นอัลกอริทึมแบบ generic square-root เส้นโค้งเชิงวงรีขนาด 256 บิตจึงให้ความปลอดภัยประมาณ 128 บิต ซึ่งเทียบเท่ากับ RSA ขนาด 3072 บิต ทำให้การดำเนินการเร็วขึ้นและได้กุญแจและลายเซ็นที่มีขนาดเล็กลง

Mechanisms

จุดบนเส้นโค้งเชิงวงรีบนฟิลด์จำกัดจะก่อตัวเป็นกลุ่มอาเบล (abelian group) ภายใต้กฎการบวกทางเรขาคณิต การบวกจุดฐาน P เข้ากับตัวเองซ้ำ k ครั้ง (การคูณสเกลาร์, kP) สามารถทำได้อย่างมีประสิทธิภาพ แต่การกู้คืนค่า k จาก kP เป็นปัญหาที่ยาก ECDH ดำเนินการ Diffie-Hellman โดยการแลกเปลี่ยนผลคูณสเกลาร์ของจุดฐาน; ECDSA และ EdDSA สร้างลายเซ็นจากค่าสเกลาร์ต่อข้อความ (nonce) ซึ่งหากมีการใช้ซ้ำหรือคาดเดาได้ จะทำให้กุญแจส่วนตัวรั่วไหลได้ ดังที่แสดงให้เห็นจากการละเมิดความปลอดภัยหลายครั้งที่เกิดขึ้นจริง

Clinical relevance

ECC เป็นตัวเลือกเริ่มต้นสำหรับการเข้ารหัสแบบกุญแจสาธารณะในระบบใหม่ ๆ: ECDHE ให้การแลกเปลี่ยนกุญแจแบบ forward-secret ใน TLS 1.3, Ed25519 ใช้ลงนามกุญแจ SSH, การอัปเดตซอฟต์แวร์ และใบรับรอง, และ Curve25519 ใช้รักษาความปลอดภัยของ Signal, WireGuard และแอปพลิเคชันส่งข้อความสมัยใหม่ ด้วยขนาดกุญแจที่เล็กและการทำงานที่รวดเร็ว ทำให้เหมาะสำหรับอุปกรณ์เคลื่อนที่, สมาร์ทการ์ด และฮาร์ดแวร์ IoT ที่มีข้อจำกัด

Evidence & guidelines

ECDSA ได้รับการกำหนดมาตรฐานใน FIPS 186, ECDH ใน NIST SP 800-56A, และ EdDSA/Ed25519 ใน RFC 8032; Curve25519/X25519 ใน RFC 7748 แนวปฏิบัติสมัยใหม่นิยมใช้ Edwards curves และ X25519 เนื่องจากมีความทนทานต่อข้อผิดพลาดในการนำไปใช้งาน การล่มสลายของ ECDSA เมื่อมีการใช้ nonces ซ้ำ (โดยเฉพาะการดึงกุญแจของ Sony PlayStation 3 ในปี 2010) เป็นตัวอย่างเตือนใจที่เป็นมาตรฐาน

History

Neal Koblitz และ Victor Miller ได้เสนอการใช้เส้นโค้งเชิงวงรีสำหรับการเข้ารหัสอย่างอิสระในปี 1985-1987 การนำไปใช้ในช่วงแรกเป็นไปอย่างช้า ๆ เนื่องจากความกังวลเรื่องสิทธิบัตรและความน่าเชื่อถือ รวมถึงความซับซ้อนของ NIST curves แต่ ECC ได้กลายเป็นที่นิยมอย่างแพร่หลายในทศวรรษ 2010 เนื่องจากประสิทธิภาพของขนาดกุญแจมีความสำคัญมากขึ้น และ Curve25519 ของ Bernstein (2006) และ Ed25519 ได้นำเสนอการออกแบบที่รวดเร็วและทนทานต่อการใช้งานผิดพลาด ซึ่งปัจจุบันมีการใช้งานอย่างกว้างขวาง

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

เหตุใดกุญแจเส้นโค้งเชิงวงรีขนาด 256 บิตจึงเทียบเท่ากับกุญแจ RSA ขนาด 3072 บิต?

การโจมตีที่ดีที่สุดที่รู้จักต่อลอการิทึมไม่ต่อเนื่องของเส้นโค้งเชิงวงรีเป็นแบบ generic และใช้เวลาประมาณรากที่สองของขนาดกลุ่ม ในขณะที่การแยกตัวประกอบและลอการิทึมไม่ต่อเนื่องแบบฟิลด์จำกัดมีอัลกอริทึมแบบ subexponential ที่เร็วกว่า ดังนั้นเส้นโค้งเชิงวงรีจึงต้องการบิตน้อยกว่ามากสำหรับระดับความปลอดภัยที่เท่ากัน

NIST elliptic curves น่าเชื่อถือหรือไม่?

NIST P-curves มาตรฐานมีการใช้งานอย่างแพร่หลายและยังไม่พบว่าถูกเจาะได้ แต่การเลือกค่าคงที่ที่ไม่สามารถอธิบายได้และความยากในการนำไปใช้งานทำให้หลายคนนิยมใช้ Curve25519 และ Ed25519 ซึ่งมีการออกแบบที่โปร่งใสและง่ายต่อการนำไปใช้งานอย่างปลอดภัยในเวลาคงที่