Skip to content
กลับไปยังผลการค้นหา

การเข้ารหัสลับแบบเส้นโค้งวงรี

ผู้เสนอ
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 และระบบฝังตัวที่ทรัพยากรในการประมวลผลมีจำกัด
  • การวิจัยการเข้ารหัสลับหลังควอนตัม โดยพิจารณาเส้นโค้งไฮเปอร์โบลิกสำหรับอัลกอริทึมที่ทนทานต่อควอนตัม

วิธีการทำงาน

วิธีการทำงาน

1

เลือกสมการเส้นโค้งวงรี (โดยทั่วไปคือ y^2 = x^3 + ax + b บนฟีลด์จำกัด) จุดกำเนิด G บนเส้นโค้ง และอันดับ n (จำนวนจุดบนเส้นโค้ง) กุญแจส่วนตัว d เป็นจำนวนเต็มสุ่ม และกุญแจสาธารณะ Q = d × G จะถูกคำนวณโดยการคูณจุด

2

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

3

ในการเข้ารหัสข้อความสำหรับกุญแจสาธารณะ Q ให้สร้างค่าสุ่ม k และคำนวณค่าสองค่า: จุด (x, y) = k × G และข้อความที่เข้ารหัสซึ่งรวมข้อความเข้ากับแฮชของ k × Q

4

ผู้รับจะใช้กุญแจส่วนตัว 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 ได้หรือไม่?

ในทางเทคนิคเป็นไปได้ แต่ไม่แนะนำ การใช้กุญแจแยกกันสำหรับการเข้ารหัสและการลงนามเป็นไปตามหลักการแยกกุญแจและลดความเสี่ยงของช่องโหว่ที่ละเอียดอ่อน

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. 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
    คัดลอกแล้ว
  2. Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 203-209.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว