Is RSA a one-way function? (17 min)

Следующий вопрос, который мы собираемся рассмотреть,

является ли RSA по настоящему односторонней функцией.

Или другими словами: на сколько сложно

обратить RSA без знания "черного хода"?

Итак, если атакующий хочет обратить RSA функцию,

при этом в основном обладая открытым ключом,

назовем его(N,e). И сейчас, ему дано x в степени e

и его цель определить x. Вопрос заключается в том,

насколько сложно получить x в степени e по модулю N.

В итоге на самом деле мы задаем вопрос

насколько сложно вычислить приближенные корни по составному модулю.

Если эта задача окажется сверхсложной, то RSA действительно является односторонней функцией.

А если окажется простой,

во что нам не хотелось бы верить, тогда бы RSA давно бы был взломан

Таким образом лучший алгоритм для решения этой проблемы

заключается в вычислении факториала модуля N.

А затем, после вычисления факториала, как мы это делали

на прошлой неделе, легко вычислить приближенный корень остатка от деления p,

легко вычислить приближенный корень остатка от деления q.

И, после получения этих корней, совсем просто объединить их вместе,

используя, так называемую, Китайскую теорему об остатках,

восстановив тем самым приближенный корень остатка от деления на N.

Теперь мы можем раскладывать модуль,

а вычисление приближенных корней остатка от деления N становится простым.

Но факторизация остатков от деления, как мы знаем,

это очень и очень непростая задача.

Вопрос заключается в том, правда ли,

что в порядке вычисления приближенных корней остатка от деления N,

нам необходимо факторизовать остаток от деления N? Как мы знаем,

лучший алгоритм вычисления приближенных корней

остатка от деления N требует факторизации N.

Но кто знает, может есть короткий путь,

который позволит нам вычислить приближенный корень остатка от деления N

без факторизации остатков? Чтобы показать,

что это возможно, нам потребуется продемонстрировать сокращение.

То есть, мы должны показать, что,

если я дам вам эффективный алгоритм

вычисления приближенных корней остатка от деления N,

и что эффективный алгоритм может быть превращен в алгоритм разложения

Это и называется сокращением. А именно, учитывая алгоритм

приближенных корней остатка от деления N, мы получаем алгоритм разложения.