ขนาดคีย์สาธารณะสำหรับเส้นโค้งวงรีต่างๆ

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

ถ้าคุณมีเส้นโค้งวงรีที่มีกลุ่มย่อยขนาดใหญ่ $คิว$ (ซึ่งเป็นจำนวนเฉพาะ) จากนั้นเรารู้วิธีคำนวณบันทึกแยกภายในกลุ่มย่อยนั้นใน $O(\sqrt{q})$ เวลา และใช้กับเส้นโค้งวงรีทั้งหมด (จริง ๆ แล้วคือทุกกลุ่ม)

เพื่อให้การโจมตีครั้งนี้เกิดขึ้น $2^{128}$ เวลา เราต้องการ $q \ประมาณ 2^{256}$.

และเนื่องจากทฤษฎีบท Hasse สำหรับเส้นโค้งเฉพาะของลักษณะเฉพาะ $p$, เรามี $p + 2\sqrt{p} > q$หรืออีกนัยหนึ่งคือตัวเล็กที่สุด $p$ ได้ประมาณ 256 บิต

วิธีมาตรฐานในการแสดงรหัสสาธารณะคือการให้ $x$ ประสานงานเป็นจำนวนเต็ม นี่คือค่าระหว่าง 0 ถึง $p-1$; นั่นคือค่า 256 บิต

ดังนั้น การเลือกเส้นโค้งอื่นที่ไม่ใช่ Curve25519, secp256k1 หรือ P256 ไม่ได้ช่วยอะไรเราเลย เส้นโค้งทางเลือกนั้นอาจลดความปลอดภัยหรือมีรหัสสาธารณะที่มีขนาดใหญ่น้อยที่สุด

เกี่ยวกับสิ่งเดียวที่คุณสามารถลองคิดวิธีการส่งสัญญาณที่ลดลงได้ $x$ ประสานงาน; แนวทางง่ายๆ อย่างหนึ่งคือการเลือกเสมอ $x$ ประสานงานกับ $k$ บิต 0 ที่ด้านบน (และไม่ส่งสัญญาณเหล่านั้น $k$ บิตอย่างชัดเจน); การค้นหาคีย์ดังกล่าวโดยใช้การสุ่มตัวอย่างการปฏิเสธจะใช้เวลา $O(2^k)$ เวลาและจะบันทึก $k$ บิต - อาจทำได้ถ้าคุณต้องการบันทึกหนึ่งหรือสองไบต์ - เห็นได้ชัดว่าเป็นไปไม่ได้ที่จะบันทึกมากกว่านั้น ฉันไม่ทราบวิธีการที่ชาญฉลาดกว่าในการค้นหากุญแจสาธารณะที่ตรงตามเทคนิคการประหยัดพื้นที่ที่คล้ายกัน