WEBVTT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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