проблема с RSA
В криптографии проблема RSA суммирует задачу выполнения RSA, операции с закрытым ключом имея только открытый ключ . Алгоритм RSA возводит сообщение в степень по модулю составного числа N , которого коэффициенты неизвестны. Таким образом, задачу можно аккуратно описать как нахождение e й корни произвольного числа по модулю N. Для больших размеров ключей RSA (свыше 1024 бит) эффективный метод решения этой проблемы неизвестен; если когда-либо будет разработан эффективный метод, это поставит под угрозу текущую или возможную безопасность криптосистем на основе RSA — как для шифрования с открытым ключом, так и для цифровых подписей .
Более конкретно, проблема RSA состоит в том, чтобы эффективно вычислить P с учетом открытого ключа RSA ( N , e ) и зашифрованного текста C ≡ P. и ( мод Н ). Структура открытого ключа 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.
См. также [ править ]
- Сильное предположение RSA
- Факторинговый вызов RSA
- Криптосистема Рабина , эквивалентность которой факторингу известна.
Ссылки [ править ]
- ^ Боне, Дэн; Венкатесан, Рамаратнам (1998). «Нарушение RSA может не быть эквивалентом факторинга». Достижения криптологии – EUROCRYPT'98 . Конспекты лекций по информатике. Том. 1403. Спрингер. стр. 59–71. дои : 10.1007/BFb0054117 . ISBN 978-3-540-64518-4 .
- ^ Алгоритм для этого приведен, например, в Менезес; ван Оршот; Ванстон (2001). «Шифрование с открытым ключом» (PDF) . Справочник по прикладной криптографии .
Дальнейшее чтение [ править ]
- Нарушение RSA может быть таким же трудным, как факторизация , Д. Браун, 2005. В этом нерецензируемом препринте утверждается, что решение проблемы RSA с использованием программы прямых линий так же сложно, как и факторизация, при условии, что e имеет небольшой коэффициент.
- Нарушение RSA в общих чертах эквивалентно факторингу , Д. Аггарвал и У. Маурер, 2008. Эта статья Eurocrypt 2009 (ссылка на препринтную версию) доказывает, что решение проблемы RSA с использованием универсального кольцевого алгоритма так же сложно, как и факторизация.
- When e-th Roots Become Easier Than Factoring , Антуан Жу , Дэвид Наккаш и Эммануэль Томе, 2007. Эта статья Asiacrypt 2007 (ссылка на препринтную версию) доказывает, что решение проблемы RSA с использованием оракула для некоторых других особых случаев Задача RSA проще, чем факторинг.
| |||||||||||||||||||||
