ทำลาย RSA โดยไม่ต้องเติมโดยใช้การโจมตีตารางสายรุ้ง

ใช่ การโจมตีในคำถามจะใช้ได้กับโมดูโลต่ำของตัวอย่างคำว่า "พจนานุกรม" เหมาะสมกว่า "ตารางสีรุ้ง" (ใช้ในบริบทของการสร้างตารางขนาดกะทัดรัดของแฮชที่คำนวณล่วงหน้า)

การโจมตีจริงไม่สามารถทำงานในลักษณะนี้ได้ ในทางปฏิบัติ RSA เป็นไปไม่ได้ที่จะสร้างพจนานุกรมขนาดใหญ่พอ เนื่องจากจะใช้เวลามากเกินไปในการสร้าง (สัดส่วนกับโมดูลัส $n$ซึ่งโดยทั่วไปแล้วในปัจจุบันจะมีขนาดอย่างน้อย 2048 บิต) อย่างไรก็ตาม หากอลิซเข้ารหัสข้อความที่ทราบว่าเป็นของชุดเล็กๆ (เช่น ชื่อในรายชื่อชั้นเรียน) โดยตรงกับ RSA หนังสือเรียน $m\mapsto c:=m^e\bmod n$จากนั้นจะสามารถถอดรหัสได้ $ค$ โดยการเข้ารหัสแต่ละข้อความที่เป็นไปได้และทดสอบว่าข้อความใดตรงกัน $ค$. การค้นหาตามลำดับของ $m$ ในม้วนชั้นเรียนจะทำ: พจนานุกรมที่เกี่ยวข้อง $ค$ จะมีประโยชน์ก็ต่อเมื่อมีหลายข้อความ (และ RSA ไม่ได้ใช้จริงโดยการแบ่งข้อความออกเป็นชิ้นเล็กๆ ดังเช่นในคำถาม)

การขยายการเข้ารหัสแบบสุ่มช่วยแก้ปัญหานี้ได้โดย ย้อนกลับ เปลี่ยนข้อความ $m$ เป็นตัวแทนข้อความแบบสุ่มที่เพียงพอ $\widetilde m\in[0,n)$. จากนั้นตำราเรียน RSA สามารถนำไปใช้ได้อย่างปลอดภัย $\ไวด์ทิลด์ m$ตามสมมติฐานของ RSA: สำหรับคีย์สาธารณะที่เหมาะสม $(น,อี)$ และ สุ่ม $x\in[0,n)$,มันยากที่จะหา $x$ จาก $x^e\bmod n$.

ตัวถอดรหัส (Bob) จะ 'ลบ' บิตสุ่มเหล่านั้นได้อย่างไรหากเขาไม่รู้จัก

ภาพใหญ่คือมีการประชุมระหว่างอลิซกับบ็อบเกี่ยวกับส่วนไหนของ $\ไวด์ทิลด์ m$ กำลังขยาย (บางส่วนสุ่ม) ที่อลิซเพิ่มเข้ามาซึ่งบ็อบควรลบออก คำอธิบายแบบง่ายนั้นค่อนข้างใกล้เคียงกับเทคนิคการเติมที่เลิกใช้แล้วใน RSAES-PKCS1-v1_5. ที่ทันสมัย RSAES-สศอ มีขั้นตอนเพิ่มเติมดังนั้นทั้งหมดยกเว้น (สูงสุด) 8 บิตของ $\ไวด์ทิลด์ m$ ปรากฏแบบสุ่มแม้ว่า $m$ ไม่ใช่ (ซึ่งได้มาจากการแปลงรหัสลับแบบสมมาตรที่ย้อนกลับได้หลังจากใช้การเติมแบบสุ่ม ซึ่งกระจายการสุ่ม) แต่แนวคิดยังคงอยู่