[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,,A questão seguinte, vamos pedir
Dialogue: 0,0:00:01.70,0:00:03.64,Default,,0000,0000,0000,,RSA é realmente uma função one-way?
Dialogue: 0,0:00:03.64,0:00:05.79,Default,,0000,0000,0000,,Em outras palavras, é realmente difícil
Dialogue: 0,0:00:05.79,0:00:08.10,Default,,0000,0000,0000,,inverter RSA sem saber o alçapão?
Dialogue: 0,0:00:09.01,0:00:11.100,Default,,0000,0000,0000,,Assim, se um atacante queria inverter a função RSA,
Dialogue: 0,0:00:11.100,0:00:15.00,Default,,0000,0000,0000,,bem, o que o atacante tem, é basicamente a chave pública,
Dialogue: 0,0:00:15.00,0:00:19.05,Default,,0000,0000,0000,,a saber, que tem N e e. E agora, ele é dado x para o e-
Dialogue: 0,0:00:19.05,0:00:23.29,Default,,0000,0000,0000,,e seu objetivo é recuperar x. OK, então a questão realmente é:
Dialogue: 0,0:00:23.29,0:00:26.13,Default,,0000,0000,0000,,dado x para o módulo e N, como é que é difícil
Dialogue: 0,0:00:26.13,0:00:28.93,Default,,0000,0000,0000,,recuperar x? Então, o que estamos realmente fazendo é,
Dialogue: 0,0:00:28.93,0:00:33.11,Default,,0000,0000,0000,,como é que é difícil calcular e'th raízes módulo um composto?
Dialogue: 0,0:00:34.18,0:00:38.54,Default,,0000,0000,0000,,Se este problema acaba por ser difícil, então RSA é de fato uma função de mão única.
Dialogue: 0,0:00:38.54,0:00:39.97,Default,,0000,0000,0000,,Se este problema torna-se mais fácil, que
Dialogue: 0,0:00:39.97,0:00:44.56,Default,,0000,0000,0000,,é claro que não acredito que seja fácil, então RSA seria realmente quebrado.
Dialogue: 0,0:00:44.56,0:00:46.83,Default,,0000,0000,0000,,Assim, verifica-se o melhor algoritmo para este problema
Dialogue: 0,0:00:46.83,0:00:49.56,Default,,0000,0000,0000,,exige que o primeiro fator N. módulo
Dialogue: 0,0:00:50.05,0:00:52.24,Default,,0000,0000,0000,,E então, uma vez que o módulo consignado, já temos
Dialogue: 0,0:00:52.24,0:00:55.89,Default,,0000,0000,0000,,visto na semana passada, que é fácil de calcular a raiz e'th módulo p,
Dialogue: 0,0:00:55.89,0:00:58.48,Default,,0000,0000,0000,,é fácil de calcular a raiz e'th módulo q.
Dialogue: 0,0:00:58.48,0:01:02.11,Default,,0000,0000,0000,,E, então, dado ambas as raízes e'th, é realmente fácil de combiná-los,
Dialogue: 0,0:01:02.11,0:01:04.70,Default,,0000,0000,0000,,usando o que é chamado de teorema restante chinês
Dialogue: 0,0:01:04.70,0:01:07.67,Default,,0000,0000,0000,,e, na verdade, recuperar a raiz e'th modulo N.
Dialogue: 0,0:01:07.67,0:01:09.95,Default,,0000,0000,0000,,Assim, uma vez que somos capazes de fatorar o módulo,
Dialogue: 0,0:01:09.95,0:01:12.85,Default,,0000,0000,0000,,computação e'th raízes modulo N se torna fácil.
Dialogue: 0,0:01:12.85,0:01:14.64,Default,,0000,0000,0000,,Mas factoring, o módulo de elasticidade, tanto quanto
Dialogue: 0,0:01:14.64,0:01:16.76,Default,,0000,0000,0000,,Nós sabemos, é um problema muito, muito difícil.
Dialogue: 0,0:01:16.76,0:01:19.86,Default,,0000,0000,0000,,Mas uma pergunta natural é, é verdade que em
Dialogue: 0,0:01:19.86,0:01:22.57,Default,,0000,0000,0000,,Para calcular e'th raízes módulo N, temos que
Dialogue: 0,0:01:22.57,0:01:25.71,Default,,0000,0000,0000,,fator de N modulo? Tanto quanto sabemos, o
Dialogue: 0,0:01:25.71,0:01:27.37,Default,,0000,0000,0000,,melhor algoritmo para calcular raízes e'th
Dialogue: 0,0:01:27.37,0:01:30.00,Default,,0000,0000,0000,,modulo N, requer fatoração de N.
Dialogue: 0,0:01:30.00,0:01:31.63,Default,,0000,0000,0000,,Mas, quem sabe, talvez haja um corte curto
Dialogue: 0,0:01:31.63,0:01:33.77,Default,,0000,0000,0000,,que nos permitem calcular e'th raízes modulo N,
Dialogue: 0,0:01:33.77,0:01:36.70,Default,,0000,0000,0000,,sem fatorar o módulo. Para mostrar que
Dialogue: 0,0:01:36.70,0:01:38.81,Default,,0000,0000,0000,,isso não é possível, temos que mostrar uma redução.
Dialogue: 0,0:01:38.81,0:01:40.31,Default,,0000,0000,0000,,Isto é, temos de mostrar que,
Dialogue: 0,0:01:40.31,0:01:42.00,Default,,0000,0000,0000,,se eu te der um algoritmo eficiente para
Dialogue: 0,0:01:42.00,0:01:43.87,Default,,0000,0000,0000,,computação e'th raízes modulo N, que
Dialogue: 0,0:01:43.87,0:01:48.13,Default,,0000,0000,0000,,algoritmo eficiente pode ser transformado em um algoritmo de factoring.
Dialogue: 0,0:01:48.13,0:01:51.02,Default,,0000,0000,0000,,Então, isso é chamado de redução. Ou seja, tendo em conta um algoritmo para
Dialogue: 0,0:01:51.02,0:01:53.14,Default,,0000,0000,0000,,e'th raízes módulo N, obtemos um algoritmo de factoring.
Dialogue: 0,0:01:53.14,0:01:57.31,Default,,0000,0000,0000,,Isso mostra que não se pode calcular e'th raízes modulo N
Dialogue: 0,0:01:57.31,0:02:00.10,Default,,0000,0000,0000,,mais rápido do que o módulo de factoring.
Dialogue: 0,0:02:00.10,0:02:02.28,Default,,0000,0000,0000,,Se tivéssemos esse resultado, seria mostrar que
Dialogue: 0,0:02:02.28,0:02:05.72,Default,,0000,0000,0000,,realmente quebrar RSA, na verdade é tão difícil como fatorar
Dialogue: 0,0:02:05.72,0:02:08.11,Default,,0000,0000,0000,,Mas, infelizmente, isso não é muito conhecido no momento.
Dialogue: 0,0:02:08.11,0:02:11.97,Default,,0000,0000,0000,,Na verdade, este é um dos mais antigos problemas de chave pública de criptografia.
Dialogue: 0,0:02:11.97,0:02:14.42,Default,,0000,0000,0000,,Então, deixe-me dar-lhe um exemplo concreto.
Dialogue: 0,0:02:14.42,0:02:18.52,Default,,0000,0000,0000,,Suponha-se, eu dou-lhe um algoritmo que irá calcular cubo raízes módulo N.
Dialogue: 0,0:02:19.04,0:02:23.69,Default,,0000,0000,0000,,Assim, para qualquer x em ZN, o algoritmo irá calcular a raiz cúbica de x modulo N.
Dialogue: 0,0:02:23.69,0:02:25.97,Default,,0000,0000,0000,,Minha pergunta é, você pode mostrar que o uso de
Dialogue: 0,0:02:25.97,0:02:29.07,Default,,0000,0000,0000,,tal algoritmo pode fatorar o módulo N?
Dialogue: 0,0:02:29.07,0:02:31.24,Default,,0000,0000,0000,,E, mesmo que não seja conhecido. O que é conhecido,
Dialogue: 0,0:02:31.24,0:02:33.92,Default,,0000,0000,0000,,eu vos digo, é por exemplo, que para e igual a 2,
Dialogue: 0,0:02:34.38,0:02:37.71,Default,,0000,0000,0000,,isto é, se eu te dou um algoritmo para calcular raízes quadrada módulo N,
Dialogue: 0,0:02:37.71,0:02:40.70,Default,,0000,0000,0000,,então, de facto, que implica o factoring modulus.
Dialogue: 0,0:02:40.70,0:02:44.70,Default,,0000,0000,0000,,Assim, o cálculo de raízes quadradas é de fato tão duro como o módulo de factoring.
Dialogue: 0,0:02:44.71,0:02:47.78,Default,,0000,0000,0000,,Infelizmente, se você acha que volta para a definição de RSA,
Dialogue: 0,0:02:47.78,0:02:52.91,Default,,0000,0000,0000,,que exigia que 'e' vezes d é 1 mod phi (N).
Dialogue: 0,0:02:52.91,0:02:58.61,Default,,0000,0000,0000,,O que isto significa é que, e necessariamente tem de ser relativamente privilegiada para phi (N).
Dialogue: 0,0:02:58.61,0:03:03.13,Default,,0000,0000,0000,,Certo, isso, o que a primeira equação diz é que o e é inversível módulo phi (N).
Dialogue: 0,0:03:03.13,0:03:06.12,Default,,0000,0000,0000,,Mas, se e é invertível módulo phi (N), o que significa, necessariamente, que
Dialogue: 0,0:03:06.12,0:03:09.11,Default,,0000,0000,0000,,e deve ser privilegiada relativamente a phi (N).
Dialogue: 0,0:03:09.11,0:03:13.93,Default,,0000,0000,0000,,Mas, phi (N), se você se lembra, que é igual a menos um p vezes q menos 1.
Dialogue: 0,0:03:13.93,0:03:19.38,Default,,0000,0000,0000,,E, uma vez que p e q são ambos números primos grandes, p - 1 vezes q - 1 é sempre igual.
Dialogue: 0,0:03:19.38,0:03:25.50,Default,,0000,0000,0000,,E, como resultado, o GCD de 2 e phi (N) é igual a 2,
Dialogue: 0,0:03:25.50,0:03:28.22,Default,,0000,0000,0000,,porque phi (N) é mesmo. E, portanto, o público
Dialogue: 0,0:03:28.22,0:03:30.86,Default,,0000,0000,0000,,expoente 2 não é relativamente privilegiada para phi (N).
Dialogue: 0,0:03:30.86,0:03:33.17,Default,,0000,0000,0000,,que significa que, embora tenhamos uma redução
Dialogue: 0,0:03:33.17,0:03:35.26,Default,,0000,0000,0000,,de tomar a raiz quadrada de factoring,
Dialogue: 0,0:03:35.26,0:03:38.76,Default,,0000,0000,0000,,e não é igual a 2 pode ser utilizado como um expoente RSA.
Dialogue: 0,0:03:38.76,0:03:43.64,Default,,0000,0000,0000,,Então, realmente o menor expoente RSA que é legal é, de facto, e é igual a 3.
Dialogue: 0,0:03:43.64,0:03:46.91,Default,,0000,0000,0000,,Mas, para o e igual 3, a questão de se raízes cúbicas de computação
Dialogue: 0,0:03:46.91,0:03:48.98,Default,,0000,0000,0000,,é tão duro como factoring, é um problema em aberto.
Dialogue: 0,0:03:48.98,0:03:50.98,Default,,0000,0000,0000,,É realmente muito divertido pensar sobre essa questão.
Dialogue: 0,0:03:50.98,0:03:53.44,Default,,0000,0000,0000,,Portanto, gostaria de incentivá-lo a pensar sobre isso um pouco.
Dialogue: 0,0:03:53.44,0:03:58.35,Default,,0000,0000,0000,,Isto é, se eu lhe der um algoritmo eficiente para a computação cubo raízes módulo N,
Dialogue: 0,0:03:58.35,0:04:02.11,Default,,0000,0000,0000,,você pode usar esse algoritmo para realmente fatorar o módulo N?
Dialogue: 0,0:04:02.11,0:04:05.30,Default,,0000,0000,0000,,Vou dizer-lhe que há um pouco de evidência para dizer
Dialogue: 0,0:04:05.30,0:04:09.40,Default,,0000,0000,0000,,que uma redução como essa, na verdade não existe, mas é uma evidência muito, muito fraco.
Dialogue: 0,0:04:09.40,0:04:11.37,Default,,0000,0000,0000,,O que esta prova diz que é, basicamente, se você
Dialogue: 0,0:04:11.37,0:04:13.50,Default,,0000,0000,0000,,me dar uma redução de uma forma muito particular.
Dialogue: 0,0:04:13.50,0:04:16.07,Default,,0000,0000,0000,,Em outras palavras, se a sua redução é o que é chamado algébrica,
Dialogue: 0,0:04:16.07,0:04:18.51,Default,,0000,0000,0000,,(Eu não vou explicar o que isso significa aqui.)
Dialogue: 0,0:04:18.51,0:04:23.09,Default,,0000,0000,0000,,Isto é, se for dado um cubo raiz oráculo, você realmente pode me mostrar um algoritmo
Dialogue: 0,0:04:23.09,0:04:26.06,Default,,0000,0000,0000,,que, então, fator. Essa redução, por si só,
Dialogue: 0,0:04:26.06,0:04:28.55,Default,,0000,0000,0000,,seria, na verdade, implica um algoritmo de factoring.
Dialogue: 0,0:04:28.55,0:04:31.08,Default,,0000,0000,0000,,Ok então, que dizer que se factoring é difícil,
Dialogue: 0,0:04:31.08,0:04:33.64,Default,,0000,0000,0000,,uma redução na realidade não existe.
Dialogue: 0,0:04:33.64,0:04:35.54,Default,,0000,0000,0000,,Mas, como eu digo isso é uma evidência muito fraca.
Dialogue: 0,0:04:35.54,0:04:37.62,Default,,0000,0000,0000,,Porque, que é dizer que a redução deve ser algébrico.
Dialogue: 0,0:04:37.62,0:04:39.72,Default,,0000,0000,0000,,Talvez, há alguns outros tipos de reduções que
Dialogue: 0,0:04:39.72,0:04:42.86,Default,,0000,0000,0000,,não temos realmente considerado. Então, eu o faria
Dialogue: 0,0:04:42.86,0:04:44.34,Default,,0000,0000,0000,,incentivá-lo a pensar um pouco sobre isso
Dialogue: 0,0:04:44.34,0:04:46.24,Default,,0000,0000,0000,,pergunta. É realmente muito interessante.
Dialogue: 0,0:04:46.24,0:04:50.09,Default,,0000,0000,0000,,Como você usaria um algoritmo de raiz cúbica de fatorar o módulo?
Dialogue: 0,0:04:51.31,0:04:54.14,Default,,0000,0000,0000,,Mas como eu disse, tanto quanto sabemos, a RSA é uma função de uma maneira.
Dialogue: 0,0:04:54.14,0:05:00.27,Default,,0000,0000,0000,,Na verdade, quebrando RSA, computando raízes e'th que é, na verdade, requer módulo de factoring o.
Dialogue: 0,0:05:00.27,0:05:02.92,Default,,0000,0000,0000,,Nós todos acreditamos que é verdade, e isso é o estado da arte.
Dialogue: 0,0:05:02.92,0:05:07.64,Default,,0000,0000,0000,,Mas, agora, tem havido muito trabalho para tentar melhorar o desempenho da RSA.
Dialogue: 0,0:05:07.64,0:05:12.04,Default,,0000,0000,0000,,Ou criptografia, RSA ou melhorar o desempenho de decodificação RSA.
Dialogue: 0,0:05:12.04,0:05:14.90,Default,,0000,0000,0000,,E ao que parece, tem havido uma série de falsos começos nesta direção.
Dialogue: 0,0:05:14.90,0:05:18.80,Default,,0000,0000,0000,,Então, eu quero te mostrar, este maravilhoso exemplo como um aviso.
Dialogue: 0,0:05:18.80,0:05:23.23,Default,,0000,0000,0000,,Então, basicamente, este é um exemplo de como não se melhorar a perfomance da RSA.
Dialogue: 0,0:05:23.23,0:05:26.77,Default,,0000,0000,0000,,Assim, você pode pensar que se eu quisesse acelerar descriptografia RSA,
Dialogue: 0,0:05:26.77,0:05:28.58,Default,,0000,0000,0000,,lembre-se de decodificação é feita através do aumento da
Dialogue: 0,0:05:28.58,0:05:30.90,Default,,0000,0000,0000,,cifrada com a potência de d. E, lembre-se
Dialogue: 0,0:05:30.90,0:05:34.26,Default,,0000,0000,0000,,que o algoritmo de exponenciação correu em tempo linear
Dialogue: 0,0:05:34.26,0:05:37.77,Default,,0000,0000,0000,,no tamanho de d. Tempo linear no log de d.
Dialogue: 0,0:05:37.77,0:05:39.76,Default,,0000,0000,0000,,Assim, você pode pensar a si mesmo, bem, se eu queria
Dialogue: 0,0:05:39.76,0:05:43.52,Default,,0000,0000,0000,,para acelerar a decodificação RSA, por que não eu só uso um d minúsculo.
Dialogue: 0,0:05:43.52,0:05:48.26,Default,,0000,0000,0000,,Eu vou dizer, eu vou dizer um expoente de decodificação que é da ordem de 2 a 128.
Dialogue: 0,0:05:48.42,0:05:52.35,Default,,0000,0000,0000,,Então é claramente grande o suficiente para que a pesquisa exaustiva contra d não é possível.
Dialogue: 0,0:05:52.35,0:05:57.42,Default,,0000,0000,0000,,Mas, normalmente, a descriptografia expoente d seria tão grande como o módulo, digamos 2000 bits.
Dialogue: 0,0:05:57.42,0:06:04.67,Default,,0000,0000,0000,,Usando d que é apenas 128 bits, eu basicamente acelerar descriptografia RSA por um fator de 20.
Dialogue: 0,0:06:04.67,0:06:07.53,Default,,0000,0000,0000,,Bem, eu descia de 2000 bits para 100 bits.
Dialogue: 0,0:06:07.53,0:06:10.92,Default,,0000,0000,0000,,Assim, a exponenciação seria executado 20 vezes mais rápido.
Dialogue: 0,0:06:10.92,0:06:15.44,Default,,0000,0000,0000,,Acontece que isso é uma péssima idéia. Idéia terrível, terrível, no seguinte sentido.
Dialogue: 0,0:06:15.44,0:06:18.64,Default,,0000,0000,0000,,Há um ataque por Michael Wiener, que mostra que, de facto,
Dialogue: 0,0:06:18.64,0:06:23.42,Default,,0000,0000,0000,,assim que o expoente privado d é menor do que a quarta raiz do módulo.
Dialogue: 0,0:06:23.42,0:06:27.53,Default,,0000,0000,0000,,Vamos ver, se o módulo é de cerca de 2048 bits
Dialogue: 0,0:06:27.53,0:06:34.58,Default,,0000,0000,0000,,o que significa que, se d for menor que 2 a 512, em seguida, A RSA é completamente, completamente inseguro.
Dialogue: 0,0:06:34.58,0:06:37.51,Default,,0000,0000,0000,,E, isto é, ele é inseguro da pior forma possível.
Dialogue: 0,0:06:37.51,0:06:43.13,Default,,0000,0000,0000,,Ou seja, apenas dei uma chave pública e um e, você pode rapidamente recuperar a chave privada d.
Dialogue: 0,0:06:44.23,0:06:48.49,Default,,0000,0000,0000,,Bem, para algumas pessoas, disse: bem, este ataque funciona até 512 bits.
Dialogue: 0,0:06:48.49,0:06:52.38,Default,,0000,0000,0000,,Então, por que donÂ't fazemos o módulo, por exemplo, você sabe que 530 bits.
Dialogue: 0,0:06:52.38,0:06:54.23,Default,,0000,0000,0000,,Então, este ataque realmente não seria aplicável.
Dialogue: 0,0:06:54.23,0:06:57.54,Default,,0000,0000,0000,,Mas, ainda assim, temos de acelerar descriptografia RSA por um fator de 4,
Dialogue: 0,0:06:57.54,0:07:01.100,Default,,0000,0000,0000,,porque diminuiu o expoente de 2000 bits para, digamos, 530 bits.
Dialogue: 0,0:07:01.100,0:07:03.98,Default,,0000,0000,0000,,Bem se vê, mesmo que não seja seguro. Na verdade,
Dialogue: 0,0:07:03.98,0:07:06.24,Default,,0000,0000,0000,,existe uma extensão ao ataque de Wiener, que é realmente muito
Dialogue: 0,0:07:06.24,0:07:08.18,Default,,0000,0000,0000,,mais complicada, que mostra que se d
Dialogue: 0,0:07:08.18,0:07:13.23,Default,,0000,0000,0000,,é inferior a 0,292 N para o, então também RSA é inseguro.
Dialogue: 0,0:07:13.23,0:07:16.67,Default,,0000,0000,0000,,E, na verdade, a conjectura de que isto é verdadeiro se a N para o 0.5.
Dialogue: 0,0:07:16.67,0:07:21.98,Default,,0000,0000,0000,,Portanto, mesmo se d é como N para a 0,4999, RSA ainda deve ser inseguro,
Dialogue: 0,0:07:21.98,0:07:25.78,Default,,0000,0000,0000,,embora isso seja um problema em aberto. É, novamente, um problema maravilhoso aberto,
Dialogue: 0,0:07:25.78,0:07:28.39,Default,,0000,0000,0000,,Tem sido aberto para como, o que é, 14 anos.
Dialogue: 0,0:07:28.39,0:07:31.56,Default,,0000,0000,0000,,E, ninguém pode progredir para além desta 0,292.
Dialogue: 0,0:07:31.56,0:07:34.33,Default,,0000,0000,0000,,De alguma forma, parece meio estranho, por que 0,292
Dialogue: 0,0:07:34.33,0:07:38.22,Default,,0000,0000,0000,,ser a resposta certa e ainda ninguém pode ir além 0,292.
Dialogue: 0,0:07:38.80,0:07:41.67,Default,,0000,0000,0000,,Então, só para ser mais preciso, quando eu digo que a RSA é inseguro,
Dialogue: 0,0:07:41.67,0:07:45.22,Default,,0000,0000,0000,,o que eu quero dizer é dado apenas a chave pública N e E,
Dialogue: 0,0:07:45.22,0:07:48.08,Default,,0000,0000,0000,,seu objetivo é recuperar a chave secreta d.
Dialogue: 0,0:07:49.10,0:07:52.26,Default,,0000,0000,0000,,Se você está curioso, onde vem de 0,292,
Dialogue: 0,0:07:52.26,0:07:56.31,Default,,0000,0000,0000,,Eu vou te dizer que o que é, é basicamente um menos 1 sobre raiz quadrada de 2.
Dialogue: 0,0:07:56.31,0:07:58.50,Default,,0000,0000,0000,,Agora, como isso poderia ser a resposta certa para este problema?
Dialogue: 0,0:07:58.50,0:08:01.30,Default,,0000,0000,0000,,É muito mais natural que a resposta é N a 0,5.
Dialogue: 0,0:08:01.30,0:08:04.34,Default,,0000,0000,0000,,Mas isso ainda é um problema em aberto. Novamente, se você quer pensar sobre isso,
Dialogue: 0,0:08:04.34,0:08:06.16,Default,,0000,0000,0000,,é uma espécie de um problema divertido para trabalhar.
Dialogue: 0,0:08:06.16,0:08:10.10,Default,,0000,0000,0000,,Assim, a lição no presente é que não se deve impor qualquer estrutura em d
Dialogue: 0,0:08:10.10,0:08:12.48,Default,,0000,0000,0000,,para melhorar o desempenho da RSA, e de facto
Dialogue: 0,0:08:12.48,0:08:15.28,Default,,0000,0000,0000,,agora há uma série de resultados como este que mostram
Dialogue: 0,0:08:15.28,0:08:19.71,Default,,0000,0000,0000,,que, basicamente, qualquer tipo de truques como este para tentar melhorar o desempenho da RSA
Dialogue: 0,0:08:19.71,0:08:24.28,Default,,0000,0000,0000,,vai acabar em desastre. Portanto, este não é o caminho certo para melhorar o desempenho da RSA.
Dialogue: 0,0:08:24.28,0:08:27.99,Default,,0000,0000,0000,,Inicialmente eu não estava indo para cobrir os detalhes do ataque de Wiener.
Dialogue: 0,0:08:27.99,0:08:31.58,Default,,0000,0000,0000,,Mas dadas as discussões em classe, eu acho que alguns de vocês gostaria de ver os detalhes.
Dialogue: 0,0:08:31.58,0:08:35.23,Default,,0000,0000,0000,,Tudo o que envolve é apenas manipular algumas desigualdades.
Dialogue: 0,0:08:35.23,0:08:37.74,Default,,0000,0000,0000,,Se você não está confortável com isso, sinta-se livre para pular este slide,
Dialogue: 0,0:08:37.74,0:08:40.98,Default,,0000,0000,0000,,embora eu acho que muitos de vocês realmente gostam de ver os detalhes.
Dialogue: 0,0:08:40.98,0:08:43.36,Default,,0000,0000,0000,,Então deixe-me lembrá-lo no ataque Wiener basicamente
Dialogue: 0,0:08:43.36,0:08:46.89,Default,,0000,0000,0000,,nós estamos dando o módulo eo expoente RSA N e E,
Dialogue: 0,0:08:46.89,0:08:50.51,Default,,0000,0000,0000,,e nosso objetivo é recuperar d, o expoente privado d,
Dialogue: 0,0:08:50.51,0:08:54.17,Default,,0000,0000,0000,,e tudo o que sabemos é que d é basicamente menor do que a raiz quarta de N.
Dialogue: 0,0:08:54.17,0:08:57.71,Default,,0000,0000,0000,,Na verdade, eu vou assumir que d é menor do que a raiz quarta de N dividido por 3.
Dialogue: 0,0:08:57.71,0:09:02.37,Default,,0000,0000,0000,,Esta 3 realmente não importa, mas o termo dominante aqui é que d é menor do que a raiz quarta de N.
Dialogue: 0,0:09:02.37,0:09:05.94,Default,,0000,0000,0000,,Então vamos ver como fazê-lo. Então, primeiro de tudo, lembrar que
Dialogue: 0,0:09:05.94,0:09:09.14,Default,,0000,0000,0000,,porque e e d são RSA expoentes públicas e privadas,
Dialogue: 0,0:09:09.14,0:09:14.14,Default,,0000,0000,0000,,sabemos que e d vezes é um modulo phi (N). Bem, o que isso significa?
Dialogue: 0,0:09:14.14,0:09:22.25,Default,,0000,0000,0000,,Isto significa que existe algum inteiro k tal que e tempos d é igual a k vezes phi (N), acrescido de 1.
Dialogue: 0,0:09:22.25,0:09:26.28,Default,,0000,0000,0000,,Basicamente é o que significa para os tempos e d ser um modulo phi (N).
Dialogue: 0,0:09:26.28,0:09:29.83,Default,,0000,0000,0000,,Basicamente múltipla algum inteiro de phi (N) mais 1.
Dialogue: 0,0:09:29.83,0:09:32.59,Default,,0000,0000,0000,,Então agora vamos olhar para esta equação um pouco.
Dialogue: 0,0:09:32.59,0:09:35.83,Default,,0000,0000,0000,,E na verdade, esta equação é a equação-chave no ataque.
Dialogue: 0,0:09:35.83,0:09:40.35,Default,,0000,0000,0000,,E o que nós vamos fazer é antes de tudo dividir ambos os lados por d vezes phi (N).
Dialogue: 0,0:09:40.35,0:09:43.70,Default,,0000,0000,0000,,E na verdade eu vou mover este termo aqui para a esquerda.
Dialogue: 0,0:09:43.70,0:09:47.45,Default,,0000,0000,0000,,Então, depois que eu dividir por d vezes phi (N), o que eu vejo é que
Dialogue: 0,0:09:47.45,0:09:58.50,Default,,0000,0000,0000,,e dividido pelo phi (N) menos k dividido por d é igual a 1 ao longo d vezes phi (N).
Dialogue: 0,0:09:59.47,0:10:02.90,Default,,0000,0000,0000,,Ok, então tudo que eu fiz é que eu só dividido por d vezes phi (N)
Dialogue: 0,0:10:02.90,0:10:05.85,Default,,0000,0000,0000,,e mudei o k vezes phi prazo (N) para o lado esquerdo.
Dialogue: 0,0:10:05.85,0:10:09.12,Default,,0000,0000,0000,,Agora, apenas para os pedaços que eu estou indo para adicionar valores absolutos aqui.
Dialogue: 0,0:10:09.12,0:10:13.48,Default,,0000,0000,0000,,Estes irão tornar-se útil em apenas um minuto, mas é claro que eles não mudam essa igualdade em tudo.
Dialogue: 0,0:10:13.48,0:10:20.18,Default,,0000,0000,0000,,Agora, phi (N), claro, é quase N; phi (N) é muito, muito perto de N, como dissemos anteriormente.
Dialogue: 0,0:10:20.18,0:10:23.37,Default,,0000,0000,0000,,E tudo que eu vou precisar de então para essa fração é só para dizer que
Dialogue: 0,0:10:23.37,0:10:26.64,Default,,0000,0000,0000,,é inferior a 1 sobre raiz quadrada de N. Na verdade, é muito, muito menor
Dialogue: 0,0:10:26.64,0:10:30.57,Default,,0000,0000,0000,,do que 1 sobre raiz quadrada de N, na verdade é da ordem de 1 por N, ou até mais do que isso,
Dialogue: 0,0:10:30.57,0:10:35.64,Default,,0000,0000,0000,,mas para nossos propósitos tudo o que precisamos é que essa fração for inferior a 1 sobre raiz quadrada de N.
Dialogue: 0,0:10:35.64,0:10:37.94,Default,,0000,0000,0000,,Agora vamos olhar para essa fração por apenas um minuto.
Dialogue: 0,0:10:37.94,0:10:44.51,Default,,0000,0000,0000,,Você percebe que esta fração à esquerda aqui é uma fração que nós realmente não sabemos.
Dialogue: 0,0:10:44.51,0:10:49.04,Default,,0000,0000,0000,,Sabemos e, mas não sabemos phi (N), e, como resultado, não sabemos e sobre phi (N).
Dialogue: 0,0:10:49.04,0:10:53.63,Default,,0000,0000,0000,,Mas temos uma boa aproximação e mais de phi (N). Ou seja, sabemos que phi (N)
Dialogue: 0,0:10:53.63,0:10:59.24,Default,,0000,0000,0000,,está muito perto de N. Portanto, e mais de phi (N) está muito próximo e mais de N.
Dialogue: 0,0:10:59.24,0:11:03.44,Default,,0000,0000,0000,,Portanto, temos uma boa aproximação a esta fração lado esquerdo, e nomeadamente sobre N.
Dialogue: 0,0:11:03.44,0:11:06.03,Default,,0000,0000,0000,,O que realmente queremos é a fração lado direito,
Dialogue: 0,0:11:06.03,0:11:07.65,Default,,0000,0000,0000,,porque uma vez que temos a fração lado direito,
Dialogue: 0,0:11:07.65,0:11:12.96,Default,,0000,0000,0000,,basicamente, que vai envolver d, e então nós vamos ser capazes de recuperar d. Ok, então vamos ver
Dialogue: 0,0:11:12.96,0:11:19.04,Default,,0000,0000,0000,,se substituirmos e sobre phi (N) por e sobre N, vamos ver que tipo de erro que vamos conseguir.
Dialogue: 0,0:11:19.04,0:11:22.51,Default,,0000,0000,0000,,Assim, para analisar que, o que nós vamos fazer é, antes de tudo lembrar\NAssim, para analisar que, o que nós vamos fazer é, antes de tudo lembrar
Dialogue: 0,0:11:22.51,0:11:26.20,Default,,0000,0000,0000,,que phi (N) é basicamente N - p - q + 1,
Dialogue: 0,0:11:26.20,0:11:30.80,Default,,0000,0000,0000,,o que significa que menos phi N (N) vai ser menor do que p + q.
Dialogue: 0,0:11:30.80,0:11:34.75,Default,,0000,0000,0000,,Na verdade, eu deveria, para ser mais preciso, eu realmente deveria escrever p + q + 1, mas você sabe,
Dialogue: 0,0:11:34.75,0:11:37.84,Default,,0000,0000,0000,,que se preocupa com este 1, que não é, ele realmente não afeta nada.
Dialogue: 0,0:11:37.84,0:11:40.24,Default,,0000,0000,0000,,Então, eu estou indo só para ignorá-lo pela simplicidade.
Dialogue: 0,0:11:40.24,0:11:45.51,Default,,0000,0000,0000,,Ok, então N - phi (N) é menor que p + q. Ambos p e q são mais ou menos metade do comprimento de N,
Dialogue: 0,0:11:45.51,0:11:48.92,Default,,0000,0000,0000,,assim você sabe, eles são os dois tipos de da ordem de raiz quadrada de N,
Dialogue: 0,0:11:48.92,0:11:53.88,Default,,0000,0000,0000,,Então, basicamente p + q vamos dizer é menos do que 3 vezes a raiz quadrada de N.
Dialogue: 0,0:11:53.88,0:11:56.84,Default,,0000,0000,0000,,Ok, então vamos usar essa desigualdade em apenas um minuto.
Dialogue: 0,0:11:56.84,0:12:00.24,Default,,0000,0000,0000,,Mas agora vamos começar a usar o fato de que sabemos algo sobre d,
Dialogue: 0,0:12:00.24,0:12:02.96,Default,,0000,0000,0000,,a saber, que d é pequena. Então, se olharmos para esta desigualdade aqui,
Dialogue: 0,0:12:02.96,0:12:05.54,Default,,0000,0000,0000,,d for inferior a quarta raiz de N dividido por 3.
Dialogue: 0,0:12:05.54,0:12:08.60,Default,,0000,0000,0000,,É realmente bastante fácil de ver que se eu quadrado ambos os lados
Dialogue: 0,0:12:08.60,0:12:12.12,Default,,0000,0000,0000,,e eu só manipular as coisas um pouco, é [não] difícil ver que
Dialogue: 0,0:12:12.12,0:12:15.51,Default,,0000,0000,0000,,isso implica diretamente a seguinte relação,
Dialogue: 0,0:12:15.51,0:12:24.26,Default,,0000,0000,0000,,basicamente um mais de 2 d quadrado menos 1 sobre raiz quadrada de N é maior do que 3 sobre raiz quadrada de N.
Dialogue: 0,0:12:24.26,0:12:28.54,Default,,0000,0000,0000,,Como eu disse, este segue basicamente por quadratura ambos os lados, em seguida, tendo o
Dialogue: 0,0:12:28.54,0:12:33.33,Default,,0000,0000,0000,,inverso de ambos os lados, e então eu acho que multiplicando um lado pelo meio.
Dialogue: 0,0:12:33.33,0:12:37.91,Default,,0000,0000,0000,,Ok, então você pode facilmente obter essa relação, e vamos precisar essa relação em apenas um minuto.
Dialogue: 0,0:12:37.91,0:12:40.17,Default,,0000,0000,0000,,Então, agora vamos ver, o que gostaria de fazer é obrigado
Dialogue: 0,0:12:40.17,0:12:45.06,Default,,0000,0000,0000,,a diferença de e mais de N e K sobre d. Bem, o que sabemos?
Dialogue: 0,0:12:45.06,0:12:47.87,Default,,0000,0000,0000,,Pela desigualdade triangular, sabemos que isso é igual a
Dialogue: 0,0:12:47.87,0:12:52.12,Default,,0000,0000,0000,,a distância entre e ao longo e por cima e N phi (N), além
Dialogue: 0,0:12:52.12,0:12:56.57,Default,,0000,0000,0000,,a distância a partir de e ao longo phi (N) para k ao longo d.
Dialogue: 0,0:12:56.57,0:13:01.81,Default,,0000,0000,0000,,Este é apenas o que é chamado de uma desigualdade triangular, esta é apenas uma propriedade de valores absolutos.
Dialogue: 0,0:13:01.81,0:13:04.70,Default,,0000,0000,0000,,Agora, este valor absoluto aqui, nós já sabemos como vinculado.
Dialogue: 0,0:13:04.70,0:13:07.12,Default,,0000,0000,0000,,Se você pensar sobre isso é basicamente o limite que nós já derivada.
Dialogue: 0,0:13:07.12,0:13:11.98,Default,,0000,0000,0000,,Então, nós sabemos que este valor absoluto aqui é basicamente menor do que 1 sobre raiz quadrada de N.
Dialogue: 0,0:13:11.98,0:13:17.74,Default,,0000,0000,0000,,Agora, o que nós sabemos sobre esse valor absoluto aqui? O que é e mais N menos e mais de phi (N)?
Dialogue: 0,0:13:17.74,0:13:20.49,Default,,0000,0000,0000,,Bem, vamos fazer denominadores comuns e ver o que conseguimos.
Dialogue: 0,0:13:20.49,0:13:25.24,Default,,0000,0000,0000,,Assim, o denominador comum que vai ser N vezes phi (N),
Dialogue: 0,0:13:25.24,0:13:31.25,Default,,0000,0000,0000,,o numerador e, neste caso, vai ser vezes e phi (N) menos N.
Dialogue: 0,0:13:31.25,0:13:35.76,Default,,0000,0000,0000,,Que sabemos desta expressão aqui é menos do que três vezes a raiz quadrada de N.
Dialogue: 0,0:13:35.76,0:13:40.84,Default,,0000,0000,0000,,Então, realmente o que esta numerador vai ser é o e três vezes a raiz quadrada de N.
Dialogue: 0,0:13:40.84,0:13:44.33,Default,,0000,0000,0000,,O numerador vai ser menor do que e 3 vezes a raiz quadrada de N.
Dialogue: 0,0:13:44.33,0:13:51.25,Default,,0000,0000,0000,,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.
Dialogue: 0,0:13:51.25,0:13:57.31,Default,,0000,0000,0000,,Em outras palavras, se eu apagar e apagar e eu phi (N) Eu só fez a fração maior.
Dialogue: 0,0:13:57.31,0:14:00.02,Default,,0000,0000,0000,,Ok, então esse valor inicial absoluta é agora vai ser
Dialogue: 0,0:14:00.02,0:14:03.66,Default,,0000,0000,0000,,menor do que 3 raiz quadrada de N sobre N, que é simplesmente,
Dialogue: 0,0:14:03.66,0:14:09.24,Default,,0000,0000,0000,,3 raiz quadrada de N sobre N é simplesmente 3 sobre raiz quadrada de N.
Dialogue: 0,0:14:09.24,0:14:11.27,Default,,0000,0000,0000,,Ok, mas o que sabemos sobre a 3 sobre raiz quadrada de N?
Dialogue: 0,0:14:11.27,0:14:17.71,Default,,0000,0000,0000,,Nós sabemos que é menos de 1 por 2 d quadrado menos 1 sobre raiz quadrada de N.
Dialogue: 0,0:14:17.71,0:14:20.47,Default,,0000,0000,0000,,Ok, então esse é o fim da nossa derivação.
Dialogue: 0,0:14:20.47,0:14:26.44,Default,,0000,0000,0000,,Portanto, agora sabemos que o primeiro valor absoluto é menor do que 1 sobre 2 raiz d quadrado menos quadrado da N.
Dialogue: 0,0:14:26.44,0:14:29.51,Default,,0000,0000,0000,,O segundo valor absoluto for inferior a 1 sobre raiz quadrada de N.
Dialogue: 0,0:14:29.51,0:14:34.37,Default,,0000,0000,0000,,E, portanto, a soma é inferior a 1 sobre 2 d quadrado.
Dialogue: 0,0:14:34.37,0:14:36.58,Default,,0000,0000,0000,,E esta é a expressão que eu quero que você olhar.
Dialogue: 0,0:14:36.58,0:14:42.95,Default,,0000,0000,0000,,Então, aqui, deixe-me rodear-lo um pouco. Então deixe-me circular esta parte e esta parte.
Dialogue: 0,0:14:43.58,0:14:46.44,Default,,0000,0000,0000,,Agora, vamos olhar um pouco neste fração aqui.
Dialogue: 0,0:14:46.44,0:14:51.44,Default,,0000,0000,0000,,E o que vemos é, antes de tudo, como antes, agora sabemos o valor de e mais de N,
Dialogue: 0,0:14:51.44,0:14:54.82,Default,,0000,0000,0000,,eo que nós gostaríamos de saber é o valor k sobre d.
Dialogue: 0,0:14:54.82,0:14:56.86,Default,,0000,0000,0000,,Mas o que sabemos sobre este k fração sobre d?
Dialogue: 0,0:14:56.86,0:15:00.72,Default,,0000,0000,0000,,Nós sabemos de alguma forma que a diferença entre essas duas frações é muito pequeno;
Dialogue: 0,0:15:00.72,0:15:05.38,Default,,0000,0000,0000,,é inferior a 1 sobre 2 d quadrado. Agora, isso acaba por acontecer muito raramente,
Dialogue: 0,0:15:05.38,0:15:10.59,Default,,0000,0000,0000,,que k mais d aproxima e mais de N tão bem que
Dialogue: 0,0:15:10.59,0:15:15.31,Default,,0000,0000,0000,,a diferença entre os dois é menor do que o quadrado do denominador de k ao longo d.
Dialogue: 0,0:15:15.31,0:15:17.32,Default,,0000,0000,0000,,Acontece que isso não pode acontecer muitas vezes.
Dialogue: 0,0:15:17.32,0:15:22.34,Default,,0000,0000,0000,,Acontece que há muito poucas frações da forma k mais d que a fração de outra aproximada
Dialogue: 0,0:15:22.34,0:15:26.42,Default,,0000,0000,0000,,tão bem que a sua diferença é inferior a 1 durante 2 d quadrado.
Dialogue: 0,0:15:26.42,0:15:30.31,Default,,0000,0000,0000,,E, de facto, o número de tais fracções vai ser, no máximo, em N. logarítmica
Dialogue: 0,0:15:30.31,0:15:33.95,Default,,0000,0000,0000,,Portanto, agora há um algoritmo de fração contínua. É uma fração muito famoso
Dialogue: 0,0:15:33.95,0:15:38.88,Default,,0000,0000,0000,,que, basicamente, o que ele vai fazer é, a partir do e fração sobre N,
Dialogue: 0,0:15:38.88,0:15:42.98,Default,,0000,0000,0000,,ele vai se recuperar de log (N) possíveis candidatos para k sobre d.
Dialogue: 0,0:15:42.98,0:15:47.15,Default,,0000,0000,0000,,Então, nós apenas julgá-los todos, um por um até encontrar o k correto sobre d.
Dialogue: 0,0:15:47.15,0:15:51.64,Default,,0000,0000,0000,,E, então, está feito. Estamos a fazer, porque sabemos que,
Dialogue: 0,0:15:51.64,0:15:55.38,Default,,0000,0000,0000,,bem vezes e d é 1 k mod, portanto d é relativamente privilegiada para k,
Dialogue: 0,0:15:55.38,0:16:00.85,Default,,0000,0000,0000,,por isso, se nós apenas representam k mais d como uma fração racional numerador, você sabe, por denominador,
Dialogue: 0,0:16:00.85,0:16:05.27,Default,,0000,0000,0000,,o denominador deve ser d. E assim acabou recuperado, você sabe,
Dialogue: 0,0:16:05.27,0:16:10.36,Default,,0000,0000,0000,,nós tentamos todos os possíveis log (N) e frações que mais aproximado N tão bem
Dialogue: 0,0:16:10.36,0:16:13.69,Default,,0000,0000,0000,,que a diferença é inferior a 1 durante 2 d quadrado.
Dialogue: 0,0:16:13.69,0:16:19.34,Default,,0000,0000,0000,,E, então, basta olhar para o denominador de todas as frações, e um dos denominadores deve ser d.
Dialogue: 0,0:16:19.34,0:16:22.84,Default,,0000,0000,0000,,E, então, está feito; acabamos recuperou a chave privada.
Dialogue: 0,0:16:22.84,0:16:26.34,Default,,0000,0000,0000,,Portanto, este é um ataque muito bonito. E mostra, basicamente, como,
Dialogue: 0,0:16:26.34,0:16:31.27,Default,,0000,0000,0000,,se o expoente privado é pequeno, menor do que a quarta raiz de N,
Dialogue: 0,0:16:31.27,0:16:35.35,Default,,0000,0000,0000,,então podemos recuperar d completamente, com bastante facilidade. Ok, então eu vou parar por aqui.