Score:1

ทำไมเคล็ดลับของ Shamir สำหรับ RSA จึงใช้งานได้

ธง fr

ฉันได้อ่านแล้วว่าเคล็ดลับของ Shamir สามารถปกป้อง RSA ด้วย CRT จากการโจมตีที่ผิดพลาด อย่างไรก็ตาม ฉันไม่ชัดเจนว่าทำไมสมการต่อไปนี้ $$ s_{p}^{*}=m^{d \bmod \varphi(p \cdot t)} \bmod p \cdot t \ s_{q}^{*}=m^{d \bmod \varphi(q \cdot t)} \bmod q \cdot t $$ หมายความว่า: $$ s_{p}^{*} = s_{q}^{*} \bmod t $$

fgrieu avatar
ng flag
นั่นไม่ใช่กลอุบายของ Shamir อย่างที่ฉันรู้ ซึ่งคำนวณ $x^a\,y^b\bmod n$ ที่ประมาณ 60% ของค่าใช้จ่ายในการคำนวณเป็น $(x^a\bmod n)\,y^b\bmod n$ OTOH Shamir มีลูกเล่นมากมาย นอกจากนี้ แม้ว่าสมการดังกล่าวจะคงอยู่ แต่นั่นไม่ใช่มาตรการมาตรฐานในการป้องกันการโจมตีจากความผิดพลาด ซึ่งก็คือการตรวจสอบ $s^e\bmod n=m$
Johny Dow avatar
fr flag
@fgrieu มันมีชื่อว่าเคล็ดลับของ Shamir ใน [หัวข้อในวิทยาการเข้ารหัสลับ â CT-RSA 2009](https://link.springer.com/book/10.1007/978-3-642-00862-7) และนั่นคือสิ่งที่ฉันได้รับ ชื่อจาก.
fgrieu avatar
ng flag
ใช่ ตอนนี้ฉันเห็นว่ามันอยู่ใน Matthieu Rivain [การรักษาความปลอดภัย RSA กับการวิเคราะห์ข้อผิดพลาดโดย การเพิ่มทวีคูณแบบลูกโซ่](https://eprint.iacr.org/2009/165.pdf) (เวอร์ชันอัปเดต) แต่เดิม [ในการดำเนินการของ CT-RSA 2009](https://doi.org/10.1007/978- 3-642-00862-7_31). ถึงกระนั้น [ข้อมูลอ้างอิงนี้](https://doi.org/10.1007/978-1-4419-5906-5_1157) ทำให้ _Shamir's Trick_ มีความหมายเหมือนกันกับ [_Simultaneous Exponentiation_](https://doi.org/10.1007/978-1 -4419-5906-5_45).
Score:2
ธง ru

เรามี $\varphi(t)|\varphi(pt)$ และ $\varphi(t)|\varphi(qt)$ ดังนั้นหาก $d_1$ และ $d_2$ เป็นเลขยกกำลังสำหรับ $s_p^*$ และ $s_q^*$ แล้ว $d=d_1+k_1\varphi(t)$ และ $d=d_2+k_2\varphi(t)$ สำหรับจำนวนเต็มบางตัว $k_1$ และ $k_2$. ก็เป็นไปตามนั้น $d_1=d_2+(k_2-k_1)\varphi(t)$ และด้วยเหตุนี้ $$d_1\equiv d_2\pmod{\varphi(t)}.$$

ก็เป็นไปตามนั้น $m^{d_1}\equiv m^{d_2}\pmod t$ โดยทฤษฎีบทของออยเลอร์

Johny Dow avatar
fr flag
ฉันเพิ่งรู้ว่าฉันไม่เข้าใจว่าทำไม $d_1\equiv d_2\pmod{\phi(t)}$ คุณช่วยอธิบายเพิ่มเติมได้ไหม ขอขอบคุณ!

โพสต์คำตอบ

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