Score:0

จะหาตัวชี้กำลังซ้ำในการโจมตีแบบวนซ้ำได้อย่างไร

ธง cn

ในบทความของ Simmons และ Norris พวกเขาแสดงให้เห็นถึงการโจมตีแบบขี่จักรยานด้วยตัวอย่างต่อไปนี้:

p = 383 q = 563 s = 49 และ t = 56957 ( a เฉพาะ)

ผู้โจมตีทราบข้อมูลสาธารณะ r = pq = 215,629 , s = 49 และข้อความที่เข้ารหัส C. โดยสร้าง C1 = ค49 , ค2 = ค149ฯลฯ เขาจะพบ คเจ = C สำหรับ 1,2,5 หรือ 10

ฉันไม่เข้าใจว่าพวกเขาคิดได้อย่างไรว่าพวกเขาจะมี M = Cจ-1 ไม่เกิน 10 ขั้นตอน? พวกเขาบอกว่า 49 เป็นของเลขชี้กำลัง 10 mod Ï(r) = 214,684 แต่ฉันไม่แน่ใจว่ามันหมายความว่าอะไร ใครช่วยอธิบายที โปรด. ขอขอบคุณ!

fgrieu avatar
ng flag
บทความที่อ้างถึงคือ: Gustavus J. Simmons & Michael J. Norris (1977) ความคิดเห็นเบื้องต้นเกี่ยวกับ M.I.T. ระบบรหัสลับสาธารณะ, Cryptologia, 1:4, 406-414, [paywalled](https://doi.org/10.1080/0161-117791833219)
kelalaka avatar
in flag
[วงจรการโจมตี RSA](https://crypto.stackexchange.com/q/1572/18298)
Score:2
ธง ru

การโจมตีแบบหมุนเวียนด้วยเลขชี้กำลังการเข้ารหัส $s$ อาศัย $s$ มีโมดูโลลำดับการคูณขนาดเล็กลำดับการคูณของไซเฟอร์เท็กซ์ ถ้า $c^v\equiv 1\pmod{pq}$ และ $s^w\equiv 1\pmod v$ แล้วเข้ารหัสซ้ำๆ $ค$ สำหรับ $w$ ครั้งให้ $$c^{s\times s\times\cdots\times s\times s}\equiv c^{s^w}\pmod{pq}.$$ เรารู้ว่า $s^w=kv+1$ สำหรับบางคน $k$ ดังนั้น $$c^{s^w}=c^{kv}c\equiv c\pmod{pq}.$$

ในกรณีของคุณ $pq=215629$ และ $s=49$. ดังนั้นเราจึงรู้ว่า $v$ แบ่ง $\phi(pq)=214684$. สิ่งนี้บอกเราว่า $w$ หารลำดับการคูณของ $s$ โมดูโล 214684 การคำนวณอย่างง่ายจะแสดงให้เห็นว่า $$49^{10}\equiv 1\pmod{214684}$$ ดังนั้น $w$ ต้องหาร 10 จะได้ค่าของ $w$ น้อยกว่า 10 สำหรับบางค่าของ $ค$ (เช่น. $ค=32$).

ถ้าเราเขียน $\mathrm{ord}(x,m)$ สำหรับลำดับการคูณของ $x$ โมดูโล $m$ (เช่น จำนวนเต็มที่น้อยที่สุด $t>0$ ดังนั้น $x^t\equiv 1\pmod m$ จากนั้นนิพจน์ทั่วไปสำหรับจำนวนการวนซ้ำคือ $$\mathrm{ord}\left(s,\mathrm{ord}(c,pq)\right).$$

cn flag
สมบูรณ์แบบ! มีเหตุผล. ขอบใจ!

โพสต์คำตอบ

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