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

0:00:01.703,0:00:03.638
является ли RSA по настоящему односторонней функцией.

0:00:03.638,0:00:05.788
Или другими словами: на сколько сложно

0:00:05.788,0:00:08.104
обратить RSA без знания "черного хода"?

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

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

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

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

0:00:23.293,0:00:26.131
насколько сложно получить x в степени e по модулю N.

0:00:26.131,0:00:28.933
В итоге на самом деле мы задаем вопрос

0:00:28.933,0:00:33.113
насколько сложно вычислить приближенные корни по составному модулю.

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

0:00:38.544,0:00:39.968
А если окажется простой,

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

0:00:44.564,0:00:46.832
Таким образом лучший алгоритм для решения этой проблемы

0:00:46.832,0:00:49.563
заключается в вычислении факториала модуля N.

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

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

0:00:55.892,0:00:58.483
легко вычислить приближенный корень остатка от деления q.

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

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

0:01:04.699,0:01:07.667
восстановив тем самым приближенный корень остатка от деления на N.

0:01:07.667,0:01:09.946
Теперь мы можем раскладывать модуль,

0:01:09.946,0:01:12.848
а вычисление приближенных корней остатка от деления N становится простым.

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

0:01:14.636,0:01:16.761
это очень и очень непростая задача.

0:01:16.761,0:01:19.865
Вопрос заключается в том, правда ли,

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

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

0:01:25.707,0:01:27.369
лучший алгоритм вычисления приближенных корней

0:01:27.369,0:01:30.002
остатка от деления N требует факторизации N.

0:01:30.002,0:01:31.626
Но кто знает, может есть короткий путь,

0:01:31.626,0:01:33.771
который позволит нам вычислить приближенный корень остатка от деления N

0:01:33.771,0:01:36.704
без факторизации остатков? Чтобы показать,

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

0:01:38.808,0:01:40.314
То есть, мы должны показать, что,

0:01:40.314,0:01:42.001
если я дам вам эффективный алгоритм

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

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

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

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