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

2
00:00:01,703 --> 00:00:03,638
является ли RSA по настоящему односторонней функцией.

3
00:00:03,638 --> 00:00:05,788
Или другими словами: на сколько сложно

4
00:00:05,788 --> 00:00:08,104
обратить RSA без знания "черного хода"?

5
00:00:09,012 --> 00:00:11,998
Итак, если атакующий хочет обратить RSA функцию,

6
00:00:11,998 --> 00:00:15,001
при этом в основном обладая открытым ключом,

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

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

9
00:00:23,293 --> 00:00:26,131
насколько сложно получить x в степени e по модулю N.

10
00:00:26,131 --> 00:00:28,933
В итоге на самом деле мы задаем вопрос

11
00:00:28,933 --> 00:00:33,113
насколько сложно вычислить приближенные корни по составному модулю.

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

13
00:00:38,544 --> 00:00:39,968
А если окажется простой,

14
00:00:39,968 --> 00:00:44,564
во что нам не хотелось бы верить, тогда бы RSA давно бы был взломан

15
00:00:44,564 --> 00:00:46,832
Таким образом лучший алгоритм для решения этой проблемы

16
00:00:46,832 --> 00:00:49,563
заключается в вычислении факториала модуля N.

17
00:00:50,050 --> 00:00:52,236
А затем, после вычисления факториала, как мы это делали

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

19
00:00:55,892 --> 00:00:58,483
легко вычислить приближенный корень остатка от деления q.

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

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

22
00:01:04,699 --> 00:01:07,667
восстановив тем самым приближенный корень остатка от деления на N.

23
00:01:07,667 --> 00:01:09,946
Теперь мы можем раскладывать модуль,

24
00:01:09,946 --> 00:01:12,848
а вычисление приближенных корней остатка от деления N становится простым.

25
00:01:12,848 --> 00:01:14,636
Но факторизация остатков от деления, как мы знаем,

26
00:01:14,636 --> 00:01:16,761
это очень и очень непростая задача.

27
00:01:16,761 --> 00:01:19,865
Вопрос заключается в том, правда ли,

28
00:01:19,865 --> 00:01:22,568
что в порядке вычисления приближенных корней остатка от деления N,

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

30
00:01:25,707 --> 00:01:27,369
лучший алгоритм вычисления приближенных корней

31
00:01:27,369 --> 00:01:30,002
остатка от деления N требует факторизации N.

32
00:01:30,002 --> 00:01:31,626
Но кто знает, может есть короткий путь,

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

34
00:01:33,771 --> 00:01:36,704
без факторизации остатков? Чтобы показать,

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

36
00:01:38,808 --> 00:01:40,314
То есть, мы должны показать, что,

37
00:01:40,314 --> 00:01:42,001
если я дам вам эффективный алгоритм

38
00:01:42,001 --> 00:01:43,872
вычисления приближенных корней остатка от деления N,

39
00:01:43,872 --> 00:01:48,132
и что эффективный алгоритм может быть превращен в алгоритм разложения

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

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