เปรียบเทียบ ECDSA กับ RSA

บทนำ

เมื่อเร็ว ๆ นี้มีการพูดคุยกันมากมายเกี่ยวกับข้อดีข้อเสียของ อาร์เอส[01]
และ ECDSA[02] ในชุมชน crypto สำหรับมือใหม่พวกเขาเป็นสองคน
อัลกอริทึมลายเซ็นดิจิตอลที่ใช้กันอย่างแพร่หลายมากที่สุด แต่สำหรับเทคโนโลยีมากขึ้น
เข้าใจง่ายมากที่จะติดตามข้อเท็จจริง บทความนี้เป็น
พยายามที่จะทำให้การเปรียบเทียบทั้งสองอัลกอริทึมง่ายขึ้น แม้ว่านี่จะไม่ใช่
เรียงความทางเทคนิคอย่างลึกซึ้งผู้อ่านที่ใจร้อนมากขึ้นสามารถตรวจสอบจุดสิ้นสุดของ
บทความสำหรับตาราง TL ด่วน; DR พร้อมบทสรุปของการสนทนา

ECDSA กับ RSA

ECDSA และ RSA เป็นอัลกอริทึมที่ใช้ การเข้ารหัสคีย์สาธารณะ[03] ระบบ
เพื่อจัดเตรียมกลไกสำหรับ การรับรอง. การเข้ารหัสคีย์สาธารณะคือ
วิทยาศาสตร์ของการออกแบบระบบเข้ารหัสที่ใช้คู่คีย์: สาธารณะ
สำคัญ (ดังนั้นชื่อ) ที่สามารถแจกจ่ายได้อย่างอิสระกับทุกคนพร้อมกับ
ตรงกัน กุญแจส่วนตัวซึ่งเจ้าของเท่านั้นรู้จัก การรับรอง
หมายถึงกระบวนการตรวจสอบว่าข้อความที่ลงนามด้วยคีย์ส่วนตัวคืออะไร
สร้างโดยเจ้าของของคีย์ส่วนตัวที่เฉพาะเจาะจง อัลกอริทึมที่ใช้สำหรับ
การรับรองความถูกต้องเป็นที่รู้จักกันโดยรวมว่า อัลกอริธึมลายเซ็นดิจิตอล [04]

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

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

การนำมาใช้

RSA เป็นมาตรฐานอุตสาหกรรมสำหรับการเข้ารหัสคีย์สาธารณะเป็นเวลาหลายปี
ตอนนี้. SSL ส่วนใหญ่ /TLS ใบรับรองคือ (และยังคงอยู่) กำลังลงชื่อด้วยคีย์ RSA
แม้ว่าปัจจุบัน CAs ส่วนใหญ่จะมีการดำเนินการรองรับ ECDSA
ใบรับรองการใช้งานระยะยาวนี้ได้นำไปสู่ระบบดั้งเดิมหลายระบบเท่านั้น
สนับสนุน RSA ดังนั้นหากผู้ขายต้องการความเข้ากันได้แบบย้อนหลังกับเก่า
ซอฟต์แวร์ไคลเอ็นต์จะถูกบังคับให้ใช้ใบรับรองที่ลงชื่อด้วย RSA ปัจจุบัน
แม้ว่าลูกค้าที่ทันสมัยส่วนใหญ่ใช้การสนับสนุน ECDSA ซึ่งจะ
อาจลบข้อ จำกัด ความเข้ากันได้นี้ในอนาคตอันใกล้

กำหนดมาตรฐาน

RSA เป็นมาตรฐานแรกสำหรับ SSL /TLS ในปี 1994 [06] ในขณะที่ ECDSA ได้รับการแนะนำ
ในสเปคของ TLS v1.2 ในปี 2008 [07] ความแตกต่างของอายุนี้บ่งชี้ว่า
ความไม่เท่าเทียมกันในการกำหนดมาตรฐานที่อธิบายวิธีปฏิบัติที่ดีที่สุดสำหรับ
แต่ละอัลกอริทึม แม้ว่ามาตรฐาน RSA ได้รับการวิจัยอย่างกว้างขวางและ
ตรวจสอบแล้ว ECDSA ไม่เห็นความสนใจมากนัก เมื่อเร็ว ๆ นี้การสนับสนุนของสิ่งนี้
อัลกอริทึมโดย CA ที่สำคัญและการนำไปใช้ใน SSL /TLS ลูกค้ามี
ส่งผลให้มีการเผยแพร่งานวิจัยอย่างกว้างขวางมากขึ้น แต่ก็ยังคงเป็น
รูปแบบที่ค่อนข้างใหม่ สิ่งนี้ทำให้ห้องมีข้อบกพร่องหรือการออกแบบที่ยังไม่ได้เปิด
การใช้งานที่ผิดพลาดถูกเปิดเผยในอนาคต

อัตราส่วนขนาดคีย์ต่อความปลอดภัย

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

ในเรื่องนี้คีย์สาธารณะ RSA 2048 บิตทั่วไปให้ระดับความปลอดภัยของ
112 บิต อย่างไรก็ตาม ECDSA ต้องใช้กุญแจสาธารณะขนาด 224 บิตเพื่อจัดเตรียม
ระดับความปลอดภัย 112 บิตเดียวกัน ความแตกต่างที่โดดเด่นในขนาดปุ่มมีสอง
นัยสำคัญ ขนาดคีย์ที่เล็กลงต้องการแบนด์วิดท์น้อยลงในการตั้งค่า
SSL /TLS สตรีมซึ่งหมายความว่าใบรับรอง ECDSA เหมาะสำหรับมือถือ
การใช้งาน ยิ่งไปกว่านั้นใบรับรองดังกล่าวสามารถเก็บไว้ในอุปกรณ์ที่มีมาก
ข้อ จำกัด ของหน่วยความจำที่ จำกัด มากขึ้นข้อเท็จจริงที่อนุญาตให้ m /TLS สแต็คที่จะเป็น
ดำเนินการในอุปกรณ์ IoT โดยไม่ต้องจัดสรรทรัพยากรมากมาย การตีพิมพ์
การวิจัยยังแสดงให้เห็นว่า ECDSA มีประสิทธิภาพมากกว่า [09] ในการนำไปฝังในเครื่อง
อุปกรณ์

ความซับซ้อนของประสิทธิภาพและเวลา

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

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

สิ่งต่าง ๆ มีความซับซ้อนสำหรับระดับความปลอดภัยที่สูงขึ้น ตัวอย่างเช่นในที่สุด
การกำหนดค่าทั่วไปของระดับความปลอดภัย 112 บิต RSA ต้องใช้ 2048 บิต
เมื่อเทียบกับ ECDSA ที่ต้องการคีย์ 224 บิต ในระดับทั่วไปถัดไปของ 128 บิต RSA
ต้องใช้คีย์ 3072 บิตในขณะที่ ECDSA มีเพียง 256 บิต ผลลัพธ์นี้เป็นของ RSA
ประสิทธิภาพจะลดลงอย่างมากในขณะที่ ECDSA ได้รับผลกระทบเพียงเล็กน้อยเท่านั้น เช่น
เป็นผลมาจากปัญหาการปรับสเกลแม้ว่า RSA นั้นดูเหมือนจะมีประสิทธิภาพมากกว่า
ขณะที่ความต้องการด้านความปลอดภัยที่เพิ่มขึ้นอย่างต่อเนื่องสามารถทำได้ดีมาก
ECDSA เป็นทางออกที่แท้จริงในอนาคต

ความต้านทานหลังควอนตัม

อัลกอริทึมของแคระแกร็น [10] เป็นอัลกอริทึมที่รู้จักกันดีสำหรับการทำลายคีย์ RSA โดยใช้
คอมพิวเตอร์ควอนตัม เนื่องจากไม่มีการใช้งานจริง (สาธารณะ) ของ
เครื่องดังต่อไปนี้คือการคาดเดาเกี่ยวกับอนาคตของกุญแจสาธารณะ
การเข้ารหัส ในขณะของการเขียนนี้การใช้งาน Shor's ที่ดีที่สุด
อัลกอริทึมสามารถเอาชนะการเข้ารหัส RSA แบบ 15 บิตได้ แม้ว่าสิ่งนี้จะไม่ส่งเสียง
ที่เกี่ยวข้องกับการวิจัยมากขึ้นมุ่งสู่การคำนวณควอนตัม RSA
อาจประสบปัญหาร้ายแรงได้ตลอดเวลา

ผู้ให้การสนับสนุนสำหรับ ECDSA ไม่ควรฉลองอย่างรวดเร็วเพราะเป็นรูปไข่
การเข้ารหัสโค้ง ยังเปราะบาง [11] เป็นเวอร์ชันดัดแปลงของ Shor's
ขั้นตอนวิธี ดังนั้นหากทั้งสอง ciphers สามารถถูกทำลายโดยคอมพิวเตอร์ควอนตัม
ตัวชี้วัดเป้าหมายเพียงอย่างเดียวคือความซับซ้อนที่ต้องใช้ในการดำเนินการ
โจมตี. จากการวิจัยสาธารณะคีย์ RSA 2048 บิตต้องการ 4098 qubits
(และประตู Tofolli 5.2 ล้านล้าน) ต้องพ่ายแพ้ขณะที่ปุ่ม ECDSA 256 บิต
ต้องการเพียง 2330 qubits (และ 126 พันล้านประตู Tofolli) ดังนั้น RSA จึงมีมากขึ้น
แพงที่จะทำลายโดยใช้เครื่องควอนตัมตามทฤษฎี

สรุป

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

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

TL; DR ตาราง

อ้างอิง

• [01] อัลกอริทึม RSA
• [02] อัลกอริทึม ECDSA
• [03] การเข้ารหัสคีย์สาธารณะ
• [04] อัลกอริธึมลายเซ็นดิจิตอล
• [05] ความซับซ้อนของ NP
• [06] SSL v.0.0 RFC
• [07] TLS v.1.2 อาร์เอฟซี
• [08] ระดับความปลอดภัย
• [09] RSA vs ECC สำหรับระบบสมองกลฝังตัว
• [10] Algorigthm ของ Shor
• [11] การประมาณทรัพยากรควอนตัมสำหรับ ECDL