WEBVTT

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

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

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

00:00:05.788 --> 00:00:08.104
inverter RSA sem saber o alçapão?

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

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

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

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

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

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

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

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.

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

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

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

00:00:46.832 --> 00:00:49.563
exige que o primeiro fator N. módulo

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

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

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

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

00:01:02.107 --> 00:01:04.699
usando o que é chamado de teorema restante chinês

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

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

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

00:01:12.848 --> 00:01:14.636
Mas factoring, o módulo de elasticidade, tanto quanto

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

00:01:16.761 --> 00:01:19.865
Mas uma pergunta natural é, é verdade que em

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

00:01:22.568 --> 00:01:25.707
fator de N modulo? Tanto quanto sabemos, o

00:01:25.707 --> 00:01:27.369
melhor algoritmo para calcular raízes e'th

00:01:27.369 --> 00:01:30.002
modulo N, requer fatoração de N.

00:01:30.002 --> 00:01:31.626
Mas, quem sabe, talvez haja um corte curto

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

00:01:33.771 --> 00:01:36.704
sem fatorar o módulo. Para mostrar que

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

00:01:38.808 --> 00:01:40.314
Isto é, temos de mostrar que,

00:01:40.314 --> 00:01:42.001
se eu te der um algoritmo eficiente para

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

00:01:43.872 --> 00:01:48.132
algoritmo eficiente pode ser transformado em um algoritmo de factoring.

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

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

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

00:01:57.314 --> 00:02:00.101
mais rápido do que o módulo de factoring.

00:02:00.101 --> 00:02:02.285
Se tivéssemos esse resultado, seria mostrar que

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

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

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

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

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

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.

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

00:02:25.971 --> 00:02:29.066
tal algoritmo pode fatorar o módulo N?

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

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

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

00:02:37.711 --> 00:02:40.696
então, de facto, que implica o factoring modulus.

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.

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

00:02:47.779 --> 00:02:52.913
que exigia que 'e' vezes d é 1 mod phi (N).

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

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).

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

00:03:06.125 --> 00:03:09.107
e deve ser privilegiada relativamente a phi (N).

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.

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.

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

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

00:03:28.221 --> 00:03:30.863
expoente 2 não é relativamente privilegiada para phi (N).

00:03:30.863 --> 00:03:33.174
que significa que, embora tenhamos uma redução

00:03:33.174 --> 00:03:35.263
de tomar a raiz quadrada de factoring,

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

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

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

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

00:03:48.976 --> 00:03:50.978
É realmente muito divertido pensar sobre essa questão.

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

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,

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

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

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.

00:04:09.402 --> 00:04:11.366
O que esta prova diz que é, basicamente, se você

00:04:11.366 --> 00:04:13.500
me dar uma redução de uma forma muito particular.

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

00:04:16.070 --> 00:04:18.509
(Eu não vou explicar o que isso significa aqui.)

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

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

00:04:26.055 --> 00:04:28.554
seria, na verdade, implica um algoritmo de factoring.

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

00:04:31.084 --> 00:04:33.637
uma redução na realidade não existe.

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

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

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

00:04:39.725 --> 00:04:42.857
não temos realmente considerado. Então, eu o faria

00:04:42.857 --> 00:04:44.339
incentivá-lo a pensar um pouco sobre isso

00:04:44.339 --> 00:04:46.235
pergunta. É realmente muito interessante.

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

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

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.

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

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

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

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

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

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

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

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

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

00:05:30.895 --> 00:05:34.265
que o algoritmo de exponenciação correu em tempo linear

00:05:34.265 --> 00:05:37.767
no tamanho de d. Tempo linear no log de d.

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

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.

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.

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.

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.

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

00:06:04.669 --> 00:06:07.533
Bem, eu descia de 2000 bits para 100 bits.

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

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.

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

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

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

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.

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

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.

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

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.

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

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

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

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

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

00:07:06.243 --> 00:07:08.176
mais complicada, que mostra que se d

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

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

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

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

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

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

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

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

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

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

00:07:45.218 --> 00:07:48.077
seu objetivo é recuperar a chave secreta d.

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

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

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

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

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

00:08:04.340 --> 00:08:06.163
é uma espécie de um problema divertido para trabalhar.

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

00:08:10.101 --> 00:08:12.475
para melhorar o desempenho da RSA, e de facto

00:08:12.475 --> 00:08:15.276
agora há uma série de resultados como este que mostram

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

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.

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

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.

00:08:31.582 --> 00:08:35.229
Tudo o que envolve é apenas manipular algumas desigualdades.

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

00:08:37.743 --> 00:08:40.979
embora eu acho que muitos de vocês realmente gostam de ver os detalhes.

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

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

00:08:46.893 --> 00:08:50.513
e nosso objetivo é recuperar d, o expoente privado d,

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

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.

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.

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

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

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

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.

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

00:09:26.280 --> 00:09:29.832
Basicamente múltipla algum inteiro de phi (N) mais 1.

00:09:29.832 --> 00:09:32.592
Então agora vamos olhar para esta equação um pouco.

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

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).

00:09:40.352 --> 00:09:43.703
E na verdade eu vou mover este termo aqui para a esquerda.

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

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).

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

00:10:02.902 --> 00:10:05.850
e mudei o k vezes phi prazo (N) para o lado esquerdo.

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

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.

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

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

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

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,

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.

00:10:35.638 --> 00:10:37.939
Agora vamos olhar para essa fração por apenas um minuto.

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.

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).

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)

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.

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

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

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

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

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.

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

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

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

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,

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

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

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,

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,

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.

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

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

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

00:12:02.958 --> 00:12:05.543
d for inferior a quarta raiz de N dividido por 3.

00:12:05.543 --> 00:12:08.596
É realmente bastante fácil de ver que se eu quadrado ambos os lados

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

00:12:12.118 --> 00:12:15.510
isso implica diretamente a seguinte relação,

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.

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

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

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.

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

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

00:12:45.059 --> 00:12:47.872
Pela desigualdade triangular, sabemos que isso é igual a

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

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

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

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

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

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.

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)?

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

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

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

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.

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.

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

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.

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.

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

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

00:14:03.655 --> 00:14:09.237
3 raiz quadrada de N sobre N é simplesmente 3 sobre raiz quadrada de N.

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

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.

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

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.

00:14:26.439 --> 00:14:29.509
O segundo valor absoluto for inferior a 1 sobre raiz quadrada de N.

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

00:14:34.369 --> 00:14:36.576
E esta é a expressão que eu quero que você olhar.

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.

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

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,

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

00:14:54.825 --> 00:14:56.862
Mas o que sabemos sobre este k fração sobre d?

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;

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

00:15:05.385 --> 00:15:10.588
que k mais d aproxima e mais de N tão bem que

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.

00:15:15.307 --> 00:15:17.324
Acontece que isso não pode acontecer muitas vezes.

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

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

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

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

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

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

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.

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

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

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,

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

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

00:16:10.355 --> 00:16:13.688
que a diferença é inferior a 1 durante 2 d quadrado.

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.

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

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

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

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.