0:00:00.152,0:00:01.703
A questão seguinte, vamos pedir

0:00:01.703,0:00:03.638
RSA é realmente uma função one-way?

0:00:03.638,0:00:05.788
Em outras palavras, é realmente difícil

0:00:05.788,0:00:08.104
inverter RSA sem saber o alçapão?

0:00:09.012,0:00:11.998
Assim, se um atacante queria inverter a função RSA,

0:00:11.998,0:00:15.001
bem, o que o atacante tem, é basicamente a chave pública,

0:00:15.001,0:00:19.054
a saber, que tem N e e. E agora, ele é dado x para o e-

0:00:19.054,0:00:23.293
e seu objetivo é recuperar x. OK, então a questão realmente é:

0:00:23.293,0:00:26.131
dado x para o módulo e N, como é que é difícil

0:00:26.131,0:00:28.933
recuperar x? Então, o que estamos realmente fazendo é,

0:00:28.933,0:00:33.113
como é que é difícil calcular e'th raízes módulo um composto?

0:00:34.178,0:00:38.544
Se este problema acaba por ser difícil, então RSA é de fato uma função de mão única.

0:00:38.544,0:00:39.968
Se este problema torna-se mais fácil, que

0:00:39.968,0:00:44.564
é claro que não acredito que seja fácil, então RSA seria realmente quebrado.

0:00:44.564,0:00:46.832
Assim, verifica-se o melhor algoritmo para este problema

0:00:46.832,0:00:49.563
exige que o primeiro fator N. módulo

0:00:50.050,0:00:52.236
E então, uma vez que o módulo consignado, já temos

0:00:52.236,0:00:55.892
visto na semana passada, que é fácil de calcular a raiz e'th módulo p,

0:00:55.892,0:00:58.483
é fácil de calcular a raiz e'th módulo q.

0:00:58.483,0:01:02.107
E, então, dado ambas as raízes e'th, é realmente fácil de combiná-los,

0:01:02.107,0:01:04.699
usando o que é chamado de teorema restante chinês

0:01:04.699,0:01:07.667
e, na verdade, recuperar a raiz e'th modulo N.

0:01:07.667,0:01:09.946
Assim, uma vez que somos capazes de fatorar o módulo,

0:01:09.946,0:01:12.848
computação e'th raízes modulo N se torna fácil.

0:01:12.848,0:01:14.636
Mas factoring, o módulo de elasticidade, tanto quanto

0:01:14.636,0:01:16.761
Nós sabemos, é um problema muito, muito difícil.

0:01:16.761,0:01:19.865
Mas uma pergunta natural é, é verdade que em

0:01:19.865,0:01:22.568
Para calcular e'th raízes módulo N, temos que

0:01:22.568,0:01:25.707
fator de N modulo? Tanto quanto sabemos, o

0:01:25.707,0:01:27.369
melhor algoritmo para calcular raízes e'th

0:01:27.369,0:01:30.002
modulo N, requer fatoração de N.

0:01:30.002,0:01:31.626
Mas, quem sabe, talvez haja um corte curto

0:01:31.626,0:01:33.771
que nos permitem calcular e'th raízes modulo N,

0:01:33.771,0:01:36.704
sem fatorar o módulo. Para mostrar que

0:01:36.704,0:01:38.808
isso não é possível, temos que mostrar uma redução.

0:01:38.808,0:01:40.314
Isto é, temos de mostrar que,

0:01:40.314,0:01:42.001
se eu te der um algoritmo eficiente para

0:01:42.001,0:01:43.872
computação e'th raízes modulo N, que

0:01:43.872,0:01:48.132
algoritmo eficiente pode ser transformado em um algoritmo de factoring.

0:01:48.132,0:01:51.015
Então, isso é chamado de redução. Ou seja, tendo em conta um algoritmo para

0:01:51.015,0:01:53.137
e'th raízes módulo N, obtemos um algoritmo de factoring.

0:01:53.137,0:01:57.314
Isso mostra que não se pode calcular e'th raízes modulo N

0:01:57.314,0:02:00.101
mais rápido do que o módulo de factoring.

0:02:00.101,0:02:02.285
Se tivéssemos esse resultado, seria mostrar que

0:02:02.285,0:02:05.716
realmente quebrar RSA, na verdade é tão difícil como fatorar

0:02:05.716,0:02:08.110
Mas, infelizmente, isso não é muito conhecido no momento.

0:02:08.110,0:02:11.969
Na verdade, este é um dos mais antigos problemas de chave pública de criptografia.

0:02:11.969,0:02:14.415
Então, deixe-me dar-lhe um exemplo concreto.

0:02:14.415,0:02:18.523
Suponha-se, eu dou-lhe um algoritmo que irá calcular cubo raízes módulo N.

0:02:19.037,0:02:23.693
Assim, para qualquer x em ZN, o algoritmo irá calcular a raiz cúbica de x modulo N.

0:02:23.693,0:02:25.971
Minha pergunta é, você pode mostrar que o uso de

0:02:25.971,0:02:29.066
tal algoritmo pode fatorar o módulo N?

0:02:29.066,0:02:31.239
E, mesmo que não seja conhecido. O que é conhecido,

0:02:31.239,0:02:33.920
eu vos digo, é por exemplo, que para e igual a 2,

0:02:34.375,0:02:37.711
isto é, se eu te dou um algoritmo para calcular raízes quadrada módulo N,

0:02:37.711,0:02:40.696
então, de facto, que implica o factoring modulus.

0:02:40.696,0:02:44.699
Assim, o cálculo de raízes quadradas é de fato tão duro como o módulo de factoring.

0:02:44.712,0:02:47.779
Infelizmente, se você acha que volta para a definição de RSA,

0:02:47.779,0:02:52.913
que exigia que 'e' vezes d é 1 mod phi (N).

0:02:52.913,0:02:58.612
O que isto significa é que, e necessariamente tem de ser relativamente privilegiada para phi (N).

0:02:58.612,0:03:03.128
Certo, isso, o que a primeira equação diz é que o e é inversível módulo phi (N).

0:03:03.128,0:03:06.125
Mas, se e é invertível módulo phi (N), o que significa, necessariamente, que

0:03:06.125,0:03:09.107
e deve ser privilegiada relativamente a phi (N).

0:03:09.107,0:03:13.927
Mas, phi (N), se você se lembra, que é igual a menos um p vezes q menos 1.

0:03:13.927,0:03:19.377
E, uma vez que p e q são ambos números primos grandes, p - 1 vezes q - 1 é sempre igual.

0:03:19.377,0:03:25.503
E, como resultado, o GCD de 2 e phi (N) é igual a 2,

0:03:25.503,0:03:28.221
porque phi (N) é mesmo. E, portanto, o público

0:03:28.221,0:03:30.863
expoente 2 não é relativamente privilegiada para phi (N).

0:03:30.863,0:03:33.174
que significa que, embora tenhamos uma redução

0:03:33.174,0:03:35.263
de tomar a raiz quadrada de factoring,

0:03:35.263,0:03:38.758
e não é igual a 2 pode ser utilizado como um expoente RSA.

0:03:38.758,0:03:43.643
Então, realmente o menor expoente RSA que é legal é, de facto, e é igual a 3.

0:03:43.643,0:03:46.911
Mas, para o e igual 3, a questão de se raízes cúbicas de computação

0:03:46.911,0:03:48.976
é tão duro como factoring, é um problema em aberto.

0:03:48.976,0:03:50.978
É realmente muito divertido pensar sobre essa questão.

0:03:50.978,0:03:53.444
Portanto, gostaria de incentivá-lo a pensar sobre isso um pouco.

0:03:53.444,0:03:58.352
Isto é, se eu lhe der um algoritmo eficiente para a computação cubo raízes módulo N,

0:03:58.352,0:04:02.111
você pode usar esse algoritmo para realmente fatorar o módulo N?

0:04:02.111,0:04:05.301
Vou dizer-lhe que há um pouco de evidência para dizer

0:04:05.301,0:04:09.402
que uma redução como essa, na verdade não existe, mas é uma evidência muito, muito fraco.

0:04:09.402,0:04:11.366
O que esta prova diz que é, basicamente, se você

0:04:11.366,0:04:13.500
me dar uma redução de uma forma muito particular.

0:04:13.500,0:04:16.070
Em outras palavras, se a sua redução é o que é chamado algébrica,

0:04:16.070,0:04:18.509
(Eu não vou explicar o que isso significa aqui.)

0:04:18.509,0:04:23.087
Isto é, se for dado um cubo raiz oráculo, você realmente pode me mostrar um algoritmo

0:04:23.087,0:04:26.055
que, então, fator. Essa redução, por si só,

0:04:26.055,0:04:28.554
seria, na verdade, implica um algoritmo de factoring.

0:04:28.554,0:04:31.084
Ok então, que dizer que se factoring é difícil,

0:04:31.084,0:04:33.637
uma redução na realidade não existe.

0:04:33.637,0:04:35.537
Mas, como eu digo isso é uma evidência muito fraca.

0:04:35.537,0:04:37.617
Porque, que é dizer que a redução deve ser algébrico.

0:04:37.617,0:04:39.725
Talvez, há alguns outros tipos de reduções que

0:04:39.725,0:04:42.857
não temos realmente considerado. Então, eu o faria

0:04:42.857,0:04:44.339
incentivá-lo a pensar um pouco sobre isso

0:04:44.339,0:04:46.235
pergunta. É realmente muito interessante.

0:04:46.235,0:04:50.087
Como você usaria um algoritmo de raiz cúbica de fatorar o módulo?

0:04:51.308,0:04:54.143
Mas como eu disse, tanto quanto sabemos, a RSA é uma função de uma maneira.

0:04:54.143,0:05:00.274
Na verdade, quebrando RSA, computando raízes e'th que é, na verdade, requer módulo de factoring o.

0:05:00.274,0:05:02.918
Nós todos acreditamos que é verdade, e isso é o estado da arte.

0:05:02.918,0:05:07.637
Mas, agora, tem havido muito trabalho para tentar melhorar o desempenho da RSA.

0:05:07.637,0:05:12.041
Ou criptografia, RSA ou melhorar o desempenho de decodificação RSA.

0:05:12.041,0:05:14.901
E ao que parece, tem havido uma série de falsos começos nesta direção.

0:05:14.901,0:05:18.796
Então, eu quero te mostrar, este maravilhoso exemplo como um aviso.

0:05:18.796,0:05:23.232
Então, basicamente, este é um exemplo de como não se melhorar a perfomance da RSA.

0:05:23.232,0:05:26.772
Assim, você pode pensar que se eu quisesse acelerar descriptografia RSA,

0:05:26.772,0:05:28.578
lembre-se de decodificação é feita através do aumento da

0:05:28.578,0:05:30.895
cifrada com a potência de d. E, lembre-se

0:05:30.895,0:05:34.265
que o algoritmo de exponenciação correu em tempo linear

0:05:34.265,0:05:37.767
no tamanho de d. Tempo linear no log de d.

0:05:37.767,0:05:39.762
Assim, você pode pensar a si mesmo, bem, se eu queria

0:05:39.762,0:05:43.522
para acelerar a decodificação RSA, por que não eu só uso um d minúsculo.

0:05:43.522,0:05:48.265
Eu vou dizer, eu vou dizer um expoente de decodificação que é da ordem de 2 a 128.

0:05:48.419,0:05:52.350
Então é claramente grande o suficiente para que a pesquisa exaustiva contra d não é possível.

0:05:52.350,0:05:57.418
Mas, normalmente, a descriptografia expoente d seria tão grande como o módulo, digamos 2000 bits.

0:05:57.418,0:06:04.669
Usando d que é apenas 128 bits, eu basicamente acelerar descriptografia RSA por um fator de 20.

0:06:04.669,0:06:07.533
Bem, eu descia de 2000 bits para 100 bits.

0:06:07.533,0:06:10.915
Assim, a exponenciação seria executado 20 vezes mais rápido.

0:06:10.915,0:06:15.440
Acontece que isso é uma péssima idéia. Idéia terrível, terrível, no seguinte sentido.

0:06:15.440,0:06:18.638
Há um ataque por Michael Wiener, que mostra que, de facto,

0:06:18.638,0:06:23.425
assim que o expoente privado d é menor do que a quarta raiz do módulo.

0:06:23.425,0:06:27.526
Vamos ver, se o módulo é de cerca de 2048 bits

0:06:27.526,0:06:34.581
o que significa que, se d for menor que 2 a 512, em seguida, A RSA é completamente, completamente inseguro.

0:06:34.581,0:06:37.509
E, isto é, ele é inseguro da pior forma possível.

0:06:37.509,0:06:43.129
Ou seja, apenas dei uma chave pública e um e, você pode rapidamente recuperar a chave privada d.

0:06:44.227,0:06:48.493
Bem, para algumas pessoas, disse: bem, este ataque funciona até 512 bits.

0:06:48.493,0:06:52.378
Então, por que donÂ't fazemos o módulo, por exemplo, você sabe que 530 bits.

0:06:52.378,0:06:54.234
Então, este ataque realmente não seria aplicável.

0:06:54.234,0:06:57.545
Mas, ainda assim, temos de acelerar descriptografia RSA por um fator de 4,

0:06:57.545,0:07:01.997
porque diminuiu o expoente de 2000 bits para, digamos, 530 bits.

0:07:01.997,0:07:03.978
Bem se vê, mesmo que não seja seguro. Na verdade,

0:07:03.978,0:07:06.243
existe uma extensão ao ataque de Wiener, que é realmente muito

0:07:06.243,0:07:08.176
mais complicada, que mostra que se d

0:07:08.176,0:07:13.233
é inferior a 0,292 N para o, então também RSA é inseguro.

0:07:13.233,0:07:16.674
E, na verdade, a conjectura de que isto é verdadeiro se a N para o 0.5.

0:07:16.674,0:07:21.975
Portanto, mesmo se d é como N para a 0,4999, RSA ainda deve ser inseguro,

0:07:21.975,0:07:25.780
embora isso seja um problema em aberto. É, novamente, um problema maravilhoso aberto,

0:07:25.780,0:07:28.394
Tem sido aberto para como, o que é, 14 anos.

0:07:28.394,0:07:31.556
E, ninguém pode progredir para além desta 0,292.

0:07:31.556,0:07:34.327
De alguma forma, parece meio estranho, por que 0,292

0:07:34.327,0:07:38.217
ser a resposta certa e ainda ninguém pode ir além 0,292.

0:07:38.802,0:07:41.671
Então, só para ser mais preciso, quando eu digo que a RSA é inseguro,

0:07:41.671,0:07:45.218
o que eu quero dizer é dado apenas a chave pública N e E,

0:07:45.218,0:07:48.077
seu objetivo é recuperar a chave secreta d.

0:07:49.102,0:07:52.257
Se você está curioso, onde vem de 0,292,

0:07:52.257,0:07:56.312
Eu vou te dizer que o que é, é basicamente um menos 1 sobre raiz quadrada de 2.

0:07:56.312,0:07:58.503
Agora, como isso poderia ser a resposta certa para este problema?

0:07:58.503,0:08:01.296
É muito mais natural que a resposta é N a 0,5.

0:08:01.296,0:08:04.340
Mas isso ainda é um problema em aberto. Novamente, se você quer pensar sobre isso,

0:08:04.340,0:08:06.163
é uma espécie de um problema divertido para trabalhar.

0:08:06.163,0:08:10.101
Assim, a lição no presente é que não se deve impor qualquer estrutura em d

0:08:10.101,0:08:12.475
para melhorar o desempenho da RSA, e de facto

0:08:12.475,0:08:15.276
agora há uma série de resultados como este que mostram

0:08:15.276,0:08:19.714
que, basicamente, qualquer tipo de truques como este para tentar melhorar o desempenho da RSA

0:08:19.714,0:08:24.285
vai acabar em desastre. Portanto, este não é o caminho certo para melhorar o desempenho da RSA.

0:08:24.285,0:08:27.987
Inicialmente eu não estava indo para cobrir os detalhes do ataque de Wiener.

0:08:27.987,0:08:31.582
Mas dadas as discussões em classe, eu acho que alguns de vocês gostaria de ver os detalhes.

0:08:31.582,0:08:35.229
Tudo o que envolve é apenas manipular algumas desigualdades.

0:08:35.229,0:08:37.743
Se você não está confortável com isso, sinta-se livre para pular este slide,

0:08:37.743,0:08:40.979
embora eu acho que muitos de vocês realmente gostam de ver os detalhes.

0:08:40.979,0:08:43.365
Então deixe-me lembrá-lo no ataque Wiener basicamente

0:08:43.365,0:08:46.893
nós estamos dando o módulo eo expoente RSA N e E,

0:08:46.893,0:08:50.513
e nosso objetivo é recuperar d, o expoente privado d,

0:08:50.513,0:08:54.171
e tudo o que sabemos é que d é basicamente menor do que a raiz quarta de N.

0:08:54.171,0:08:57.711
Na verdade, eu vou assumir que d é menor do que a raiz quarta de N dividido por 3.

0:08:57.711,0:09:02.373
Esta 3 realmente não importa, mas o termo dominante aqui é que d é menor do que a raiz quarta de N.

0:09:02.373,0:09:05.944
Então vamos ver como fazê-lo. Então, primeiro de tudo, lembrar que

0:09:05.944,0:09:09.144
porque e e d são RSA expoentes públicas e privadas,

0:09:09.144,0:09:14.145
sabemos que e d vezes é um modulo phi (N). Bem, o que isso significa?

0:09:14.145,0:09:22.248
Isto significa que existe algum inteiro k tal que e tempos d é igual a k vezes phi (N), acrescido de 1.

0:09:22.248,0:09:26.280
Basicamente é o que significa para os tempos e d ser um modulo phi (N).

0:09:26.280,0:09:29.832
Basicamente múltipla algum inteiro de phi (N) mais 1.

0:09:29.832,0:09:32.592
Então agora vamos olhar para esta equação um pouco.

0:09:32.592,0:09:35.826
E na verdade, esta equação é a equação-chave no ataque.

0:09:35.826,0:09:40.352
E o que nós vamos fazer é antes de tudo dividir ambos os lados por d vezes phi (N).

0:09:40.352,0:09:43.703
E na verdade eu vou mover este termo aqui para a esquerda.

0:09:43.703,0:09:47.453
Então, depois que eu dividir por d vezes phi (N), o que eu vejo é que

0:09:47.453,0:09:58.500
e dividido pelo phi (N) menos k dividido por d é igual a 1 ao longo d vezes phi (N).

0:09:59.469,0:10:02.902
Ok, então tudo que eu fiz é que eu só dividido por d vezes phi (N)

0:10:02.902,0:10:05.850
e mudei o k vezes phi prazo (N) para o lado esquerdo.

0:10:05.850,0:10:09.119
Agora, apenas para os pedaços que eu estou indo para adicionar valores absolutos aqui.

0:10:09.119,0:10:13.484
Estes irão tornar-se útil em apenas um minuto, mas é claro que eles não mudam essa igualdade em tudo.

0:10:13.484,0:10:20.184
Agora, phi (N), claro, é quase N; phi (N) é muito, muito perto de N, como dissemos anteriormente.

0:10:20.184,0:10:23.371
E tudo que eu vou precisar de então para essa fração é só para dizer que

0:10:23.371,0:10:26.639
é inferior a 1 sobre raiz quadrada de N. Na verdade, é muito, muito menor

0:10:26.639,0: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,

0:10:30.571,0: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.

0:10:35.638,0:10:37.939
Agora vamos olhar para essa fração por apenas um minuto.

0:10:37.939,0:10:44.506
Você percebe que esta fração à esquerda aqui é uma fração que nós realmente não sabemos.

0:10:44.506,0:10:49.039
Sabemos e, mas não sabemos phi (N), e, como resultado, não sabemos e sobre phi (N).

0:10:49.039,0:10:53.631
Mas temos uma boa aproximação e mais de phi (N). Ou seja, sabemos que phi (N)

0:10:53.631,0:10:59.238
está muito perto de N. Portanto, e mais de phi (N) está muito próximo e mais de N.

0:10:59.238,0:11:03.436
Portanto, temos uma boa aproximação a esta fração lado esquerdo, e nomeadamente sobre N.

0:11:03.436,0:11:06.028
O que realmente queremos é a fração lado direito,

0:11:06.028,0:11:07.649
porque uma vez que temos a fração lado direito,

0:11:07.649,0:11:12.960
basicamente, que vai envolver d, e então nós vamos ser capazes de recuperar d. Ok, então vamos ver

0:11:12.960,0:11:19.041
se substituirmos e sobre phi (N) por e sobre N, vamos ver que tipo de erro que vamos conseguir.

0:11:19.041,0:11:22.514
Assim, para analisar que, o que nós vamos fazer é, antes de tudo lembrar[br]Assim, para analisar que, o que nós vamos fazer é, antes de tudo lembrar

0:11:22.514,0:11:26.204
que phi (N) é basicamente N - p - q + 1,

0:11:26.204,0:11:30.804
o que significa que menos phi N (N) vai ser menor do que p + q.

0:11:30.804,0:11:34.752
Na verdade, eu deveria, para ser mais preciso, eu realmente deveria escrever p + q + 1, mas você sabe,

0:11:34.752,0:11:37.838
que se preocupa com este 1, que não é, ele realmente não afeta nada.

0:11:37.838,0:11:40.238
Então, eu estou indo só para ignorá-lo pela simplicidade.

0:11:40.238,0: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,

0:11:45.508,0:11:48.918
assim você sabe, eles são os dois tipos de da ordem de raiz quadrada de N,

0:11:48.918,0:11:53.876
Então, basicamente p + q vamos dizer é menos do que 3 vezes a raiz quadrada de N.

0:11:53.876,0:11:56.844
Ok, então vamos usar essa desigualdade em apenas um minuto.

0:11:56.844,0:12:00.243
Mas agora vamos começar a usar o fato de que sabemos algo sobre d,

0:12:00.243,0:12:02.958
a saber, que d é pequena. Então, se olharmos para esta desigualdade aqui,

0:12:02.958,0:12:05.543
d for inferior a quarta raiz de N dividido por 3.

0:12:05.543,0:12:08.596
É realmente bastante fácil de ver que se eu quadrado ambos os lados

0:12:08.596,0:12:12.118
e eu só manipular as coisas um pouco, é [não] difícil ver que

0:12:12.118,0:12:15.510
isso implica diretamente a seguinte relação,

0:12:15.510,0: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.

0:12:24.263,0:12:28.542
Como eu disse, este segue basicamente por quadratura ambos os lados, em seguida, tendo o

0:12:28.542,0:12:33.334
inverso de ambos os lados, e então eu acho que multiplicando um lado pelo meio.

0:12:33.334,0:12:37.906
Ok, então você pode facilmente obter essa relação, e vamos precisar essa relação em apenas um minuto.

0:12:37.906,0:12:40.166
Então, agora vamos ver, o que gostaria de fazer é obrigado

0:12:40.166,0:12:45.059
a diferença de e mais de N e K sobre d. Bem, o que sabemos?

0:12:45.059,0:12:47.872
Pela desigualdade triangular, sabemos que isso é igual a

0:12:47.872,0:12:52.122
a distância entre e ao longo e por cima e N phi (N), além

0:12:52.122,0:12:56.566
a distância a partir de e ao longo phi (N) para k ao longo d.

0:12:56.566,0:13:01.813
Este é apenas o que é chamado de uma desigualdade triangular, esta é apenas uma propriedade de valores absolutos.

0:13:01.813,0:13:04.705
Agora, este valor absoluto aqui, nós já sabemos como vinculado.

0:13:04.705,0:13:07.116
Se você pensar sobre isso é basicamente o limite que nós já derivada.

0:13:07.116,0:13:11.977
Então, nós sabemos que este valor absoluto aqui é basicamente menor do que 1 sobre raiz quadrada de N.

0:13:11.977,0: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)?

0:13:17.737,0:13:20.486
Bem, vamos fazer denominadores comuns e ver o que conseguimos.

0:13:20.486,0:13:25.236
Assim, o denominador comum que vai ser N vezes phi (N),

0:13:25.236,0:13:31.253
o numerador e, neste caso, vai ser vezes e phi (N) menos N.

0:13:31.253,0:13:35.760
Que sabemos desta expressão aqui é menos do que três vezes a raiz quadrada de N.

0:13:35.760,0:13:40.842
Então, realmente o que esta numerador vai ser é o e três vezes a raiz quadrada de N.

0:13:40.842,0:13:44.327
O numerador vai ser menor do que e 3 vezes a raiz quadrada de N.

0:13:44.327,0: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.

0:13:51.246,0:13:57.313
Em outras palavras, se eu apagar e apagar e eu phi (N) Eu só fez a fração maior.

0:13:57.313,0:14:00.016
Ok, então esse valor inicial absoluta é agora vai ser

0:14:00.016,0:14:03.655
menor do que 3 raiz quadrada de N sobre N, que é simplesmente,

0:14:03.655,0:14:09.237
3 raiz quadrada de N sobre N é simplesmente 3 sobre raiz quadrada de N.

0:14:09.237,0:14:11.270
Ok, mas o que sabemos sobre a 3 sobre raiz quadrada de N?

0:14:11.270,0:14:17.706
Nós sabemos que é menos de 1 por 2 d quadrado menos 1 sobre raiz quadrada de N.

0:14:17.706,0:14:20.473
Ok, então esse é o fim da nossa derivação.

0:14:20.473,0:14:26.439
Portanto, agora sabemos que o primeiro valor absoluto é menor do que 1 sobre 2 raiz d quadrado menos quadrado da N.

0:14:26.439,0:14:29.509
O segundo valor absoluto for inferior a 1 sobre raiz quadrada de N.

0:14:29.509,0:14:34.369
E, portanto, a soma é inferior a 1 sobre 2 d quadrado.

0:14:34.369,0:14:36.576
E esta é a expressão que eu quero que você olhar.

0:14:36.576,0:14:42.951
Então, aqui, deixe-me rodear-lo um pouco. Então deixe-me circular esta parte e esta parte.

0:14:43.582,0:14:46.445
Agora, vamos olhar um pouco neste fração aqui.

0:14:46.445,0:14:51.444
E o que vemos é, antes de tudo, como antes, agora sabemos o valor de e mais de N,

0:14:51.444,0:14:54.825
eo que nós gostaríamos de saber é o valor k sobre d.

0:14:54.825,0:14:56.862
Mas o que sabemos sobre este k fração sobre d?

0:14:56.862,0:15:00.715
Nós sabemos de alguma forma que a diferença entre essas duas frações é muito pequeno;

0:15:00.715,0:15:05.385
é inferior a 1 sobre 2 d quadrado. Agora, isso acaba por acontecer muito raramente,

0:15:05.385,0:15:10.588
que k mais d aproxima e mais de N tão bem que

0:15:10.588,0:15:15.307
a diferença entre os dois é menor do que o quadrado do denominador de k ao longo d.

0:15:15.307,0:15:17.324
Acontece que isso não pode acontecer muitas vezes.

0:15:17.324,0:15:22.338
Acontece que há muito poucas frações da forma k mais d que a fração de outra aproximada

0:15:22.338,0:15:26.422
tão bem que a sua diferença é inferior a 1 durante 2 d quadrado.

0:15:26.422,0:15:30.308
E, de facto, o número de tais fracções vai ser, no máximo, em N. logarítmica

0:15:30.308,0:15:33.953
Portanto, agora há um algoritmo de fração contínua. É uma fração muito famoso

0:15:33.953,0:15:38.877
que, basicamente, o que ele vai fazer é, a partir do e fração sobre N,

0:15:38.877,0:15:42.977
ele vai se recuperar de log (N) possíveis candidatos para k sobre d.

0:15:42.977,0:15:47.148
Então, nós apenas julgá-los todos, um por um até encontrar o k correto sobre d.

0:15:47.148,0:15:51.645
E, então, está feito. Estamos a fazer, porque sabemos que,

0:15:51.645,0:15:55.376
bem vezes e d é 1 k mod, portanto d é relativamente privilegiada para k,

0:15:55.376,0:16:00.852
por isso, se nós apenas representam k mais d como uma fração racional numerador, você sabe, por denominador,

0:16:00.852,0:16:05.271
o denominador deve ser d. E assim acabou recuperado, você sabe,

0:16:05.271,0:16:10.355
nós tentamos todos os possíveis log (N) e frações que mais aproximado N tão bem

0:16:10.355,0:16:13.688
que a diferença é inferior a 1 durante 2 d quadrado.

0:16:13.688,0:16:19.338
E, então, basta olhar para o denominador de todas as frações, e um dos denominadores deve ser d.

0:16:19.338,0:16:22.841
E, então, está feito; acabamos recuperou a chave privada.

0:16:22.841,0:16:26.341
Portanto, este é um ataque muito bonito. E mostra, basicamente, como,

0:16:26.341,0:16:31.267
se o expoente privado é pequeno, menor do que a quarta raiz de N,

0:16:31.267,0:16:35.354
então podemos recuperar d completamente, com bastante facilidade. Ok, então eu vou parar por aqui.