การรู้ปัจจัยของคีย์ช่วยฉันถอดรหัสได้อย่างไร

ฉันเจออัลกอริทึมของ Shor (ซึ่งแก้ปัญหาต่อไปนี้: "ให้จำนวนเต็ม N ค้นหาปัจจัยสำคัญ")

ที่จริงแล้วอัลกอริทึมของ Shor แก้ปัญหา "โดยกำหนดฟังก์ชันเป็นระยะ $f$นั่นคือถ้า $\underbrace{f(f(... f(a))...)}_{k\text{ ครั้ง}} = a$อะไรนะ $k$?"

โดยระบุว่า $f$ อย่างชาญฉลาด เราสามารถใช้มันแก้ปัญหาการแยกตัวประกอบได้ ฉันทราบสิ่งนี้เพราะมันสามารถใช้ในการแก้ปัญหาที่น่าสนใจอื่น ๆ ได้เช่นกัน

ไม่ว่าในกรณีใด สิ่งที่คุณถามจริงๆ คือ "หากเราสามารถแยกตัวประกอบของคีย์ได้ สิ่งนั้นจะช่วยเราทำลาย RSA ได้อย่างไร" โปรดทราบว่าขึ้นอยู่กับความยากของการแยกตัวประกอบที่ RSA ขึ้นอยู่กับ; วิธีอื่นๆ (เช่น Diffie-Hellman) มีความเสี่ยงเท่ากันกับอัลกอริทึมของ Shor แต่ใช้วิธีอื่น $f$ การทำงาน.

ด้วย RSA ตัวแทนสาธารณะ $e$ และเลขชี้กำลังส่วนตัว $d$ มีความเกี่ยวข้องกันโดย $e \cdot d \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$. ปรากฎว่าถ้าเรารู้ปัจจัยสำคัญ $p, q$ และเรารู้จักเลขชี้กำลังสาธารณะ $e$ (ซึ่งกำหนดไว้ในพับลิกคีย์) จึงง่ายต่อการคำนวณเลขยกกำลังส่วนตัว $d$; นั่นทำให้เราสามารถถอดรหัสผ่านได้ทันที $P = C^d \bmod n$.