В криптографии проблема RSA суммирует задачу выполнения операции с закрытым ключом RSA , имея только открытый ключ . Алгоритм RSA возводит сообщение в степень по модулю составного числа N , коэффициенты которого неизвестны. Таким образом, задачу можно аккуратно описать как поиск корней e- й степени произвольного числа по модулю N. Для больших размеров ключей RSA (свыше 1024 бит) эффективный метод решения этой проблемы неизвестен; если когда-либо будет разработан эффективный метод, это поставит под угрозу текущую или возможную безопасность криптосистем на основе RSA — как для шифрования с открытым ключом, так и для цифровых подписей .
Более конкретно, проблема RSA состоит в том, чтобы эффективно вычислить P с учетом открытого ключа RSA ( N , e ) и зашифрованного текста C ≡ P e ( mod N ). Структура открытого ключа RSA требует, чтобы N было большим полупростым числом (т. е. произведением двух больших простых чисел ), чтобы 2 < e < N , чтобы e было взаимно простым с φ ( N ) и чтобы 0 ≤ C < N . C выбирается случайным образом в этом диапазоне; Чтобы определить проблему с полной точностью, необходимо также указать, как генерируются N и e , что будет зависеть от точных используемых средств генерации случайной пары ключей RSA.
Самый эффективный известный метод решения проблемы RSA — это сначала факторизовать модуль N, задача, которая считается непрактичной, если N достаточно велико (см. Целочисленную факторизацию ). Процедура установки ключа RSA уже превращает открытый показатель e с помощью этой простой факторизации в закрытый показатель d , и поэтому точно такой же алгоритм позволяет любому, кто факторизует N , получить закрытый ключ . Любой C затем можно расшифровать с помощью закрытого ключа.
Точно так же, как нет доказательств того, что факторизация целых чисел сложна в вычислительном отношении, нет также доказательств того, что проблема RSA столь же сложна. С помощью описанного выше метода задача RSA, по крайней мере, так же проста, как и факторизация, но вполне может быть и проще. Действительно, есть убедительные доказательства, указывающие на этот вывод: метод взлома метода RSA не может быть обязательно преобразован в метод факторизации больших полупростых чисел. [1] Вероятно, это проще всего увидеть по явному излишеству факторингового подхода: задача RSA требует от нас расшифровать один произвольный зашифрованный текст, тогда как метод факторинга раскрывает закрытый ключ: таким образом, расшифровываются все произвольные зашифрованные тексты, а также позволяет выполнять произвольное шифрование с закрытым ключом RSA. В том же духе нахождение показателя дешифрования d действительно вычислительно эквивалентно факторингу N , даже несмотря на то, что проблема RSA не требует d . [2]
В дополнение к проблеме RSA, RSA также имеет особую математическую структуру, которую потенциально можно использовать без непосредственного решения проблемы RSA. Чтобы в полной мере решить проблему RSA, криптосистема на основе RSA должна также использовать схему заполнения, такую как OAEP , для защиты от таких структурных проблем в RSA.