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

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

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

m = c^d

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

x= r^emod n

y= xcmod n

t= r^-1 mod n

Если x= r^emod n, то r= x^dmod n.

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

u= y^d mod n

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

tumod n= r^{-1 yd}mod = r^-1x^dc^d mod n= c^d mod n= m

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

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

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

Сначала Ìýëëîðè выбирает произвольное значение xи вычисляет y= x^emod n. e он может получить без труда - это открытый ключ Трента, который должен быть опубликован, чтобы можно было проверять подписи Трента. Теперь Ìýëëîðè вычисляет m= ym'mod n и посылает m Тренту на подпись. Трент возвращает m^dmod n. Now Ìýëëîðè вычисляет (m^dmod n)x^-1 mod n, которое равно n'^dmod nи является подписью m'.

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

(xm)^d mod n= x ^dm^dmod n

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

m₃ = m₁m₂(mod n)

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

m₃^d = (m_l^d mod n) (m₂^d mod n)

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