Криптостойкость RSA. 
Обзор современных средств криптографии

Предполагается, что криптостойкостью RSA зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно разложить n на множители, чтобы восстановить m по c и e. Не исключено, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Так же можно атаковать RSA, угадав значение (p-1)(q-1). Однако этот метод не проще разложения n на множители. Доказано, что при использовании RSA раскрытие даже нескольких битов информации по шифротексту не легче, чем дешифрования всего сообщения.

Самой очевидной атакой на RSA является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрования d, противник должен разложить n на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже менее эффективна, чем попытка разложения n на множители. В 1993 г. Был предложен метод кирптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет, если p или q окажется составным? Тогда у модуля n будет три или более делителей.

Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь, открывает возможности для атаки путем факторизации модуля.

Другая опасность заключается в генерации псевдопростых чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума.