Войти
В криптографии, Проблема RSA обобщает задачу выполнения операции с закрытым ключом RSA с учетом только открытого ключа. Алгоритм RSA передает сообщение в показатель степени, по модулю a составное число N, коэффициенты которого неизвестны. Таким образом, задачу можно аккуратно описать как нахождение корней e из произвольного числа по модулю N. Для больших размеров ключа RSA (более 1024 битов) эффективный метод решения этой проблемы неизвестен; если когда-либо будет разработан эффективный метод, он поставит под угрозу текущую или возможную безопасность криптосистем на основе RSA - как для шифрования с открытым ключом, так и цифровых подписей.
В частности, проблема RSA заключается в для эффективного вычисления P с учетом открытого ключа RSA (N, e) и зашифрованного текста C ≡ P (mod N). Структура открытого ключа RSA требует, чтобы N было большим полупростым числом (т. Е. Произведением двух больших простых чисел ), что 2 < e < N, that e be взаимно простое число с φ (N), и что 0 ≤ C < N. C is chosen randomly within that range; to specify the problem with complete precision, one must also specify how N and e are generated, which will depend on the precise means of RSA random keypair generation in use.
Наиболее эффективный метод, известный для решения проблемы RSA, - это сначала разложение модуля N на множители, задача считается непрактичной, если N достаточно велико (см. целочисленная факторизация ). Подпрограмма установки ключа RSA уже превращает публичную экспоненту e с этой простой факторизацией в частную экспоненту d, и поэтому точно такой же алгоритм позволяет любому, кто множит N, получить закрытый ключ. Затем любой C можно расшифровать с помощью закрытого ключа.
Так же, как нет доказательств того, что целочисленная факторизация является вычислительно сложной, нет также доказательств того, что проблема RSA аналогична сложной. При использовании вышеупомянутого метода проблема RSA, по крайней мере, так же проста, как факторинг, но вполне может быть проще. В самом деле, есть веские доказательства, указывающие на этот вывод: метод взлома метода RSA не может быть обязательно преобразован в метод факторизации больших полупростых чисел. Это, пожалуй, легче всего увидеть по явному излишеству подхода факторинга: проблема RSA просит нас расшифровать один произвольный зашифрованный текст, тогда как метод факторизации раскрывает закрытый ключ: таким образом расшифровывая все произвольные зашифрованные тексты, и он также позволяет выполнять произвольный RSA шифрование с закрытым ключом. В том же духе нахождение показателя расшифровки d действительно вычислительно эквивалентно факторизации N, даже несмотря на то, что проблема RSA не требует d.
В дополнение к проблеме RSA, RSA также имеет особую математическую структуру, которая потенциально могут быть использованы без непосредственного решения проблемы RSA. Чтобы полностью решить проблему RSA, криптосистема на основе RSA должна также использовать схему заполнения , например OAEP, для защиты от таких структурных проблем в RSA.
