Prime Factorization ทำลาย ECDSA อย่างไร?

Question

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

Answer 1

อย่างไรก็ตามตามความเข้าใจของฉันจุดประสงค์เดียวของอัลกอริทึมของ Shor คือการค้นหาปัจจัยสำคัญของตัวเลขจำนวนมากอย่างรวดเร็ว

ความเข้าใจของคุณไม่ถูกต้อง อัลกอริทึมของ Shorสามารถใช้ได้กับทั้งจำนวนเต็มตัวประกอบและการค้นหาลอการิทึมแบบไม่ต่อเนื่อง

อัลกอริทึมของ Shor ทำงานเป็นสองส่วน ขั้นแรกให้เปลี่ยนปัญหา (การแยกตัวประกอบหรือบันทึกแยก) เป็นหนึ่งในการค้นหาช่วงเวลาของฟังก์ชัน ขั้นตอนแรกนี้ไม่ใช่ควอนตัม จากนั้นจะหาช่วงเวลาโดยใช้ Quantum Fourier Transform (QFT) เมื่อคุณมีช่วงเวลาของฟังก์ชันแล้วขั้นตอนแรกสามารถย้อนกลับเพื่อค้นหาวิธีแก้ปัญหาเดิมได้

อัลกอริทึมของ Shor สามารถใช้งานได้โดยไม่มีส่วน Quantum และจำลอง QFT แม้ว่าจะช้ากว่าอัลกอริทึมแบบคลาสสิกที่รู้จักกันดีมากก็ตาม การใช้งานหลามนี้จำลอง QFT และอาจช่วยในการทำความเข้าใจ