ความปลอดภัย RSA เมื่อใช้ข้อความสั้น

เราทราบดีว่าข้อความสั้นที่เข้ารหัสด้วย RSA สามารถถูกบังคับได้อย่างง่ายดาย

ข้อความสั้นที่เข้ารหัสด้วย RSA แบบเรียนสามารถถูกบังคับได้อย่างง่ายดาย ปัญหาคือ ไม่ ว่าข้อความนั้นสั้น ข้อความที่ยาวกว่ามากที่เลือกในชุดเล็กๆ (เช่น ตัวตนของบุคคลในรายชื่อชั้นเรียนสาธารณะ) ก็อาจถูกบังคับโดยเดรัจฉานด้วยเทคนิคเดียวกัน ปัญหาคือ ข้อความเอนโทรปีต่ำ รวมกับการใช้การเข้ารหัส RSA แบบเรียน (โดยไม่มีการเติมแบบสุ่ม)

Bob เข้ารหัสข้อความ (..) ด้วยรหัสส่วนตัวของเขา

"เข้ารหัส" นั้นเป็นคำศัพท์ที่ไม่ถูกต้องสำหรับการใช้การแปลง $m\mapsto f(m)=m^d\bmod n$ ที่ไหน $(น,ง)$ เป็นคีย์ส่วนตัว RSA ของ Bob นั่นไม่ได้ เข้ารหัสเนื่องจากคำดังกล่าวหมายถึงการแปลงข้อความเพื่อทำให้ศัตรูไม่สามารถเข้าใจได้ และที่นี่ทุกคนสามารถยกเลิกการเปลี่ยนแปลงโดยใช้สาธารณะ $(น,อี)$. ต้องเปลี่ยนคำว่า "เข้ารหัส" เป็น "แปลง" หรือ "สัญญาณ" ผลลัพธ์ $ฉ(ม)$ ของการดำเนินการนั้นเป็นตำรา RSA ลายเซ็นของข้อความ $m$ โดยคีย์ส่วนตัวของ Bob

ผู้โจมตีสามารถปลอมข้อความใหม่หนึ่งหรือสองตัวอักษรเพื่อให้ดูเหมือนว่ามาจาก Bob ได้หรือไม่

ใช่. เครื่องมือพื้นฐานที่ใช้คือคุณสมบัติการคูณของฟังก์ชัน $f$: สำหรับทุกอย่าง $m_1,m_2$ มันถือ $f(m_1\cdot m_2\bmod n)\ =\ f(m_1)\cdot f(m_2)\bmod n$. ดังนั้นศัตรูที่รู้ตำรา RSA ลายเซ็นของข้อความ $m_1$ และ $m_2$ สามารถค้นหาลายเซ็นตำรา RSA ของข้อความ $m_1\cdot m_2\bmod n$, หรือ ${m_1}^i\cdot{m_2}^j\bmod n$ สำหรับจำนวนเต็มคู่ใดๆ $i,j$.

สำหรับข้อความที่ถูกจำกัดให้มีความหมาย มีความเป็นไปได้ที่จะมี $m_1\cdot m_2=m_3\cdot m_4$ ซึ่งช่วยให้สามารถคำนวณลายเซ็น RSA ของตำราเรียนได้ $m_4$ จากที่ $m_1$, $m_2$ และ $m_3$, เช่น $f(m_4)\ =\ f(m_1)\cdot f(m_2)\cdot f(m_3)^{-1}\bmod n$.