ต้องการความช่วยเหลือเพื่อทำความเข้าใจการโจมตีโมดูลัสทั่วไปของ RSA เพื่อรับคีย์ส่วนตัว

ฉันกำลังเรียนรู้เกี่ยวกับการโจมตีโมดูลัสทั่วไป และเรียนรู้ว่าการโจมตีโมดูลัสสาธารณะสามารถค้นหาคีย์ส่วนตัวได้ สมมติว่ามีผู้ใช้ 2 คนที่มีคีย์สาธารณะและคีย์ส่วนตัว $(e_1, d_1)$ และ $(e_2, d_2)$. สถานการณ์จำลองคือผู้โจมตีมีคีย์สาธารณะและคีย์ส่วนตัว $(e_2, d_2)$ และรหัสสาธารณะของเหยื่อ $e_1$ นี่คือขั้นตอนในการรับรหัสลับ:

1. $t= e_2\cdot d_2-1$
2. ผู้โจมตีใช้อัลกอริธึมแบบยุคลิดแบบขยายเพื่อค้นหา $f=\gcd(t,e_1)$ เลขคู่ของใคร $(ร,ส)$ ตอบสนองสมการ $r\cdot t + s\cdot e_1 = f$
3. ถ้า $ฉ=1$ ชุด $d_1' = s$ และคืนรหัสส่วนตัว $d_1'$
4. ถ้า $f\neq 1$ ชุด $t=\frac เสื้อ s$ และย้อนกลับขั้นตอนที่ 2

ฉันมีตัวอย่างด้วย $d_1=17, M = 25$ เป็นสองค่าที่เราควรหา n = 253 (โมดูลัสร่วม) $e_1 = 13$ (กุญแจสาธารณะของเหยื่อ) $e_2 = 23$ (รหัสสาธารณะของผู้โจมตี) $d_2 = 67$ (คีย์ส่วนตัวของผู้โจมตี) $C = 27$ (ไซเฟอร์เท็กซ์). ผู้โจมตีจะพบ $d_1'$ ตามขั้นตอน:

1. $t= e_2\cdot d_2-1 = 23\cdot 67 = 1540$
2. $\gcd(t,e_1) = 1 \นัย r = -2, s = 237$
3. ดังนั้น $d_1' = s = 237$
4. ตรวจสอบ $M = C^{d_1} \bmod n = 27^{237} \bmod 253 = 25$

ปัญหาคือฉันไม่เข้าใจว่าทำไมเราถึงพบรหัสลับด้วยขั้นตอนดังกล่าว ใครช่วยอธิบายฉันหน่อยได้ไหม

เราจะใช้ข้อเท็จจริงต่อไปนี้อย่างหนัก: สำหรับโมดูลัสสาธารณะคงที่ $n$ ผลคูณของจำนวนเฉพาะ, จำนวนเต็มคู่ $(จ,ง)$ สร้างเลขยกกำลัง RSA ที่ตรงกัน [นั่นคือกับ $c\mapsto c^d\bmod n\,=\,m$ สามารถถอดรหัสข้อความธรรมดาใด ๆ ได้อย่างน่าเชื่อถือ $m$ ใน $[0,น)$ เข้ารหัสต่อ $m\mapsto m^e\bmod n\,=\,c$ ] ถ้าและเฉพาะในกรณีที่$$e\cdot d\equiv1\pmod{\lambda(n)}$$ที่ไหน $\แลมบ์ดา$ คือ ฟังก์ชันคาร์ไมเคิล. ที่สามารถแสดงต่อได้จากนิยามของ $\แลมบ์ดา(n)$ เป็นจำนวนเต็มบวกอย่างเคร่งครัดน้อยที่สุด $y$ ดังนั้น $m^y\equiv 1\pmod n$ สำหรับทุกอย่าง $m\in\mathbb Z^*$. สิ่งนี้ถือโดยไม่คำนึงถึงเครื่องหมายของ $d$.

ก็เป็นไปตามนั้น $t$ ของขั้นตอนที่ 1 ของอัลกอริทึมของคำถามมีอยู่จริง $k\in \mathbb Z$ กับ $t=k\cdot\lambda(n)$.

หากพบอัลกอริทึม $ฉ=1$ ในการดำเนินการครั้งแรกของขั้นตอนที่ 2 มันจึงถือ $r\cdot k\cdot\lambda(n)+s\cdot e_1=1$, เพราะฉะนั้น $s\cdot e_1=1+(-r\cdot k)\cdot \lambda(n)$ดังนั้นเมื่ออัลกอริทึมตั้งค่า $d'_1=s$ ในขั้นตอนที่ 3 มันถือ $e_1\cdot d'_1\equiv1\pmod{\lambda(n)}$. โดยใช้ข้อเท็จจริงข้อแรก $(e_1,d'_1)$ เป็นคู่ของเลขชี้กำลัง RSA สำหรับโมดูลัสสาธารณะ $n$. หากเราต้องการ $d'_1$ ที่ไม่เป็นลบเราสามารถทำได้ $d'_1=s\bmod t$ซึ่งตามความหมายแล้วอยู่ในช่วง $[0,t)$ และยังเป็นเช่นนั้น $e_1\cdot d'_1\equiv1\pmod{\lambda(n)}$.

สิ่งที่ผิดพลาดเมื่อ $f\ne1$ ในการดำเนินการขั้นตอนที่ 2 ครั้งแรก บ่อยครั้ง $s$ จะไม่แบ่ง $t$ ในขั้นตอนที่ 4 ป้องกันการใช้อัลกอริทึมตามที่เป็นอยู่ ตัวอย่าง: $p=13$, $q=19$, $n=247$, $\varphi(n)=216$, $\lambda(n)=36$, $e_1=91$, $e_2=25$, $d_1=19$, $d_2=121$, $t=3024$, $r=-4$, $s=133$, $ฉ=7$, $t/s=432/19\not\in\mathbb Z$.

การเปลี่ยนแปลง $t:=\frac เสื้อ s$ ถึง $t:=\frac เสื้อ f$ ในขั้นตอนที่ 4 รับประกันการหาร และปล่อยให้อัลกอริทึมทำงาน การโต้แย้ง: $f$ แบ่ง $e_1$, และ $\gcd(e_1,\lambda(n))=1$, ดังนั้น $f$ เป็นโคไพร์มด้วย $\แลมบ์ดา(n)$ดังนั้นเราจึงรีสตาร์ทขั้นตอนที่ 2 ด้วย $t$ ยังคงเป็นทวีคูณของ $\แลมบ์ดา(n)$.

อีกทางหนึ่ง: ให้ $(n,e_2,d_2)$ ฝ่ายตรงข้ามสามารถปัจจัย $n$ (ดู นี้) และจากที่ได้รับ $\hat{d_1}=e^{-1}\bmod\lambda(n)$ การจับคู่ $(n,e_1)$, มักจะมี $\หมวก{d_1}$ เล็กกว่า/เร็วกว่า $d'_1$; หรือรับรหัสส่วนตัวที่ใช้งานได้ในแบบฟอร์มที่อนุญาต การทำงานของ CRT ดังนั้นการถอดรหัสหรือลายเซ็นจึงรวดเร็วยิ่งขึ้น