В криптографии задача 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.