1
00:00:00,152 --> 00:00:01,703
A questão seguinte, vamos pedir

2
00:00:01,703 --> 00:00:03,638
RSA é realmente uma função one-way?

3
00:00:03,638 --> 00:00:05,788
Em outras palavras, é realmente difícil

4
00:00:05,788 --> 00:00:08,104
inverter RSA sem saber o alçapão?

5
00:00:09,012 --> 00:00:11,998
Assim, se um atacante queria inverter a função RSA,

6
00:00:11,998 --> 00:00:15,001
bem, o que o atacante tem, é basicamente a chave pública,

7
00:00:15,001 --> 00:00:19,054
a saber, que tem N e e. E agora, ele é dado x para o e-

8
00:00:19,054 --> 00:00:23,293
e seu objetivo é recuperar x. OK, então a questão realmente é:

9
00:00:23,293 --> 00:00:26,131
dado x para o módulo e N, como é que é difícil

10
00:00:26,131 --> 00:00:28,933
recuperar x? Então, o que estamos realmente fazendo é,

11
00:00:28,933 --> 00:00:33,113
como é que é difícil calcular e'th raízes módulo um composto?

12
00:00:34,178 --> 00:00:38,544
Se este problema acaba por ser difícil, então RSA é de fato uma função de mão única.

13
00:00:38,544 --> 00:00:39,968
Se este problema torna-se mais fácil, que

14
00:00:39,968 --> 00:00:44,564
é claro que não acredito que seja fácil, então RSA seria realmente quebrado.

15
00:00:44,564 --> 00:00:46,832
Assim, verifica-se o melhor algoritmo para este problema

16
00:00:46,832 --> 00:00:49,563
exige que o primeiro fator N. módulo

17
00:00:50,050 --> 00:00:52,236
E então, uma vez que o módulo consignado, já temos

18
00:00:52,236 --> 00:00:55,892
visto na semana passada, que é fácil de calcular a raiz e'th módulo p,

19
00:00:55,892 --> 00:00:58,483
é fácil de calcular a raiz e'th módulo q.

20
00:00:58,483 --> 00:01:02,107
E, então, dado ambas as raízes e'th, é realmente fácil de combiná-los,

21
00:01:02,107 --> 00:01:04,699
usando o que é chamado de teorema restante chinês

22
00:01:04,699 --> 00:01:07,667
e, na verdade, recuperar a raiz e'th modulo N.

23
00:01:07,667 --> 00:01:09,946
Assim, uma vez que somos capazes de fatorar o módulo,

24
00:01:09,946 --> 00:01:12,848
computação e'th raízes modulo N se torna fácil.

25
00:01:12,848 --> 00:01:14,636
Mas factoring, o módulo de elasticidade, tanto quanto

26
00:01:14,636 --> 00:01:16,761
Nós sabemos, é um problema muito, muito difícil.

27
00:01:16,761 --> 00:01:19,865
Mas uma pergunta natural é, é verdade que em

28
00:01:19,865 --> 00:01:22,568
Para calcular e'th raízes módulo N, temos que

29
00:01:22,568 --> 00:01:25,707
fator de N modulo? Tanto quanto sabemos, o

30
00:01:25,707 --> 00:01:27,369
melhor algoritmo para calcular raízes e'th

31
00:01:27,369 --> 00:01:30,002
modulo N, requer fatoração de N.

32
00:01:30,002 --> 00:01:31,626
Mas, quem sabe, talvez haja um corte curto

33
00:01:31,626 --> 00:01:33,771
que nos permitem calcular e'th raízes modulo N,

34
00:01:33,771 --> 00:01:36,704
sem fatorar o módulo. Para mostrar que

35
00:01:36,704 --> 00:01:38,808
isso não é possível, temos que mostrar uma redução.

36
00:01:38,808 --> 00:01:40,314
Isto é, temos de mostrar que,

37
00:01:40,314 --> 00:01:42,001
se eu te der um algoritmo eficiente para

38
00:01:42,001 --> 00:01:43,872
computação e'th raízes modulo N, que

39
00:01:43,872 --> 00:01:48,132
algoritmo eficiente pode ser transformado em um algoritmo de factoring.

40
00:01:48,132 --> 00:01:51,015
Então, isso é chamado de redução. Ou seja, tendo em conta um algoritmo para

41
00:01:51,015 --> 00:01:53,137
e'th raízes módulo N, obtemos um algoritmo de factoring.

42
00:01:53,137 --> 00:01:57,314
Isso mostra que não se pode calcular e'th raízes modulo N

43
00:01:57,314 --> 00:02:00,101
mais rápido do que o módulo de factoring.

44
00:02:00,101 --> 00:02:02,285
Se tivéssemos esse resultado, seria mostrar que

45
00:02:02,285 --> 00:02:05,716
realmente quebrar RSA, na verdade é tão difícil como fatorar

46
00:02:05,716 --> 00:02:08,110
Mas, infelizmente, isso não é muito conhecido no momento.

47
00:02:08,110 --> 00:02:11,969
Na verdade, este é um dos mais antigos problemas de chave pública de criptografia.

48
00:02:11,969 --> 00:02:14,415
Então, deixe-me dar-lhe um exemplo concreto.

49
00:02:14,415 --> 00:02:18,523
Suponha-se, eu dou-lhe um algoritmo que irá calcular cubo raízes módulo N.

50
00:02:19,037 --> 00:02:23,693
Assim, para qualquer x em ZN, o algoritmo irá calcular a raiz cúbica de x modulo N.

51
00:02:23,693 --> 00:02:25,971
Minha pergunta é, você pode mostrar que o uso de

52
00:02:25,971 --> 00:02:29,066
tal algoritmo pode fatorar o módulo N?

53
00:02:29,066 --> 00:02:31,239
E, mesmo que não seja conhecido. O que é conhecido,

54
00:02:31,239 --> 00:02:33,920
eu vos digo, é por exemplo, que para e igual a 2,

55
00:02:34,375 --> 00:02:37,711
isto é, se eu te dou um algoritmo para calcular raízes quadrada módulo N,

56
00:02:37,711 --> 00:02:40,696
então, de facto, que implica o factoring modulus.

57
00:02:40,696 --> 00:02:44,699
Assim, o cálculo de raízes quadradas é de fato tão duro como o módulo de factoring.

58
00:02:44,712 --> 00:02:47,779
Infelizmente, se você acha que volta para a definição de RSA,

59
00:02:47,779 --> 00:02:52,913
que exigia que 'e' vezes d é 1 mod phi (N).

60
00:02:52,913 --> 00:02:58,612
O que isto significa é que, e necessariamente tem de ser relativamente privilegiada para phi (N).

61
00:02:58,612 --> 00:03:03,128
Certo, isso, o que a primeira equação diz é que o e é inversível módulo phi (N).

62
00:03:03,128 --> 00:03:06,125
Mas, se e é invertível módulo phi (N), o que significa, necessariamente, que

63
00:03:06,125 --> 00:03:09,107
e deve ser privilegiada relativamente a phi (N).

64
00:03:09,107 --> 00:03:13,927
Mas, phi (N), se você se lembra, que é igual a menos um p vezes q menos 1.

65
00:03:13,927 --> 00:03:19,377
E, uma vez que p e q são ambos números primos grandes, p - 1 vezes q - 1 é sempre igual.

66
00:03:19,377 --> 00:03:25,503
E, como resultado, o GCD de 2 e phi (N) é igual a 2,

67
00:03:25,503 --> 00:03:28,221
porque phi (N) é mesmo. E, portanto, o público

68
00:03:28,221 --> 00:03:30,863
expoente 2 não é relativamente privilegiada para phi (N).

69
00:03:30,863 --> 00:03:33,174
que significa que, embora tenhamos uma redução

70
00:03:33,174 --> 00:03:35,263
de tomar a raiz quadrada de factoring,

71
00:03:35,263 --> 00:03:38,758
e não é igual a 2 pode ser utilizado como um expoente RSA.

72
00:03:38,758 --> 00:03:43,643
Então, realmente o menor expoente RSA que é legal é, de facto, e é igual a 3.

73
00:03:43,643 --> 00:03:46,911
Mas, para o e igual 3, a questão de se raízes cúbicas de computação

74
00:03:46,911 --> 00:03:48,976
é tão duro como factoring, é um problema em aberto.

75
00:03:48,976 --> 00:03:50,978
É realmente muito divertido pensar sobre essa questão.

76
00:03:50,978 --> 00:03:53,444
Portanto, gostaria de incentivá-lo a pensar sobre isso um pouco.

77
00:03:53,444 --> 00:03:58,352
Isto é, se eu lhe der um algoritmo eficiente para a computação cubo raízes módulo N,

78
00:03:58,352 --> 00:04:02,111
você pode usar esse algoritmo para realmente fatorar o módulo N?

79
00:04:02,111 --> 00:04:05,301
Vou dizer-lhe que há um pouco de evidência para dizer

80
00:04:05,301 --> 00:04:09,402
que uma redução como essa, na verdade não existe, mas é uma evidência muito, muito fraco.

81
00:04:09,402 --> 00:04:11,366
O que esta prova diz que é, basicamente, se você

82
00:04:11,366 --> 00:04:13,500
me dar uma redução de uma forma muito particular.

83
00:04:13,500 --> 00:04:16,070
Em outras palavras, se a sua redução é o que é chamado algébrica,

84
00:04:16,070 --> 00:04:18,509
(Eu não vou explicar o que isso significa aqui.)

85
00:04:18,509 --> 00:04:23,087
Isto é, se for dado um cubo raiz oráculo, você realmente pode me mostrar um algoritmo

86
00:04:23,087 --> 00:04:26,055
que, então, fator. Essa redução, por si só,

87
00:04:26,055 --> 00:04:28,554
seria, na verdade, implica um algoritmo de factoring.

88
00:04:28,554 --> 00:04:31,084
Ok então, que dizer que se factoring é difícil,

89
00:04:31,084 --> 00:04:33,637
uma redução na realidade não existe.

90
00:04:33,637 --> 00:04:35,537
Mas, como eu digo isso é uma evidência muito fraca.

91
00:04:35,537 --> 00:04:37,617
Porque, que é dizer que a redução deve ser algébrico.

92
00:04:37,617 --> 00:04:39,725
Talvez, há alguns outros tipos de reduções que

93
00:04:39,725 --> 00:04:42,857
não temos realmente considerado. Então, eu o faria

94
00:04:42,857 --> 00:04:44,339
incentivá-lo a pensar um pouco sobre isso

95
00:04:44,339 --> 00:04:46,235
pergunta. É realmente muito interessante.

96
00:04:46,235 --> 00:04:50,087
Como você usaria um algoritmo de raiz cúbica de fatorar o módulo?

97
00:04:51,308 --> 00:04:54,143
Mas como eu disse, tanto quanto sabemos, a RSA é uma função de uma maneira.

98
00:04:54,143 --> 00:05:00,274
Na verdade, quebrando RSA, computando raízes e'th que é, na verdade, requer módulo de factoring o.

99
00:05:00,274 --> 00:05:02,918
Nós todos acreditamos que é verdade, e isso é o estado da arte.

100
00:05:02,918 --> 00:05:07,637
Mas, agora, tem havido muito trabalho para tentar melhorar o desempenho da RSA.

101
00:05:07,637 --> 00:05:12,041
Ou criptografia, RSA ou melhorar o desempenho de decodificação RSA.

102
00:05:12,041 --> 00:05:14,901
E ao que parece, tem havido uma série de falsos começos nesta direção.

103
00:05:14,901 --> 00:05:18,796
Então, eu quero te mostrar, este maravilhoso exemplo como um aviso.

104
00:05:18,796 --> 00:05:23,232
Então, basicamente, este é um exemplo de como não se melhorar a perfomance da RSA.

105
00:05:23,232 --> 00:05:26,772
Assim, você pode pensar que se eu quisesse acelerar descriptografia RSA,

106
00:05:26,772 --> 00:05:28,578
lembre-se de decodificação é feita através do aumento da

107
00:05:28,578 --> 00:05:30,895
cifrada com a potência de d. E, lembre-se

108
00:05:30,895 --> 00:05:34,265
que o algoritmo de exponenciação correu em tempo linear

109
00:05:34,265 --> 00:05:37,767
no tamanho de d. Tempo linear no log de d.

110
00:05:37,767 --> 00:05:39,762
Assim, você pode pensar a si mesmo, bem, se eu queria

111
00:05:39,762 --> 00:05:43,522
para acelerar a decodificação RSA, por que não eu só uso um d minúsculo.

112
00:05:43,522 --> 00:05:48,265
Eu vou dizer, eu vou dizer um expoente de decodificação que é da ordem de 2 a 128.

113
00:05:48,419 --> 00:05:52,350
Então é claramente grande o suficiente para que a pesquisa exaustiva contra d não é possível.

114
00:05:52,350 --> 00:05:57,418
Mas, normalmente, a descriptografia expoente d seria tão grande como o módulo, digamos 2000 bits.

115
00:05:57,418 --> 00:06:04,669
Usando d que é apenas 128 bits, eu basicamente acelerar descriptografia RSA por um fator de 20.

116
00:06:04,669 --> 00:06:07,533
Bem, eu descia de 2000 bits para 100 bits.

117
00:06:07,533 --> 00:06:10,915
Assim, a exponenciação seria executado 20 vezes mais rápido.

118
00:06:10,915 --> 00:06:15,440
Acontece que isso é uma péssima idéia. Idéia terrível, terrível, no seguinte sentido.

119
00:06:15,440 --> 00:06:18,638
Há um ataque por Michael Wiener, que mostra que, de facto,

120
00:06:18,638 --> 00:06:23,425
assim que o expoente privado d é menor do que a quarta raiz do módulo.

121
00:06:23,425 --> 00:06:27,526
Vamos ver, se o módulo é de cerca de 2048 bits

122
00:06:27,526 --> 00:06:34,581
o que significa que, se d for menor que 2 a 512, em seguida, A RSA é completamente, completamente inseguro.

123
00:06:34,581 --> 00:06:37,509
E, isto é, ele é inseguro da pior forma possível.

124
00:06:37,509 --> 00:06:43,129
Ou seja, apenas dei uma chave pública e um e, você pode rapidamente recuperar a chave privada d.

125
00:06:44,227 --> 00:06:48,493
Bem, para algumas pessoas, disse: bem, este ataque funciona até 512 bits.

126
00:06:48,493 --> 00:06:52,378
Então, por que donÂ't fazemos o módulo, por exemplo, você sabe que 530 bits.

127
00:06:52,378 --> 00:06:54,234
Então, este ataque realmente não seria aplicável.

128
00:06:54,234 --> 00:06:57,545
Mas, ainda assim, temos de acelerar descriptografia RSA por um fator de 4,

129
00:06:57,545 --> 00:07:01,997
porque diminuiu o expoente de 2000 bits para, digamos, 530 bits.

130
00:07:01,997 --> 00:07:03,978
Bem se vê, mesmo que não seja seguro. Na verdade,

131
00:07:03,978 --> 00:07:06,243
existe uma extensão ao ataque de Wiener, que é realmente muito

132
00:07:06,243 --> 00:07:08,176
mais complicada, que mostra que se d

133
00:07:08,176 --> 00:07:13,233
é inferior a 0,292 N para o, então também RSA é inseguro.

134
00:07:13,233 --> 00:07:16,674
E, na verdade, a conjectura de que isto é verdadeiro se a N para o 0.5.

135
00:07:16,674 --> 00:07:21,975
Portanto, mesmo se d é como N para a 0,4999, RSA ainda deve ser inseguro,

136
00:07:21,975 --> 00:07:25,780
embora isso seja um problema em aberto. É, novamente, um problema maravilhoso aberto,

137
00:07:25,780 --> 00:07:28,394
Tem sido aberto para como, o que é, 14 anos.

138
00:07:28,394 --> 00:07:31,556
E, ninguém pode progredir para além desta 0,292.

139
00:07:31,556 --> 00:07:34,327
De alguma forma, parece meio estranho, por que 0,292

140
00:07:34,327 --> 00:07:38,217
ser a resposta certa e ainda ninguém pode ir além 0,292.

141
00:07:38,802 --> 00:07:41,671
Então, só para ser mais preciso, quando eu digo que a RSA é inseguro,

142
00:07:41,671 --> 00:07:45,218
o que eu quero dizer é dado apenas a chave pública N e E,

143
00:07:45,218 --> 00:07:48,077
seu objetivo é recuperar a chave secreta d.

144
00:07:49,102 --> 00:07:52,257
Se você está curioso, onde vem de 0,292,

145
00:07:52,257 --> 00:07:56,312
Eu vou te dizer que o que é, é basicamente um menos 1 sobre raiz quadrada de 2.

146
00:07:56,312 --> 00:07:58,503
Agora, como isso poderia ser a resposta certa para este problema?

147
00:07:58,503 --> 00:08:01,296
É muito mais natural que a resposta é N a 0,5.

148
00:08:01,296 --> 00:08:04,340
Mas isso ainda é um problema em aberto. Novamente, se você quer pensar sobre isso,

149
00:08:04,340 --> 00:08:06,163
é uma espécie de um problema divertido para trabalhar.

150
00:08:06,163 --> 00:08:10,101
Assim, a lição no presente é que não se deve impor qualquer estrutura em d

151
00:08:10,101 --> 00:08:12,475
para melhorar o desempenho da RSA, e de facto

152
00:08:12,475 --> 00:08:15,276
agora há uma série de resultados como este que mostram

153
00:08:15,276 --> 00:08:19,714
que, basicamente, qualquer tipo de truques como este para tentar melhorar o desempenho da RSA

154
00:08:19,714 --> 00:08:24,285
vai acabar em desastre. Portanto, este não é o caminho certo para melhorar o desempenho da RSA.

155
00:08:24,285 --> 00:08:27,987
Inicialmente eu não estava indo para cobrir os detalhes do ataque de Wiener.

156
00:08:27,987 --> 00:08:31,582
Mas dadas as discussões em classe, eu acho que alguns de vocês gostaria de ver os detalhes.

157
00:08:31,582 --> 00:08:35,229
Tudo o que envolve é apenas manipular algumas desigualdades.

158
00:08:35,229 --> 00:08:37,743
Se você não está confortável com isso, sinta-se livre para pular este slide,

159
00:08:37,743 --> 00:08:40,979
embora eu acho que muitos de vocês realmente gostam de ver os detalhes.

160
00:08:40,979 --> 00:08:43,365
Então deixe-me lembrá-lo no ataque Wiener basicamente

161
00:08:43,365 --> 00:08:46,893
nós estamos dando o módulo eo expoente RSA N e E,

162
00:08:46,893 --> 00:08:50,513
e nosso objetivo é recuperar d, o expoente privado d,

163
00:08:50,513 --> 00:08:54,171
e tudo o que sabemos é que d é basicamente menor do que a raiz quarta de N.

164
00:08:54,171 --> 00:08:57,711
Na verdade, eu vou assumir que d é menor do que a raiz quarta de N dividido por 3.

165
00:08:57,711 --> 00:09:02,373
Esta 3 realmente não importa, mas o termo dominante aqui é que d é menor do que a raiz quarta de N.

166
00:09:02,373 --> 00:09:05,944
Então vamos ver como fazê-lo. Então, primeiro de tudo, lembrar que

167
00:09:05,944 --> 00:09:09,144
porque e e d são RSA expoentes públicas e privadas,

168
00:09:09,144 --> 00:09:14,145
sabemos que e d vezes é um modulo phi (N). Bem, o que isso significa?

169
00:09:14,145 --> 00:09:22,248
Isto significa que existe algum inteiro k tal que e tempos d é igual a k vezes phi (N), acrescido de 1.

170
00:09:22,248 --> 00:09:26,280
Basicamente é o que significa para os tempos e d ser um modulo phi (N).

171
00:09:26,280 --> 00:09:29,832
Basicamente múltipla algum inteiro de phi (N) mais 1.

172
00:09:29,832 --> 00:09:32,592
Então agora vamos olhar para esta equação um pouco.

173
00:09:32,592 --> 00:09:35,826
E na verdade, esta equação é a equação-chave no ataque.

174
00:09:35,826 --> 00:09:40,352
E o que nós vamos fazer é antes de tudo dividir ambos os lados por d vezes phi (N).

175
00:09:40,352 --> 00:09:43,703
E na verdade eu vou mover este termo aqui para a esquerda.

176
00:09:43,703 --> 00:09:47,453
Então, depois que eu dividir por d vezes phi (N), o que eu vejo é que

177
00:09:47,453 --> 00:09:58,500
e dividido pelo phi (N) menos k dividido por d é igual a 1 ao longo d vezes phi (N).

178
00:09:59,469 --> 00:10:02,902
Ok, então tudo que eu fiz é que eu só dividido por d vezes phi (N)

179
00:10:02,902 --> 00:10:05,850
e mudei o k vezes phi prazo (N) para o lado esquerdo.

180
00:10:05,850 --> 00:10:09,119
Agora, apenas para os pedaços que eu estou indo para adicionar valores absolutos aqui.

181
00:10:09,119 --> 00:10:13,484
Estes irão tornar-se útil em apenas um minuto, mas é claro que eles não mudam essa igualdade em tudo.

182
00:10:13,484 --> 00:10:20,184
Agora, phi (N), claro, é quase N; phi (N) é muito, muito perto de N, como dissemos anteriormente.

183
00:10:20,184 --> 00:10:23,371
E tudo que eu vou precisar de então para essa fração é só para dizer que

184
00:10:23,371 --> 00:10:26,639
é inferior a 1 sobre raiz quadrada de N. Na verdade, é muito, muito menor

185
00:10:26,639 --> 00:10:30,571
do que 1 sobre raiz quadrada de N, na verdade é da ordem de 1 por N, ou até mais do que isso,

186
00:10:30,571 --> 00:10:35,638
mas para nossos propósitos tudo o que precisamos é que essa fração for inferior a 1 sobre raiz quadrada de N.

187
00:10:35,638 --> 00:10:37,939
Agora vamos olhar para essa fração por apenas um minuto.

188
00:10:37,939 --> 00:10:44,506
Você percebe que esta fração à esquerda aqui é uma fração que nós realmente não sabemos.

189
00:10:44,506 --> 00:10:49,039
Sabemos e, mas não sabemos phi (N), e, como resultado, não sabemos e sobre phi (N).

190
00:10:49,039 --> 00:10:53,631
Mas temos uma boa aproximação e mais de phi (N). Ou seja, sabemos que phi (N)

191
00:10:53,631 --> 00:10:59,238
está muito perto de N. Portanto, e mais de phi (N) está muito próximo e mais de N.

192
00:10:59,238 --> 00:11:03,436
Portanto, temos uma boa aproximação a esta fração lado esquerdo, e nomeadamente sobre N.

193
00:11:03,436 --> 00:11:06,028
O que realmente queremos é a fração lado direito,

194
00:11:06,028 --> 00:11:07,649
porque uma vez que temos a fração lado direito,

195
00:11:07,649 --> 00:11:12,960
basicamente, que vai envolver d, e então nós vamos ser capazes de recuperar d. Ok, então vamos ver

196
00:11:12,960 --> 00:11:19,041
se substituirmos e sobre phi (N) por e sobre N, vamos ver que tipo de erro que vamos conseguir.

197
00:11:19,041 --> 00:11:22,514
Assim, para analisar que, o que nós vamos fazer é, antes de tudo lembrar
Assim, para analisar que, o que nós vamos fazer é, antes de tudo lembrar

198
00:11:22,514 --> 00:11:26,204
que phi (N) é basicamente N - p - q + 1,

199
00:11:26,204 --> 00:11:30,804
o que significa que menos phi N (N) vai ser menor do que p + q.

200
00:11:30,804 --> 00:11:34,752
Na verdade, eu deveria, para ser mais preciso, eu realmente deveria escrever p + q + 1, mas você sabe,

201
00:11:34,752 --> 00:11:37,838
que se preocupa com este 1, que não é, ele realmente não afeta nada.

202
00:11:37,838 --> 00:11:40,238
Então, eu estou indo só para ignorá-lo pela simplicidade.

203
00:11:40,238 --> 00:11:45,508
Ok, então N - phi (N) é menor que p + q. Ambos p e q são mais ou menos metade do comprimento de N,

204
00:11:45,508 --> 00:11:48,918
assim você sabe, eles são os dois tipos de da ordem de raiz quadrada de N,

205
00:11:48,918 --> 00:11:53,876
Então, basicamente p + q vamos dizer é menos do que 3 vezes a raiz quadrada de N.

206
00:11:53,876 --> 00:11:56,844
Ok, então vamos usar essa desigualdade em apenas um minuto.

207
00:11:56,844 --> 00:12:00,243
Mas agora vamos começar a usar o fato de que sabemos algo sobre d,

208
00:12:00,243 --> 00:12:02,958
a saber, que d é pequena. Então, se olharmos para esta desigualdade aqui,

209
00:12:02,958 --> 00:12:05,543
d for inferior a quarta raiz de N dividido por 3.

210
00:12:05,543 --> 00:12:08,596
É realmente bastante fácil de ver que se eu quadrado ambos os lados

211
00:12:08,596 --> 00:12:12,118
e eu só manipular as coisas um pouco, é [não] difícil ver que

212
00:12:12,118 --> 00:12:15,510
isso implica diretamente a seguinte relação,

213
00:12:15,510 --> 00:12:24,263
basicamente um mais de 2 d quadrado menos 1 sobre raiz quadrada de N é maior do que 3 sobre raiz quadrada de N.

214
00:12:24,263 --> 00:12:28,542
Como eu disse, este segue basicamente por quadratura ambos os lados, em seguida, tendo o

215
00:12:28,542 --> 00:12:33,334
inverso de ambos os lados, e então eu acho que multiplicando um lado pelo meio.

216
00:12:33,334 --> 00:12:37,906
Ok, então você pode facilmente obter essa relação, e vamos precisar essa relação em apenas um minuto.

217
00:12:37,906 --> 00:12:40,166
Então, agora vamos ver, o que gostaria de fazer é obrigado

218
00:12:40,166 --> 00:12:45,059
a diferença de e mais de N e K sobre d. Bem, o que sabemos?

219
00:12:45,059 --> 00:12:47,872
Pela desigualdade triangular, sabemos que isso é igual a

220
00:12:47,872 --> 00:12:52,122
a distância entre e ao longo e por cima e N phi (N), além

221
00:12:52,122 --> 00:12:56,566
a distância a partir de e ao longo phi (N) para k ao longo d.

222
00:12:56,566 --> 00:13:01,813
Este é apenas o que é chamado de uma desigualdade triangular, esta é apenas uma propriedade de valores absolutos.

223
00:13:01,813 --> 00:13:04,705
Agora, este valor absoluto aqui, nós já sabemos como vinculado.

224
00:13:04,705 --> 00:13:07,116
Se você pensar sobre isso é basicamente o limite que nós já derivada.

225
00:13:07,116 --> 00:13:11,977
Então, nós sabemos que este valor absoluto aqui é basicamente menor do que 1 sobre raiz quadrada de N.

226
00:13:11,977 --> 00:13:17,737
Agora, o que nós sabemos sobre esse valor absoluto aqui? O que é e mais N menos e mais de phi (N)?

227
00:13:17,737 --> 00:13:20,486
Bem, vamos fazer denominadores comuns e ver o que conseguimos.

228
00:13:20,486 --> 00:13:25,236
Assim, o denominador comum que vai ser N vezes phi (N),

229
00:13:25,236 --> 00:13:31,253
o numerador e, neste caso, vai ser vezes e phi (N) menos N.

230
00:13:31,253 --> 00:13:35,760
Que sabemos desta expressão aqui é menos do que três vezes a raiz quadrada de N.

231
00:13:35,760 --> 00:13:40,842
Então, realmente o que esta numerador vai ser é o e três vezes a raiz quadrada de N.

232
00:13:40,842 --> 00:13:44,327
O numerador vai ser menor do que e 3 vezes a raiz quadrada de N.

233
00:13:44,327 --> 00:13:51,246
Então agora eu sei que e é menor do que phi (N), então eu sei que e mais de phi (N) é menor que 1.

234
00:13:51,246 --> 00:13:57,313
Em outras palavras, se eu apagar e apagar e eu phi (N) Eu só fez a fração maior.

235
00:13:57,313 --> 00:14:00,016
Ok, então esse valor inicial absoluta é agora vai ser

236
00:14:00,016 --> 00:14:03,655
menor do que 3 raiz quadrada de N sobre N, que é simplesmente,

237
00:14:03,655 --> 00:14:09,237
3 raiz quadrada de N sobre N é simplesmente 3 sobre raiz quadrada de N.

238
00:14:09,237 --> 00:14:11,270
Ok, mas o que sabemos sobre a 3 sobre raiz quadrada de N?

239
00:14:11,270 --> 00:14:17,706
Nós sabemos que é menos de 1 por 2 d quadrado menos 1 sobre raiz quadrada de N.

240
00:14:17,706 --> 00:14:20,473
Ok, então esse é o fim da nossa derivação.

241
00:14:20,473 --> 00:14:26,439
Portanto, agora sabemos que o primeiro valor absoluto é menor do que 1 sobre 2 raiz d quadrado menos quadrado da N.

242
00:14:26,439 --> 00:14:29,509
O segundo valor absoluto for inferior a 1 sobre raiz quadrada de N.

243
00:14:29,509 --> 00:14:34,369
E, portanto, a soma é inferior a 1 sobre 2 d quadrado.

244
00:14:34,369 --> 00:14:36,576
E esta é a expressão que eu quero que você olhar.

245
00:14:36,576 --> 00:14:42,951
Então, aqui, deixe-me rodear-lo um pouco. Então deixe-me circular esta parte e esta parte.

246
00:14:43,582 --> 00:14:46,445
Agora, vamos olhar um pouco neste fração aqui.

247
00:14:46,445 --> 00:14:51,444
E o que vemos é, antes de tudo, como antes, agora sabemos o valor de e mais de N,

248
00:14:51,444 --> 00:14:54,825
eo que nós gostaríamos de saber é o valor k sobre d.

249
00:14:54,825 --> 00:14:56,862
Mas o que sabemos sobre este k fração sobre d?

250
00:14:56,862 --> 00:15:00,715
Nós sabemos de alguma forma que a diferença entre essas duas frações é muito pequeno;

251
00:15:00,715 --> 00:15:05,385
é inferior a 1 sobre 2 d quadrado. Agora, isso acaba por acontecer muito raramente,

252
00:15:05,385 --> 00:15:10,588
que k mais d aproxima e mais de N tão bem que

253
00:15:10,588 --> 00:15:15,307
a diferença entre os dois é menor do que o quadrado do denominador de k ao longo d.

254
00:15:15,307 --> 00:15:17,324
Acontece que isso não pode acontecer muitas vezes.

255
00:15:17,324 --> 00:15:22,338
Acontece que há muito poucas frações da forma k mais d que a fração de outra aproximada

256
00:15:22,338 --> 00:15:26,422
tão bem que a sua diferença é inferior a 1 durante 2 d quadrado.

257
00:15:26,422 --> 00:15:30,308
E, de facto, o número de tais fracções vai ser, no máximo, em N. logarítmica

258
00:15:30,308 --> 00:15:33,953
Portanto, agora há um algoritmo de fração contínua. É uma fração muito famoso

259
00:15:33,953 --> 00:15:38,877
que, basicamente, o que ele vai fazer é, a partir do e fração sobre N,

260
00:15:38,877 --> 00:15:42,977
ele vai se recuperar de log (N) possíveis candidatos para k sobre d.

261
00:15:42,977 --> 00:15:47,148
Então, nós apenas julgá-los todos, um por um até encontrar o k correto sobre d.

262
00:15:47,148 --> 00:15:51,645
E, então, está feito. Estamos a fazer, porque sabemos que,

263
00:15:51,645 --> 00:15:55,376
bem vezes e d é 1 k mod, portanto d é relativamente privilegiada para k,

264
00:15:55,376 --> 00:16:00,852
por isso, se nós apenas representam k mais d como uma fração racional numerador, você sabe, por denominador,

265
00:16:00,852 --> 00:16:05,271
o denominador deve ser d. E assim acabou recuperado, você sabe,

266
00:16:05,271 --> 00:16:10,355
nós tentamos todos os possíveis log (N) e frações que mais aproximado N tão bem

267
00:16:10,355 --> 00:16:13,688
que a diferença é inferior a 1 durante 2 d quadrado.

268
00:16:13,688 --> 00:16:19,338
E, então, basta olhar para o denominador de todas as frações, e um dos denominadores deve ser d.

269
00:16:19,338 --> 00:16:22,841
E, então, está feito; acabamos recuperou a chave privada.

270
00:16:22,841 --> 00:16:26,341
Portanto, este é um ataque muito bonito. E mostra, basicamente, como,

271
00:16:26,341 --> 00:16:31,267
se o expoente privado é pequeno, menor do que a quarta raiz de N,

272
00:16:31,267 --> 00:16:35,354
então podemos recuperar d completamente, com bastante facilidade. Ok, então eu vou parar por aqui.