-
Следующий вопрос, который мы собираемся рассмотреть,
-
является ли 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, мы получаем алгоритм разложения.