Циклические атаки
Пусть с = me mod n - зашифрованное сообщение, к - положительное целое, при этом сс = с (mod n). Тогда зашифрованием является подстановка на множестве {0,1 ... п-1}, в которой присутствует к, что может привести к ситуации, когда се" = m (mod n). Злоумышленник вычисляет значения се mod n, ce mod n и т.д. до тех пор, пока не будет получено значение с. Если се mod n = с, тогда се" = m (mod n). Основой циклической атаки является нахождение такого небольшого положительного целого и, при котором выполняется условие f(u) = НОД (се" - с, п) > 1. Если cc'u= c(mod p) hc'Vc (mod q), то f(u) = р. Аналогично, если ceU ^ с (mod p) и с°и= с (mod q), то f(u) = q. В любом из этих случаев злоумышленник получает разложение п на множители.
При этом существует вероятность возникновения одной из следующих ситуаций:
• если выбрать общий модуль п для каждого участника при различных парах (ei5 d;), появляется потенциальная возможность разложить на множители модуль п (правда, для этого необходимо знать каждую пару (eb dj)). Более того, если одно и то же сообщение отправлено несколькими участниками, злоумышленник, перехватив эти сообщения, может восстановить открытый текст на основе знания общедоступных параметров системы. Учитывая сказанное, при выборе параметров в асимметричных алгоритмах шифрования необходимо, чтобы п создавалось для каждого участника системы отдельно. Кроме того, развитие эффективных алгоритмов факторизации больших целых чисел предъявляет жесткие требования к размеру п; на сегодняшний день минимально рекомендуемая длина п должна быть равна 768 битам;
• при выборе экспонент end тоже могут возникать ситуации, существенно ослабляющие стойкость RSA. При выборе экспоненты е обычно ориентируются на обеспечение приемлемой скорости операций зашифрования/расшифрования, что приводит к выбору малых значений е. Например, рассмотрим случай, когда е = 3 для участников А, В и С (предполагается также, что модули п у каких-либо двух участников взаимно просты). В этом случае злоумышленник, перехватив одинаковые сообщения, переданные всем участникам (например, многоадресная доставка), с5= me mod n, где i = А, В, С, может вычислить число х = m3mod (nAnBnc). Поскольку m3< nAnBnc, это возможно только в случае, если х = т3. Тогда злоумышленник, вычислив кубический корень, может найти т. С точки зрения достижения приемлемых скоростных параметров и обеспечения должного уровня безопасности имеет смысл выбрать число е = 216+ 1, являющееся числом Ферма и имеющее в битовом представлении всего лишь две единицы. Выбор небольшого числа d также опасно тем, что если НОД (р - 1, q - 1) и d приблизительно равны п/4, то существуют алгоритмы факторизации п на основе знания только открытого ключа. Кроме того, в случае небольшого значения d оно может быть найдено простым перебором всех возможных значений.
Для RSA характерно наличие так называемых нешифруемых блоков открытого сообщения, то есть таких т, для которых выполняется равенство mL> = m (mod n). Например, m = О, т=1ит = п-1 всегда являются иешифруемыми блоками сообщения. Необходимым и достаточным условием нешифруемости сообщения является т0"1 = 1 (mod n).
В общем случае под единицей в равенстве следует понимать отдельный элемент группы, к которой принадлежит т. Как видно из приведенного условия нешифруемости, таких блоков сообщения совсем немало. Точное количество нешифруемых блоков сообщения равно (1 + НОД(е, р - 1)) х X (1 + НОД (е - 1, q - 1)). Данная особенность алгоритма RSA налагает определенные требования при выборе значения е. Так, например, если е равно 1 + k[(p(q), ф(р)], все элементы кольца сообщений окажутся иешифруемыми.
Необходимо отметить, что RSA критичен также к адаптивной атаке с выбором зашифрованных сообщений. Этот метод основан на гомоморфных свойствах RSA. Другими словами, для любых открытых сообщений mt и т2 и для соответствующих зашифрованных сообщений ct и с2 выполняется следующее равенство: (m1m2)e= mfmf" qc2 (mod n).