Score:1

การแยกตัวประกอบ RSA รู้รูปแบบของ p และ q

ธง lk

ฉันสงสัยว่าการรู้รูปแบบของปัจจัยทั้งสอง (p และ q) ของ RSA modulus N นั้นมีประโยชน์อย่างมากสำหรับการแยกตัวประกอบหรือไม่

ตัวอย่างเช่น: p ในรูปแบบ 4k+3 ดังนั้น (p-3)%4 = 0 และ q ในรูปแบบ 4k+7 ดังนั้น (q-7)%4 = 0

poncho avatar
my flag
โปรดทราบว่ารูปแบบ '4k+3' และ '4k+7' นั้นเหมือนกันทุกประการ...
Score:4
ธง ng

ถ้า $k$ เหมือนกันทั้ง 2 รูปแบบ กล่าวคือ $n=(4k+3)(4k+7)$การแยกตัวประกอบเป็นเรื่องเล็กน้อย: $p=\lceil\sqrt n\,\rceil-2$, $q=p+4$.

สมมติว่าทั้งสอง $k$ เป็นอิสระจากนี้ไป: โปรดทราบว่าสำหรับจำนวนเฉพาะคี่ $p$ ตามขนาด ปริมาณที่กำหนด $p\bmod4$ เป็นเรื่องเกี่ยวกับการแบ่งเท่า ๆ กัน $\{1,3\}$. ดังนั้นแบบฟอร์มที่รู้จักจึงให้ข้อมูลเกี่ยวกับข้อมูลหนึ่งบิต $p$. เราได้รับข้อมูลเดียวกันเกี่ยวกับ $คิว$แต่การสังเกต $n\equiv1\pmod4$ อนุญาตให้อนุมานได้แล้ว $p\equiv3\pmod4$. ดังนั้นรูปแบบที่รู้จักจึงให้ข้อมูลเพียง 1 บิตต่อปัจจัยช่วยเหลือ $n$: สำหรับที่กำหนด $n$ มันสามารถทำงานได้อย่างดีที่สุดเพียงครึ่งเดียว นอกจากนี้เกี่ยวกับหนึ่ง $n$ จากสี่ในโมดูลัส RSA ปกติมีรูปแบบนี้ ดังนั้นหากปัญหาเหล่านี้ง่าย $n$, RSA จะไม่ปลอดภัย

โพสต์คำตอบ

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