Значение: «Если вычислять большие целые числа сложно, то сломать RSA сложно», это не доказано »

Я читал CLRS и сказал:

Если факторизация больших целых чисел проста, то взломать криптосистему RSA легко.

Что имеет смысл для меня, потому что со знанием и легко создать секретный ключ, который известен из открытого ключа. Хотя, это объясняет обратное утверждение, которое я не совсем понимаю:$p$$q$

Обратное утверждение, что если вычислять большие целые числа сложно, то сломать RSA сложно, это не доказано.

Что означает приведенное выше утверждение? Если предположить, что факторинг сложен (каким-то формальным образом), почему это не означает, что взломать криптосистему RSA сложно?

Теперь учтите, что если мы предположили, что факторинг сложен ... и что мы обнаружили, что это означает, что криптосистему RSA трудно сломать. Что бы это формально означало?

Самый простой способ думать об этом - думать о противоположном.

Заявление:

если сложно вычислить большие целые числа, то сломать RSA сложно

эквивалентно следующему:

если разбить RSA легко, то легко вычислить большие целые числа

Это утверждение не было доказано.

Они говорят, что у нас есть алгоритм, который решает факторинг за полиномиальное время. Затем мы можем использовать его для построения алгоритма, который решает RSA за полиномиальное время.

Но может быть какой-то другой способ взломать RSA, который не включает факторизацию целых чисел. Вполне возможно, что мы обнаружим, что можем взломать RSA таким образом, чтобы не допустить факторизации целых чисел за полиномиальное время.

Короче говоря, мы знаем, что RSA по крайней мере так же просто, как факторинг. Возможны два исхода: RSA и факторинг имеют одинаковую сложность, или RSA является более простой проблемой, чем факторинг. Мы не знаем, в чем дело.

Существование сложного пути не означает, что простого пути не существует.

Может быть несколько способов сломать RSA, и нам нужно найти только один из них.

Одним из таких способов является факторизация большого целого числа, поэтому, если это легко, мы можем сделать это таким образом, и RSA не работает. Это также единственный способ, которым мы знаем. Если это невозможно сделать, мы все равно можем найти другой, менее требовательный в вычислительном отношении способ выполнения нашей задачи без необходимости явно вычислять p и q из n .

Чтобы доказать, что RSA сломан, мы должны доказать, что один из способов сделать это легко.

Чтобы доказать безопасность RSA, мы должны доказать, что все способы сделать это сложны.

Наконец, ваше утверждение недоказано, поскольку не доказано, что не существует другого, более простого метода, который извлекает информацию из зашифрованного текста.

Еще один способ взглянуть на это заключается в том, что нарушение RSA требует только особого случая факторинга, который может быть или не быть простым, независимо от общего вопроса факторинга.

$3$

Это означает, что проблема RSA кажется (в настоящее время) более конкретной, чем факторинг.

$pq$$e,$$v,$$m$$v \equiv m^e \mod pq$

$pq,$$p$$q$

$d$$m \equiv v^d$

$m$

Фактически, в 1998 году Бонех и Венкатесан опубликовали доказательство того, что некий простой класс алгоритмов (плюс, время, экспоненты, вещи типа XOR / NAND) не могут быть использованы для превращения решения задачи RSA в алгоритм факторинга. У аргумента была простая изобретательность: манипулируя этими арифметическими операциями математически, мы можем выяснить, что «алгоритм редукции» (для точности: это алгоритм, который использует «оракул» RSA для полупростого, чтобы факторизовать полупростое) превращается это сам по себе алгоритм факторинга, так что мы можем изменить его на вариант, который не вызывает его оракула. Итак, у нас есть трихотомия: либо (а) такого алгоритма редукции не существует, либо (б) алгоритм редукции не имеет хорошей арифметической интерпретации, либо (в) факторинг является полиномиальным временем, как и алгоритм редукции.

$\log_e C$$\mathbb{Z}_{m}$$e$$m$$C$

Эти две математические задачи связаны между собой, но (если я правильно помню) считается, что решение одной не подразумевает решение другой. Я не знаю, являются ли они единственными двумя способами математически сломать RSA.