Score:1

RSA : ตัวประกอบร่วมระหว่าง M และ n

ธง cn

สมมติว่าเรามีการเข้ารหัส RSA แบบคลาสสิก โดยที่ n = p*q สำหรับ C ที่กำหนด ฉันเห็นบนอินเทอร์เน็ตว่า RSA อาจอ่อนแอหากเรารู้ว่าข้อความธรรมดา M และ n มีปัจจัยร่วมกัน อย่างไรก็ตาม ฉันไม่สามารถหาข้อพิสูจน์ได้

เรารู้ว่า $M=C^e \space mod\;n$โดยที่ e เป็นกุญแจสาธารณะ ฉันพยายามจะพูดอย่างนั้น $M = a + k*n$โดยที่ a และ k เป็นจำนวนเต็มบวก และทำซ้ำอัลกอริทึม ดังนั้น :

$C = M^e\;mod\;n = (a + k*n)^e\;mod\;n = a^e\;mod\;n$

และ

$M = C^d\;mod\;n = a^{d*e}\;mod\;n$

อย่างไรก็ตาม ฟังดูไร้ประโยชน์ เนื่องจากเราไม่รู้ค่า (แม้ว่าจะต้องใช้กำลังที่โหดร้าย เราก็ต้องใช้ค่าจำนวนมากเพื่อคำนวณหาก $n$ มีขนาดใหญ่) และ $d$เห็นได้ชัดว่าเนื่องจากเป็นคีย์ส่วนตัว ใครก็ได้ช่วยฉันในเรื่องนี้ที

Score:3
ธง my

สำหรับ C ที่กำหนด ฉันเห็นบนอินเทอร์เน็ตว่า RSA อาจอ่อนแอหากเรารู้ว่าข้อความธรรมดา M และ n มีปัจจัยร่วมกัน อย่างไรก็ตาม ฉันไม่สามารถหาข้อพิสูจน์ได้

มันค่อนข้างง่าย เรารู้ทั้งสองอย่าง $C$ และ $n$; ถ้า $M$ มีปัจจัยร่วมกับ $n$ก็เช่นกัน $C$. ดังนั้นเราจึงสามารถคำนวณได้ $\gcd(C, n)$. เนื่องจากเราทราบดีว่า $M$ และ $n$ มีตัวประกอบร่วมกัน นี่ไม่ใช่ 1; เราคิดว่า $C < n$จึงไม่เป็นเช่นนั้น $n$. ดังนั้นจึงต้องเป็นปัจจัยที่เหมาะสมของ $n$; ถ้า $n$ เป็นผลคูณของจำนวนเฉพาะสองตัว, นี่จะเป็นหนึ่งในนั้น, และตัวประกอบเฉพาะสองตัวของ $n$ เป็นแล้ว $\gcd(C, n)$ และ $n / \gcd(C, n)$.

เมื่อเราแยกตัวประกอบของ $n$ แล้ว (สมมติว่าเรารู้ค่า $e$) การคำนวณ $d$ ตรงไปตรงมา

poncho avatar
my flag
@Marth83: ดีกว่าไหม
Marth83 avatar
cn flag
ใช่ นั่นคือสิ่งที่ฉันสงสัย ขอบคุณ!

โพสต์คำตอบ

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