การเข้ารหัสลับแบบเส้นโค้งวงรี
- ผู้เสนอ
- Neal Koblitz
- ปี
- 1985
- ประเภท
- asymmetric encryption and key agreement
- กลุ่มวิธี
- Public-key cryptography
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การเข้ารหัสลับแบบเส้นโค้งวงรี (ECC) เป็นระบบการเข้ารหัสลับแบบกุญแจสาธารณะที่อิงตามโครงสร้างเชิงพีชคณิตของเส้นโค้งวงรีบนฟีลด์จำกัด ถูกเสนอขึ้นโดย Neal Koblitz และ Victor Miller อย่างอิสระในปี 1985 ECC ให้ความปลอดภัยเทียบเท่ากับ RSA แต่มีขนาดกุญแจที่เล็กกว่ามาก การเข้ารหัสลับสมัยใหม่นิยมใช้ ECC มากขึ้นเรื่อยๆ เนื่องจากประสิทธิภาพ: กุญแจ ECC ขนาด 256 บิตให้ความปลอดภัยเทียบเท่ากับกุญแจ RSA ขนาด 2048 บิต ทำให้เหมาะสำหรับสภาพแวดล้อมที่มีข้อจำกัดและระบบที่มีประสิทธิภาพสูง
แนวคิดเบื้องหลังวิธีการ
ECC อิงตามปัญหาลอการิทึมแบบไม่ต่อเนื่องบนเส้นโค้งวงรี: เมื่อกำหนดสมการเส้นโค้งและจุดสองจุด จะง่ายต่อการคำนวณผลบวกของจุดเหล่านั้นโดยใช้คุณสมบัติทางเรขาคณิตของเส้นโค้ง แต่จะยากอย่างยิ่งที่จะย้อนกลับการดำเนินการนี้และหาว่าต้องบวกจุดหนึ่งเข้ากับตัวเองกี่ครั้งจึงจะได้จุดอื่น ความไม่สมมาตรนี้ช่วยให้สามารถสร้างและแลกเปลี่ยนกุญแจได้อย่างปลอดภัย ต่างจาก RSA ที่อาศัยปัญหาการแยกตัวประกอบ ความยากของ ECC มาจากโครงสร้างของกรุปเส้นโค้งวงรี
ประวัติศาสตร์
ECC ถูกคิดค้นขึ้นโดย Neal Koblitz และ Victor Miller อย่างอิสระในช่วงปี 1985-1987 ในตอนแรก การยอมรับเป็นไปอย่างช้าๆ เนื่องจากความกังวลเรื่องสิทธิบัตรและความโดดเด่นของ RSA อย่างไรก็ตาม ตั้งแต่ช่วงปี 2000 เป็นต้นมา ECC ได้รับความนิยมในฐานะทางเลือกที่ดีกว่า โดยเฉพาะอย่างยิ่งหลังจากที่สำนักงานความมั่นคงแห่งชาติ (NSA) แนะนำให้ใช้เส้นโค้งวงรีสำหรับข้อมูลลับ โปรโตคอลสมัยใหม่ เช่น TLS 1.3, Signal และระบบบล็อกเชน ส่วนใหญ่ได้กำหนดมาตรฐานบนเส้นโค้ง ECC เช่น Curve25519 และ P-256
ควรใช้เมื่อใด
ECC เหมาะอย่างยิ่งสำหรับการใช้งานที่ต้องการความปลอดภัยสูงพร้อมทรัพยากรจำกัด เช่น อุปกรณ์พกพา ระบบ IoT และระบบฝังตัว ECC เป็นมาตรฐานในโปรโตคอลอินเทอร์เน็ตสมัยใหม่ (TLS 1.3 ใช้ ECDHE) ระบบบล็อกเชน (Bitcoin และ Ethereum ใช้ ECDSA) และแอปส่งข้อความ (Signal ใช้ Curve25519) ควรเลือกใช้ ECC แทน RSA สำหรับระบบใหม่ เนื่องจากประสิทธิภาพที่เหนือกว่าและความปลอดภัยที่เทียบเท่ากัน
ข้อจำกัดและข้อควรพิจารณา
- พื้นฐานทางคณิตศาสตร์ที่ซับซ้อนกว่า RSA ทำให้การนำไปใช้และการวิเคราะห์มีความท้าทายมากขึ้น
- ต้องเลือกพารามิเตอร์ของเส้นโค้งวงรีอย่างระมัดระวัง เส้นโค้งที่อ่อนแอ (เช่น เส้นโค้งที่มีดีกรีการฝังต่ำ) อาจตกเป็นเป้าของการโจมตีได้
- ความปลอดภัยขึ้นอยู่กับเส้นโค้งที่ใช้เป็นอย่างมาก เส้นโค้งที่เป็นมาตรฐานเป็นที่นิยม แต่การเลือกเส้นโค้งเหล่านี้ก็มีความขัดแย้งบางประการ
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ขนาดกุญแจที่เล็กกว่า RSA มากสำหรับระดับความปลอดภัยที่เทียบเท่ากัน ช่วยลดภาระในการจัดเก็บและการส่งข้อมูล
- การสร้างกุญแจ การเข้ารหัส และการถอดรหัสที่เร็วกว่า RSA สำหรับความแข็งแกร่งด้านความปลอดภัยเท่ากัน
- เหมาะสำหรับอุปกรณ์ที่มีทรัพยากรจำกัด เช่น โทรศัพท์มือถือ อุปกรณ์ IoT และสมาร์การ์ด
- มีการกำหนดมาตรฐานและรองรับอย่างแพร่หลายในไลบรารีและการเข้ารหัสลับสมัยใหม่
การประยุกต์ใช้
- การเข้ารหัส TLS/SSL สำหรับ HTTPS และความปลอดภัยเว็บสมัยใหม่โดยใช้การแลกเปลี่ยนกุญแจ ECDHE
- ระบบบล็อกเชนและสกุลเงินดิจิทัล (Bitcoin ใช้ ECDSA บน secp256k1, Ethereum ใช้ secp256k1 สำหรับลายเซ็นบัญชีและธุรกรรม)
- การส่งข้อความและการสื่อสารที่ปลอดภัย (Signal Protocol ใช้ Curve25519 และ X25519)
- การยืนยันตัวตนและลายเซ็นดิจิทัลในสมาร์การ์ด, โมดูลความปลอดภัยฮาร์ดแวร์ และข้อมูลประจำตัวของรัฐบาล
- ความปลอดภัยของระบบ IoT และระบบฝังตัวที่ทรัพยากรในการประมวลผลมีจำกัด
- การวิจัยการเข้ารหัสลับหลังควอนตัม โดยพิจารณาเส้นโค้งไฮเปอร์โบลิกสำหรับอัลกอริทึมที่ทนทานต่อควอนตัม
วิธีการทำงาน
วิธีการทำงาน
เลือกสมการเส้นโค้งวงรี (โดยทั่วไปคือ y^2 = x^3 + ax + b บนฟีลด์จำกัด) จุดกำเนิด G บนเส้นโค้ง และอันดับ n (จำนวนจุดบนเส้นโค้ง) กุญแจส่วนตัว d เป็นจำนวนเต็มสุ่ม และกุญแจสาธารณะ Q = d × G จะถูกคำนวณโดยการคูณจุด
จุดบนเส้นโค้งวงรีจะก่อตัวเป็นกรุปภายใต้การดำเนินการบวกเชิงเรขาคณิต ในการบวกจุดสองจุดที่แตกต่างกัน ให้ลากเส้นตรงผ่านจุดทั้งสอง หาจุดที่เส้นตัดกับเส้นโค้ง และสะท้อนผลลัพธ์ข้ามแกน x การคูณจุดด้วยสองจะใช้เส้นสัมผัสแทน
ในการเข้ารหัสข้อความสำหรับกุญแจสาธารณะ Q ให้สร้างค่าสุ่ม k และคำนวณค่าสองค่า: จุด (x, y) = k × G และข้อความที่เข้ารหัสซึ่งรวมข้อความเข้ากับแฮชของ k × Q
ผู้รับจะใช้กุญแจส่วนตัว d ของตนเพื่อคำนวณ d × (k × G) = k × (d × G) = k × Q เพื่อกู้คืนความลับร่วมและถอดรหัสข้อความ
ข้อผิดพลาดที่พบบ่อย
- การนำการคูณจุดไปใช้โดยไม่ป้องกันการโจมตีช่องทางข้างเคียง อาจทำให้กุญแจส่วนตัวรั่วไหลผ่านการวิเคราะห์เวลาหรือการใช้พลังงาน
- การใช้เส้นโค้งวงรีที่อ่อนแอหรือไม่เป็นมาตรฐาน ซึ่งอาจมีจุดอ่อนทางคณิตศาสตร์ที่ลดทอนความปลอดภัยลงจนไม่มีอยู่จริง
- การไม่ใช้ตัวสร้างเลขสุ่มที่ปลอดภัยสำหรับการเข้ารหัสลับสำหรับคีย์ชั่วคราว k ในลายเซ็น ECDSA ทำให้ลายเซ็นสามารถปลอมแปลงได้
คำถามที่พบบ่อย
เหตุใดกุญแจ ECC ขนาด 256 บิตจึงมีความปลอดภัยเท่ากับกุญแจ RSA ขนาด 2048 บิต?
ปัญหาลอการิทึมแบบไม่ต่อเนื่องบนเส้นโค้งวงรีนั้นยากกว่าปัญหาการแยกตัวประกอบจำนวนเต็ม การแก้ปัญหา ECDLP ต้องใช้เวลาแบบเอ็กซ์โพเนนเชียลแม้จะมีคอมพิวเตอร์ควอนตัมที่ใช้อัลกอริทึมของ Shor ในขณะที่การแยกตัวประกอบจำนวนเต็มจะใช้เวลาแบบโพลีโนเมียลบนคอมพิวเตอร์ควอนตัม
เส้นโค้งวงรีใดที่ใช้กันมากที่สุด?
เส้นโค้งมาตรฐานของ NIST คือ P-256, P-384 และ P-521 Curve25519 ของ Bernstein เป็นที่นิยมในระบบสมัยใหม่เนื่องจากมีความทนทานต่อการโจมตีจากการนำไปใช้ Bitcoin ใช้ secp256k1 และ Ethereum ก็ใช้ secp256k1 สำหรับลายเซ็นบัญชีและธุรกรรม
ECC มีความเสี่ยงต่อคอมพิวเตอร์ควอนตัมหรือไม่?
ใช่ อัลกอริทึมของ Shor สามารถแก้ปัญหาลอการิทึมแบบไม่ต่อเนื่องบนเส้นโค้งวงรีบนคอมพิวเตอร์ควอนตัมได้ ทำให้ทั้ง ECC และ RSA มีความเสี่ยง การวิจัยการเข้ารหัสลับหลังควอนตัมกำลังพัฒนาทางเลือกที่อิงตามแลตทิซ, อิงตามโค้ด และอิงตามพหุนาม
ความแตกต่างระหว่าง ECDH และ ECDSA คืออะไร?
ECDH (Elliptic Curve Diffie-Hellman) เป็นโปรโตคอลการตกลงกุญแจเพื่อสร้างความลับร่วมกันผ่านช่องทางที่ไม่ปลอดภัย ECDSA (Elliptic Curve Digital Signature Algorithm) ใช้สำหรับการสร้างและตรวจสอบลายเซ็นดิจิทัล
ฉันสามารถใช้กุญแจเดียวกันสำหรับ ECDH และ ECDSA ได้หรือไม่?
ในทางเทคนิคเป็นไปได้ แต่ไม่แนะนำ การใช้กุญแจแยกกันสำหรับการเข้ารหัสและการลงนามเป็นไปตามหลักการแยกกุญแจและลดความเสี่ยงของช่องโหว่ที่ละเอียดอ่อน
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Miller, V. S. (1985). Use of Elliptic Curves in Cryptography. In Proceedings of the Advances in Cryptology - CRYPTO 1985, LNCS 218, pp. 417-426.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้วKoblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 203-209.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว