Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В криптографии , то проблема 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 не просит г . [2]

Помимо проблемы RSA, RSA также имеет особую математическую структуру, которая потенциально может быть использована без непосредственного решения проблемы RSA. Чтобы достичь полной силы проблемы RSA, криптосистема на основе RSA должна также использовать схему заполнения, такую ​​как OAEP , для защиты от таких структурных проблем в RSA.

См. Также [ править ]

Ссылки [ править ]

  1. ^ Боне, Дэн; Венкатесан, Рамаратнам (1998). «Нарушение RSA не может быть равнозначно факторингу». Достижения в криптологии - EUROCRYPT'98 . Конспект лекций по информатике. 1403 . Springer. С. 59–71. DOI : 10.1007 / BFb0054117 . ISBN 978-3-540-64518-4.
  2. ^ Алгоритм для этого, например, дан в Menezes; ван Оршот; Ванстон (2001). «Шифрование с открытым ключом» (PDF) . Справочник по прикладной криптографии .

Дальнейшее чтение [ править ]