Score:1

ช่องโหว่ RSA เมื่อ M ที่เข้ารหัสไม่ได้อยู่ร่วมกับ N

ธง kr

ฉันได้ทดสอบกับกรณีทดสอบสองสามข้อแล้ว ดูเหมือนว่าข้อความเข้ารหัส $M^e$ ของ RSA มีค่าเท่ากับ N เสมอเมื่อ e=3 มีเหตุผลว่าทำไม? จะเกิดอะไรขึ้นถ้าไซเฟอร์เท็กซ์ $M^e$ ไม่ใช่ coprime กับ M เมื่อ e=3?

fgrieu avatar
ng flag
เมื่อ $(N,e)$ เป็นคีย์สาธารณะ RSA ที่ถูกต้อง โดยที่ $N$ เป็นผลคูณของจำนวนเฉพาะลับที่แตกต่างกันสองตัว $p$ และ $q$ มีความน่าจะเป็นประมาณ $1/p+1/q$ ที่ข้อความสุ่ม $M $ นั้น $M^e$ ไม่เหมือนกับ $N$ เนื่องจากทั้ง $p$ และ $q$ ต้องมีค่ามาก (ทศนิยมหลายร้อยหลัก) เพื่อให้ RSA ปลอดภัย ความน่าจะเป็นดังกล่าวจึงไม่มีนัยสำคัญเลยในการใช้งานจริงของ RSA คำถามกำลังพิจารณาบางสิ่งที่ใช้งานจริงจะไม่เกิดขึ้นสำหรับการสุ่มหรือการสุ่ม $M$ หรือสำหรับ $M\in[1,N)$ ที่เลือกโดยผู้ที่ไม่รู้ (หรือไม่สามารถหา) การแยกตัวประกอบของ $N$ .
kelalaka avatar
in flag
RSA เป็นการเปลี่ยนแปลงประตูกล นี่หมายความว่าคุณมีอะไร?
Score:3
ธง gb

เมื่อไร $N = pq$ เป็นผลคูณของจำนวนเฉพาะสองตัว ซึ่งเป็นจำนวนเดียวที่ไม่มีจำนวนเฉพาะ $N$ คือผู้ที่มีอย่างใดอย่างหนึ่ง $p$ หรือ $คิว$ เป็นปัจจัย เป็นไปได้ที่จะมีอย่างแน่นอน $ม^3$ หารด้วยอย่างใดอย่างหนึ่ง $p$ หรือ $คิว$ ดังนั้นการสังเกตของคุณจึงไม่เป็นความจริงโดยทั่วไป ตัวอย่าง:

$$ ม = 42\ N = 7*13 = 91\ M^3 \equiv 14 \pmod{91} $$ เห็นได้ชัดว่า 14 และ 91 ไม่ใช่ coprime - ทั้งคู่ใช้ร่วมกัน $7$ เป็นปัจจัย การคำนวณ GCD ของ $c = M^3$ และ $N$ จึงเกิดการรั่วไหล $7$ เป็นปัจจัยของ $N$ทำลาย RSA

Chen avatar
kr flag
ตกลงฉันไม่ได้คิดเรื่องนี้ในกรณีดังกล่าว เป็นช่องโหว่ด้านความปลอดภัยที่รุนแรง เนื่องจากการใช้ GCD ของ ciphertext(C) และการรั่วไหลของ N p หรือ q?
Chen avatar
kr flag
การใช้ OAEP กับ C ที่ไม่ใช่ coprime กับ N จะยุติปัญหาหรือไม่
fgrieu avatar
ng flag
@Chen: ฉันไม่เข้าใจสิ่งที่คุณหมายถึงโดย "ใช้ OAEP บน C"; แต่การใช้ OAEP เพื่อสร้างอินพุต $M$ สำหรับการเข้ารหัส RSA แบบดิบ $M\mapsto C=M^e\bmod N$ สำหรับการรักษาความปลอดภัย $N$ เป็นอย่างอื่นนั้นแน่นอนว่าจะ "แก้ไขปัญหา" หากมี ตอนนี้เราสามารถเข้ารหัสผลคูณของ $p$ หรือ $q$ ได้อย่างปลอดภัย อีกครั้ง แม้จะไม่ได้ใช้ OAEP ก็ไม่มีปัญหาในทางปฏิบัติ เพราะการเลือก $M$ หรือ $C$ ใน $[1,n)$ กับ $\gcd(C,N)\ne1$ เป็นไปไม่ได้สำหรับคนที่ไม่รู้ ( ไม่สามารถหาได้) การแยกตัวประกอบของ $N$
Chen avatar
kr flag
ขออภัย ฉันตั้งใจจะใช้ OAEP กับ M คุณหมายความว่าการเลือก M ที่ให้ $gcd(C,N)â 1$ โดยตั้งใจนั้นเป็นไปไม่ได้หากไม่รู้ p และ q
Chen avatar
kr flag
และทำไมจะเป็นไปไม่ได้? จะเป็นไปได้ไหมที่มีโอกาสสำเร็จ 1/p + 1/q
meshcollider avatar
gb flag
@Chen ก็คงไม่ต่างอะไรจากผู้โจมตีเพียงแค่คาดเดาปัจจัยสุ่มของ $N$ :)
poncho avatar
my flag
@Chen: สำหรับขนาดจริง $p, q$ นั่นคือ $2^{-1024}$ หรือเล็กกว่า $1/p + 1/q$ นั้น "เป็นไปไม่ได้"

โพสต์คำตอบ

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