Взломайте RSA без заполнения, используя атаку радужной таблицы

Да, атака в вопросе будет работать для низкого модуля примера.Термин «словарь» более уместен, чем «радужная таблица» (используется в контексте создания компактной таблицы предварительно вычисленных хэшей).

Однако настоящие атаки не могут работать таким образом. В RSA, как это практикуется, невозможно построить достаточно большой словарь, так как это займет слишком много времени (пропорционально модулю $n$, который в настоящее время обычно составляет не менее 2048 бит). Однако, если Алиса зашифровала сообщение, которое, как известно, принадлежит небольшому набору (например, имена в списках классов) непосредственно с помощью учебника RSA $m\mapsto c:=m^e\bmod n$, то можно расшифровать $с$ путем шифрования каждого возможного сообщения и тестирования, которое соответствует $с$. Последовательный поиск $м$ в списке классов подойдет: словарь соответствующих $с$ полезно только в том случае, если сообщений несколько (и RSA практически не используется, разбивая сообщения на небольшие куски, как в вопросе).

Случайное заполнение шифрования решает эту проблему, обратимо перевернуть сообщение $м$ в достаточно случайный представитель сообщения $\широкая м\in[0,n)$. Тогда учебник RSA можно смело применять к $\широкая м$, согласно предположению RSA: для правильного открытого ключа $(п,е)$ и случайный $х\в[0,n)$, трудно найти $х$ от $х^е\bмод п$.

как дешифратор (Боб) может «удалить» эти случайные биты, если он их не знает?

Общая картина такова, что между Алисой и Бобом существует соглашение о том, какие биты $\широкая м$ являются отступами (некоторые из которых случайны), добавленными Алисой, которые должны быть удалены Бобом. Это упрощенное описание довольно близко к устаревшему методу заполнения в RSAES-PKCS1-v1_5. Современный РГАЭС-ОАЭП имеет дополнительные шаги, поэтому все, кроме (максимум) 8 бит $\широкая м$ кажутся случайными, даже когда $м$ не является (что получается с помощью обратимого симметричного криптографического преобразования после применения случайного заполнения, рассеивающего случайность), но идея остается.