Вскрытие с выбранным шифротекстом против RSA

Некоторые вскрытия работают против реализаций RSA. Они вскрывают не сам базовый алгоритм, а над­строенный над ним протокол. Важно понимать, что само по себе использование RSA не обеспечивает безопас­ности. Дело в реализации.

Сценарий 1: Еве, подслушавшей линии связи Алисы, удалось перехватить сообщение с, шифрованное с по­мощью RSA открытым ключом Алисы. Ева хочет прочитать сообщение. На языке математики, ей нужно от, для которого

Для раскрытия от она сначала выбирает первое случайное число г, меньшее я. Она достает открытый ключ Алисы е. Затем она вычисляет

х = r^e mod я

у = хс mod я

t = r^lmod n

EcJinx = r^e mod n,Tor = x^d mod n.

Теперь просит Алису подписать у ее закрытым ключом, таким образом расшифровав у. (Алиса должна под­писать сообщение, а не его хэш сумму.) Не забывайте, Алиса никогда раньше не видела у. Алиса посылает Еве

u = y^d mod n

Теперь Ева вычисляет

tu mod я = г¹ / mod = fVc^d mod я = с "mod я = от

И Ева получает от.

Сценарий 2: Трент - это компьютер-нотариус. Если Алиса хочет заверить документ, она посылает его Тренту. Трент подписывает его цифровой подписью RSA и отправляет обратно. (Однонаправленные хэш-функции не используются, Трент шифрует все сообщение своим закрытым ключом.)

Мэллори хочет, чтобы Трент подписал такое сообщение, которое в обычном случае он он никогда не подп и-шет. Может быть это фальшивая временная метка, может быть автором этого сообщения является другое лицо. Какой бы ни была причина, Трент никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение от'.

Сначала Мэллори выбирает произвольное значение х и вычисляет у = х^е mod n. e он может получить без труда - это открытый ключ Трента, который должен быть опубликован, чтобы можно было проверять подписи Трента. Теперь Мэллори вычисляет от = ут' mod n и посылает от Тренту на подпись. Трент возвращает m^d mod п. Now Мэллори вычисляет (m^d mod n)x^l mod n, которое равно я" mod я и является подписью от'.

На самом деле Мэллори может использовать множество способов решить подобную задачу [423, 458, 486]. Слабым местом, которое используют такие вскрытия, является сохранение мультипликативной структуры входа при возведении в степень. То есть:

{xm)^d mod n = x ^dm^d mod n

Сценарий 3: Ева хочет, чтобы Алиса подписала от₃. Она создает два сообщения, т_х и от₂, такие что

от₃ = т_хт_г (mod я)

Если Ева сможет заставить Алису подписать т_х и от₂, она может вычислить подпись для от₃:

m₃^d = (m_i^d mod n) (m₂^d mod п)

Мораль: Никогда не пользуйтесь алгоритмом RSA для подписи случайных документов, подсунутых вам по­сторонними. Всегда сначала воспользуйтесь однонаправленной хэш-фунцией. Формат блоков ISO 9796 предот­вращает это вскрытие.