Phá vỡ RSA mà không cần đệm bằng tấn công bảng cầu vồng

Có, cuộc tấn công trong câu hỏi sẽ hoạt động đối với mô đun thấp của ví dụ.Thuật ngữ "từ điển" phù hợp hơn "bảng cầu vồng" (được sử dụng trong ngữ cảnh tạo một bảng băm nhỏ gọn được tính toán trước).

Tuy nhiên, các cuộc tấn công thực tế không thể hoạt động theo cách này. Trong RSA như thực tế, không thể xây dựng một từ điển đủ lớn, vì sẽ mất quá nhiều thời gian để xây dựng (tỷ lệ thuận với mô đun $n$, thường là ít nhất 2048-bit ngày nay). Tuy nhiên, nếu Alice mã hóa một tin nhắn được biết là thuộc về một nhóm nhỏ (chẳng hạn như tên trong danh sách lớp) trực tiếp bằng RSA trong sách giáo khoa $m\mapsto c:=m^e\bmod n$, sau đó có thể giải mã $c$ bằng cách mã hóa từng tin nhắn có thể và kiểm tra tin nhắn phù hợp $c$. Một tìm kiếm tuần tự của $m$ trong điểm danh lớp sẽ làm: một từ điển tương ứng $c$ chỉ hữu ích nếu có một số tin nhắn (và RSA thực tế không được sử dụng bằng cách chia tin nhắn thành các phần nhỏ, như trong câu hỏi).

Đệm mã hóa ngẫu nhiên giải quyết vấn đề này, bằng cách đảo ngược chuyển một tin nhắn $m$ thành một đại diện thông điệp đủ ngẫu nhiên $\widetilde m\in[0,n)$. Sau đó, RSA sách giáo khoa có thể được áp dụng một cách an toàn cho $\widetilde m$, theo giả định RSA: đối với khóa công khai thích hợp $(n,e)$ và ngẫu nhiên $x\in[0,n)$, thật khó để tìm thấy $x$ từ $x^e\bmod n$.

làm cách nào bộ giải mã (Bob) có thể 'xóa' các bit ngẫu nhiên đó nếu anh ta không biết chúng?

Bức tranh toàn cảnh là có một quy ước giữa Alice và Bob về những bit nào của $\widetilde m$ là phần đệm (một số ngẫu nhiên) do Alice thêm vào, Bob sẽ xóa phần đệm đó. Mô tả đơn giản hóa đó khá gần với kỹ thuật đệm không dùng nữa trong RSAES-PKCS1-v1_5. Hiện đại RSAES-OAEP có các bước bổ sung nên tất cả ngoại trừ (tối đa) 8 bit của $\widetilde m$ xuất hiện ngẫu nhiên ngay cả khi $m$ không (thu được bằng phép biến đổi mật mã đối xứng có thể đảo ngược sau khi áp dụng phần đệm ngẫu nhiên, giúp khuếch tán tính ngẫu nhiên), nhưng ý tưởng vẫn còn.