Атака с выборкой зашифрованного текста

Потенциальная атака RSА базируется на мультипликативном свойстве RSA. Предположим, Алиса создает зашифрованный текст C = P^e mod n и передает C Бобу. Также предположим, что Боб расшифрует произвольный зашифрованный текст для Евы – С₁, отличный от C. Ева перехватывает C и использует следующие шаги, чтобы найти P:

а. Ева выбирает случайное целое число X в Z_n*.

б. Ева вычисляет .

в. Ева передает Y Бобу для дешифрования и получает Z = Y^d mod n ; это шаг атаки выборкой зашифрованного текста.

г. Ева может легко найти P, потому что

Z = Y^d mod n = (C x X^e)^d mod n = (C^d x X^ed) mod n = (C^d x X) mod n = (P x X) mod n

Z = (P x X) mod n -> P=Z x X^-1 mod n

Ева использует расширенный евклидов алгоритм для того, чтобы найти мультипликативную инверсию X, и в конечном счете значение P.

Атаки на показатель степени шифрования

Чтобы уменьшить время шифрования, можно попытаться использовать короткий ключ шифрования — малое значение числа e, например, значение для e, такое как e = 3 (второе простое число). Однако есть некоторые потенциальные атаки на показатель при его малом значении степени шифрования, которые мы здесь кратко обсуждаем. Эти атаки вообще не кончаются вскрытием системы, но они все-таки должны быть предотвращены. Для того чтобы сорвать эти виды атак, рекомендуется использовать e = 2¹⁶ + 1 = 65537 (или простое число, близкое к этому значению).

Атака теоремы Куперcмита (Coppersmith) может быть главной для атаки малого показателя степени на ключ шифрования. Основное положение этой теоремы: для полинома f(x) степени e по модулю n, чтобы найти корни, если один из корней является меньшим чем n^1/e, можно использовать алгоритм сложности, log n. Эта теорема может быть применена к RSA-криптосистеме C = f(P) = P^e mod n. Если e = 3 и известны хотя бы две трети битов в исходном тексте P, алгоритм может найти все биты в исходном тексте.

Атака широковещательной передачи может быть начата, если один объект передает одно и то же сообщение группе получателей с тем же самым ключом шифрования. Например, предположим следующий сценарий: Алиса хочет передать одно и то же сообщение трем получателям с тем же самым общедоступным ключом e = 3 и модулями n₁, n₂ и n₃.

C₁ = P³ mod n₁

C₂ = P³ mod n₂

C₃ = P³ mod n₃

Применяя китайскую теорему об остатках к этим трем уравнениям, Ева может найти уравнение формы C’ = P³ mod n₁n₂n₃. Это означает, что P³ < n₁n₂n₃ и что C’ = P³ решается с помощью обычной арифметики (не модульной). Ева может найти значение C’ = P^1/3.

Атака связанных между собой сообщений была обнаружена Франклином Рейтером (Franklin Reiter). Она может быть кратко описана следующим образом. Алиса зашифровала два исходных текста, P₁ и P₂, с помощью e = 3 и передает C₁ и C₂ Бобу. Если P₁ связан с P₂ линейной функцией, то Ева может восстановить P₁ и P₂ в выполнимое время вычисления.

Атака короткого списка, обнаруженная Куперсмитом, может быть кратко описана следующим образом. Алиса имеет сообщение М для передачи Бобу. Она записывает сообщение и зашифровывает его как сообщение r₁, а результат записывает как C₁ и передает C₁ (Бобу). Ева перехватывает C₁ и удаляет его. Боб сообщает Алисе, что он не получил сообщение, так что Алиса заполняет сообщение, снова зашифровывает как сообщение r₂ и передает это Бобу. Ева также перехватывает и это сообщение. Ева теперь имеет C₁ и C₂, и она знает, что оба зашифрованных текста принадлежат одному и тому же исходному тексту. Куперсмит доказал, что если r₁ и r₂ короткие, то Ева способна восстановить первоначальное сообщение М.