[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.15,0:00:01.70,Default,,0000,0000,0000,,Следующий вопрос, который мы собираемся рассмотреть,
Dialogue: 0,0:00:01.70,0:00:03.64,Default,,0000,0000,0000,,является ли RSA по настоящему односторонней функцией.
Dialogue: 0,0:00:03.64,0:00:05.79,Default,,0000,0000,0000,,Или другими словами: на сколько сложно
Dialogue: 0,0:00:05.79,0:00:08.10,Default,,0000,0000,0000,,обратить RSA без знания "черного хода"?
Dialogue: 0,0:00:09.01,0:00:11.100,Default,,0000,0000,0000,,Итак, если атакующий хочет обратить RSA функцию,
Dialogue: 0,0:00:11.100,0:00:15.00,Default,,0000,0000,0000,,при этом в основном обладая открытым ключом,
Dialogue: 0,0:00:15.00,0:00:19.05,Default,,0000,0000,0000,,назовем его(N,e). И сейчас, ему дано x в степени e
Dialogue: 0,0:00:19.05,0:00:23.29,Default,,0000,0000,0000,,и его цель определить x. Вопрос заключается в том,
Dialogue: 0,0:00:23.29,0:00:26.13,Default,,0000,0000,0000,,насколько сложно получить x в степени e по модулю N.
Dialogue: 0,0:00:26.13,0:00:28.93,Default,,0000,0000,0000,,В итоге на самом деле мы задаем вопрос
Dialogue: 0,0:00:28.93,0:00:33.11,Default,,0000,0000,0000,,насколько сложно вычислить приближенные корни по составному модулю.
Dialogue: 0,0:00:34.18,0:00:38.54,Default,,0000,0000,0000,,Если эта задача окажется сверхсложной, то RSA действительно является односторонней функцией.
Dialogue: 0,0:00:38.54,0:00:39.97,Default,,0000,0000,0000,,А если окажется простой,
Dialogue: 0,0:00:39.97,0:00:44.56,Default,,0000,0000,0000,,во что нам не хотелось бы верить, тогда бы RSA давно бы был взломан
Dialogue: 0,0:00:44.56,0:00:46.83,Default,,0000,0000,0000,,Таким образом лучший алгоритм для решения этой проблемы
Dialogue: 0,0:00:46.83,0:00:49.56,Default,,0000,0000,0000,,заключается в вычислении факториала модуля N.
Dialogue: 0,0:00:50.05,0:00:52.24,Default,,0000,0000,0000,,А затем, после вычисления факториала, как мы это делали
Dialogue: 0,0:00:52.24,0:00:55.89,Default,,0000,0000,0000,,на прошлой неделе, легко вычислить приближенный корень остатка от деления p,
Dialogue: 0,0:00:55.89,0:00:58.48,Default,,0000,0000,0000,,легко вычислить приближенный корень остатка от деления q.
Dialogue: 0,0:00:58.48,0:01:02.11,Default,,0000,0000,0000,,И, после получения этих корней, совсем просто объединить их вместе,
Dialogue: 0,0:01:02.11,0:01:04.70,Default,,0000,0000,0000,,используя, так называемую, Китайскую теорему об остатках,
Dialogue: 0,0:01:04.70,0:01:07.67,Default,,0000,0000,0000,,восстановив тем самым приближенный корень остатка от деления на N.
Dialogue: 0,0:01:07.67,0:01:09.95,Default,,0000,0000,0000,,Теперь мы можем раскладывать модуль,
Dialogue: 0,0:01:09.95,0:01:12.85,Default,,0000,0000,0000,,а вычисление приближенных корней остатка от деления N становится простым.
Dialogue: 0,0:01:12.85,0:01:14.64,Default,,0000,0000,0000,,Но факторизация остатков от деления, как мы знаем,
Dialogue: 0,0:01:14.64,0:01:16.76,Default,,0000,0000,0000,,это очень и очень непростая задача.
Dialogue: 0,0:01:16.76,0:01:19.86,Default,,0000,0000,0000,,Вопрос заключается в том, правда ли,
Dialogue: 0,0:01:19.86,0:01:22.57,Default,,0000,0000,0000,,что в порядке вычисления приближенных корней остатка от деления N,
Dialogue: 0,0:01:22.57,0:01:25.71,Default,,0000,0000,0000,,нам необходимо факторизовать остаток от деления N? Как мы знаем,
Dialogue: 0,0:01:25.71,0:01:27.37,Default,,0000,0000,0000,,лучший алгоритм вычисления приближенных корней
Dialogue: 0,0:01:27.37,0:01:30.00,Default,,0000,0000,0000,,остатка от деления N требует факторизации N.
Dialogue: 0,0:01:30.00,0:01:31.63,Default,,0000,0000,0000,,Но кто знает, может есть короткий путь,
Dialogue: 0,0:01:31.63,0:01:33.77,Default,,0000,0000,0000,,который позволит нам вычислить приближенный корень остатка от деления N
Dialogue: 0,0:01:33.77,0:01:36.70,Default,,0000,0000,0000,,без факторизации остатков? Чтобы показать,
Dialogue: 0,0:01:36.70,0:01:38.81,Default,,0000,0000,0000,,что это возможно, нам потребуется продемонстрировать сокращение.
Dialogue: 0,0:01:38.81,0:01:40.31,Default,,0000,0000,0000,,То есть, мы должны показать, что,
Dialogue: 0,0:01:40.31,0:01:42.00,Default,,0000,0000,0000,,если я дам вам эффективный алгоритм
Dialogue: 0,0:01:42.00,0:01:43.87,Default,,0000,0000,0000,,вычисления приближенных корней остатка от деления N,
Dialogue: 0,0:01:43.87,0:01:48.13,Default,,0000,0000,0000,,и что эффективный алгоритм может быть превращен в алгоритм разложения
Dialogue: 0,0:01:48.13,0:01:51.02,Default,,0000,0000,0000,,Это и называется сокращением. А именно, учитывая алгоритм
Dialogue: 0,0:01:51.02,0:01:53.14,Default,,0000,0000,0000,,приближенных корней остатка от деления N, мы получаем алгоритм разложения.