นักวิทยาศาสตร์จีนเสนอวิธีถอดรหัสคีย์ RSA-2048 บนคอมพิวเตอร์ควอนตัม

กลุ่มของ นักวิจัยจากศูนย์วิทยาศาสตร์และมหาวิทยาลัยต่างๆ จีน ฉันเสนอวิธีใหม่ในการเพิ่มประสิทธิภาพr กระบวนการแยกตัวประกอบของพารามิเตอร์คีย์ RSA ในคอมพิวเตอร์ควอนตัม

ตามที่นักวิจัย วิธีการที่พวกเขาพัฒนาขึ้นทำให้สามารถใช้คอมพิวเตอร์ควอนตัมได้ ด้วย 372 qubits เพื่อถอดรหัสคีย์ RSA-2048 เมื่อเปรียบเทียบกันแล้ว IBM Osprey ซึ่งเป็นโปรเซสเซอร์ควอนตัมที่ทรงพลังที่สุดที่สร้างขึ้นในปัจจุบันมี 433 คิวบิต และภายในปี 2026 IBM วางแผนที่จะสร้างระบบ Kookaburra ด้วย 4000 คิวบิต

เป็นมูลค่าการกล่าวขวัญว่า วิธีการยังเป็นเพียงทฤษฎีเท่านั้น มันไม่ได้รับการทดสอบในทางปฏิบัติและสร้างความสงสัยในหมู่นักเข้ารหัสบางคน

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

จนถึงตอนนี้ เชื่อกันว่าด้วยการพัฒนาในปัจจุบัน ของคอมพิวเตอร์ควอนตัม, คีย์ RSA ที่มีขนาด 2048 บิตไม่สามารถถอดรหัสได้เป็นเวลานานเนื่องจากใช้อัลกอริทึม Shor แบบคลาสสิก คอมพิวเตอร์ควอนตัมที่มีคิวบิตนับล้านต้องใช้เวลามากในการแยกตัวประกอบคีย์ RSA 2048 บิต

วิธีการที่เสนอโดยนักวิจัยชาวจีนทำให้เกิดความสงสัยในข้อสันนิษฐานนี้ และหากได้รับการยืนยัน จะทำให้สามารถถอดรหัสคีย์ RSA-2048 ที่ไม่ได้อยู่ในระบบของอนาคตอันไกล แต่อยู่ในคอมพิวเตอร์ควอนตัมที่มีอยู่แล้ว

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

ความสงสัย จากนักเข้ารหัสบางคน เป็นเพราะข้อเท็จจริง ที่บทความของนักวิจัยชาวจีนแสดงให้เห็น ใช้วิธีการของคุณกับจำนวนน้อยเท่านั้นซึ่งเป็นลำดับเดียวกับที่อัลกอริทึมของ Schnorr ทำงาน แม้จะมีการอ้างว่าเกินขีดจำกัดของขนาดแล้ว แต่ก็ยังไม่มีหลักฐานหรือรายละเอียดใดๆ ในทางปฏิบัติ วิธีนี้จะแสดงให้เห็นปัจจัยจำนวนเต็ม 48 บิตโดยใช้คอมพิวเตอร์ควอนตัม 10 คิวบิต

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

จำนวนของ qubits ที่ต้องการคือ O(logN/loglogN) ซึ่งเป็น sublinear ในความยาวบิตจำนวนเต็ม N ทำให้เป็นอัลกอริทึมการแยกตัวประกอบแบบ qubit ที่ประหยัดที่สุดจนถึงปัจจุบัน เราสาธิตอัลกอริทึมในการทดลองโดยแยกตัวประกอบจำนวนเต็มสูงสุด 48 บิตกับ 10 คิวบิตตัวนำยิ่งยวด ซึ่งเป็นจำนวนเต็มที่ใหญ่ที่สุดที่แยกตัวประกอบในอุปกรณ์ควอนตัม เราประเมินว่าวงจรควอนตัมที่มี 372 คิวบิตเชิงกายภาพและความลึกหลายพันเป็นสิ่งจำเป็นในการท้าทาย RSA-2048 โดยใช้อัลกอริทึมของเรา การศึกษาของเราแสดงให้เห็นถึงคำมั่นสัญญาที่ดีในการเร่งการประยุกต์ใช้คอมพิวเตอร์ควอนตัมที่มีเสียงดังในปัจจุบัน และปูทางสำหรับการแยกตัวประกอบของจำนวนเต็มขนาดใหญ่ที่มีนัยสำคัญทางการเข้ารหัสที่เหมือนจริง

มีการกล่าวว่าสมมติฐานที่ว่า 372 คิวบิตจริงจะเพียงพอในการแยกตัวประกอบของคีย์ RSA-2048 นั้นเป็นไปตามทฤษฎี ดังนั้นจึงเป็นไปได้มากว่าวิธีควอนตัมที่ใช้อัลกอริทึมของ Schnorr จะมีปัญหาในการปรับขนาดเหมือนกันและใช้งานไม่ได้เมื่อแยกตัวประกอบจำนวนมาก .

หากปัญหาเกี่ยวกับการปรับขนาดได้รับการแก้ไขจริง ๆ ความปลอดภัยของอัลกอริธึมการเข้ารหัสลับตามความซับซ้อนของการแยกตัวประกอบจำนวนเฉพาะจำนวนมากจะไม่ถูกทำลายในระยะยาวอย่างที่คาดไว้ แต่ในวันนี้

สุดท้ายนี้ หากสนใจอยากทราบข้อมูลเพิ่มเติม สามารถเข้าไปดูรายละเอียดได้ที่ ลิงค์ต่อไปนี้