-
A questão seguinte, vamos pedir
-
RSA é realmente uma função one-way?
-
Em outras palavras, é realmente difícil
-
inverter RSA sem saber o alçapão?
-
Assim, se um atacante queria inverter a função RSA,
-
bem, o que o atacante tem, é basicamente a chave pública,
-
a saber, que tem N e e. E agora, ele é dado x para o e-
-
e seu objetivo é recuperar x. OK, então a questão realmente é:
-
dado x para o módulo e N, como é que é difícil
-
recuperar x? Então, o que estamos realmente fazendo é,
-
como é que é difícil calcular e'th raízes módulo um composto?
-
Se este problema acaba por ser difícil, então RSA é de fato uma função de mão única.
-
Se este problema torna-se mais fácil, que
-
é claro que não acredito que seja fácil, então RSA seria realmente quebrado.
-
Assim, verifica-se o melhor algoritmo para este problema
-
exige que o primeiro fator N. módulo
-
E então, uma vez que o módulo consignado, já temos
-
visto na semana passada, que é fácil de calcular a raiz e'th módulo p,
-
é fácil de calcular a raiz e'th módulo q.
-
E, então, dado ambas as raízes e'th, é realmente fácil de combiná-los,
-
usando o que é chamado de teorema restante chinês
-
e, na verdade, recuperar a raiz e'th modulo N.
-
Assim, uma vez que somos capazes de fatorar o módulo,
-
computação e'th raízes modulo N se torna fácil.
-
Mas factoring, o módulo de elasticidade, tanto quanto
-
Nós sabemos, é um problema muito, muito difícil.
-
Mas uma pergunta natural é, é verdade que em
-
Para calcular e'th raízes módulo N, temos que
-
fator de N modulo? Tanto quanto sabemos, o
-
melhor algoritmo para calcular raízes e'th
-
modulo N, requer fatoração de N.
-
Mas, quem sabe, talvez haja um corte curto
-
que nos permitem calcular e'th raízes modulo N,
-
sem fatorar o módulo. Para mostrar que
-
isso não é possível, temos que mostrar uma redução.
-
Isto é, temos de mostrar que,
-
se eu te der um algoritmo eficiente para
-
computação e'th raízes modulo N, que
-
algoritmo eficiente pode ser transformado em um algoritmo de factoring.
-
Então, isso é chamado de redução. Ou seja, tendo em conta um algoritmo para
-
e'th raízes módulo N, obtemos um algoritmo de factoring.
-
Isso mostra que não se pode calcular e'th raízes modulo N
-
mais rápido do que o módulo de factoring.
-
Se tivéssemos esse resultado, seria mostrar que
-
realmente quebrar RSA, na verdade é tão difícil como fatorar
-
Mas, infelizmente, isso não é muito conhecido no momento.
-
Na verdade, este é um dos mais antigos problemas de chave pública de criptografia.
-
Então, deixe-me dar-lhe um exemplo concreto.
-
Suponha-se, eu dou-lhe um algoritmo que irá calcular cubo raízes módulo N.
-
Assim, para qualquer x em ZN, o algoritmo irá calcular a raiz cúbica de x modulo N.
-
Minha pergunta é, você pode mostrar que o uso de
-
tal algoritmo pode fatorar o módulo N?
-
E, mesmo que não seja conhecido. O que é conhecido,
-
eu vos digo, é por exemplo, que para e igual a 2,
-
isto é, se eu te dou um algoritmo para calcular raízes quadrada módulo N,
-
então, de facto, que implica o factoring modulus.
-
Assim, o cálculo de raízes quadradas é de fato tão duro como o módulo de factoring.
-
Infelizmente, se você acha que volta para a definição de RSA,
-
que exigia que 'e' vezes d é 1 mod phi (N).
-
O que isto significa é que, e necessariamente tem de ser relativamente privilegiada para phi (N).
-
Certo, isso, o que a primeira equação diz é que o e é inversível módulo phi (N).
-
Mas, se e é invertível módulo phi (N), o que significa, necessariamente, que
-
e deve ser privilegiada relativamente a phi (N).
-
Mas, phi (N), se você se lembra, que é igual a menos um p vezes q menos 1.
-
E, uma vez que p e q são ambos números primos grandes, p - 1 vezes q - 1 é sempre igual.
-
E, como resultado, o GCD de 2 e phi (N) é igual a 2,
-
porque phi (N) é mesmo. E, portanto, o público
-
expoente 2 não é relativamente privilegiada para phi (N).
-
que significa que, embora tenhamos uma redução
-
de tomar a raiz quadrada de factoring,
-
e não é igual a 2 pode ser utilizado como um expoente RSA.
-
Então, realmente o menor expoente RSA que é legal é, de facto, e é igual a 3.
-
Mas, para o e igual 3, a questão de se raízes cúbicas de computação
-
é tão duro como factoring, é um problema em aberto.
-
É realmente muito divertido pensar sobre essa questão.
-
Portanto, gostaria de incentivá-lo a pensar sobre isso um pouco.
-
Isto é, se eu lhe der um algoritmo eficiente para a computação cubo raízes módulo N,
-
você pode usar esse algoritmo para realmente fatorar o módulo N?
-
Vou dizer-lhe que há um pouco de evidência para dizer
-
que uma redução como essa, na verdade não existe, mas é uma evidência muito, muito fraco.
-
O que esta prova diz que é, basicamente, se você
-
me dar uma redução de uma forma muito particular.
-
Em outras palavras, se a sua redução é o que é chamado algébrica,
-
(Eu não vou explicar o que isso significa aqui.)
-
Isto é, se for dado um cubo raiz oráculo, você realmente pode me mostrar um algoritmo
-
que, então, fator. Essa redução, por si só,
-
seria, na verdade, implica um algoritmo de factoring.
-
Ok então, que dizer que se factoring é difícil,
-
uma redução na realidade não existe.
-
Mas, como eu digo isso é uma evidência muito fraca.
-
Porque, que é dizer que a redução deve ser algébrico.
-
Talvez, há alguns outros tipos de reduções que
-
não temos realmente considerado. Então, eu o faria
-
incentivá-lo a pensar um pouco sobre isso
-
pergunta. É realmente muito interessante.
-
Como você usaria um algoritmo de raiz cúbica de fatorar o módulo?
-
Mas como eu disse, tanto quanto sabemos, a RSA é uma função de uma maneira.
-
Na verdade, quebrando RSA, computando raízes e'th que é, na verdade, requer módulo de factoring o.
-
Nós todos acreditamos que é verdade, e isso é o estado da arte.
-
Mas, agora, tem havido muito trabalho para tentar melhorar o desempenho da RSA.
-
Ou criptografia, RSA ou melhorar o desempenho de decodificação RSA.
-
E ao que parece, tem havido uma série de falsos começos nesta direção.
-
Então, eu quero te mostrar, este maravilhoso exemplo como um aviso.
-
Então, basicamente, este é um exemplo de como não se melhorar a perfomance da RSA.
-
Assim, você pode pensar que se eu quisesse acelerar descriptografia RSA,
-
lembre-se de decodificação é feita através do aumento da
-
cifrada com a potência de d. E, lembre-se
-
que o algoritmo de exponenciação correu em tempo linear
-
no tamanho de d. Tempo linear no log de d.
-
Assim, você pode pensar a si mesmo, bem, se eu queria
-
para acelerar a decodificação RSA, por que não eu só uso um d minúsculo.
-
Eu vou dizer, eu vou dizer um expoente de decodificação que é da ordem de 2 a 128.
-
Então é claramente grande o suficiente para que a pesquisa exaustiva contra d não é possível.
-
Mas, normalmente, a descriptografia expoente d seria tão grande como o módulo, digamos 2000 bits.
-
Usando d que é apenas 128 bits, eu basicamente acelerar descriptografia RSA por um fator de 20.
-
Bem, eu descia de 2000 bits para 100 bits.
-
Assim, a exponenciação seria executado 20 vezes mais rápido.
-
Acontece que isso é uma péssima idéia. Idéia terrível, terrível, no seguinte sentido.
-
Há um ataque por Michael Wiener, que mostra que, de facto,
-
assim que o expoente privado d é menor do que a quarta raiz do módulo.
-
Vamos ver, se o módulo é de cerca de 2048 bits
-
o que significa que, se d for menor que 2 a 512, em seguida, A RSA é completamente, completamente inseguro.
-
E, isto é, ele é inseguro da pior forma possível.
-
Ou seja, apenas dei uma chave pública e um e, você pode rapidamente recuperar a chave privada d.
-
Bem, para algumas pessoas, disse: bem, este ataque funciona até 512 bits.
-
Então, por que donÂ't fazemos o módulo, por exemplo, você sabe que 530 bits.
-
Então, este ataque realmente não seria aplicável.
-
Mas, ainda assim, temos de acelerar descriptografia RSA por um fator de 4,
-
porque diminuiu o expoente de 2000 bits para, digamos, 530 bits.
-
Bem se vê, mesmo que não seja seguro. Na verdade,
-
existe uma extensão ao ataque de Wiener, que é realmente muito
-
mais complicada, que mostra que se d
-
é inferior a 0,292 N para o, então também RSA é inseguro.
-
E, na verdade, a conjectura de que isto é verdadeiro se a N para o 0.5.
-
Portanto, mesmo se d é como N para a 0,4999, RSA ainda deve ser inseguro,
-
embora isso seja um problema em aberto. É, novamente, um problema maravilhoso aberto,
-
Tem sido aberto para como, o que é, 14 anos.
-
E, ninguém pode progredir para além desta 0,292.
-
De alguma forma, parece meio estranho, por que 0,292
-
ser a resposta certa e ainda ninguém pode ir além 0,292.
-
Então, só para ser mais preciso, quando eu digo que a RSA é inseguro,
-
o que eu quero dizer é dado apenas a chave pública N e E,
-
seu objetivo é recuperar a chave secreta d.
-
Se você está curioso, onde vem de 0,292,
-
Eu vou te dizer que o que é, é basicamente um menos 1 sobre raiz quadrada de 2.
-
Agora, como isso poderia ser a resposta certa para este problema?
-
É muito mais natural que a resposta é N a 0,5.
-
Mas isso ainda é um problema em aberto. Novamente, se você quer pensar sobre isso,
-
é uma espécie de um problema divertido para trabalhar.
-
Assim, a lição no presente é que não se deve impor qualquer estrutura em d
-
para melhorar o desempenho da RSA, e de facto
-
agora há uma série de resultados como este que mostram
-
que, basicamente, qualquer tipo de truques como este para tentar melhorar o desempenho da RSA
-
vai acabar em desastre. Portanto, este não é o caminho certo para melhorar o desempenho da RSA.
-
Inicialmente eu não estava indo para cobrir os detalhes do ataque de Wiener.
-
Mas dadas as discussões em classe, eu acho que alguns de vocês gostaria de ver os detalhes.
-
Tudo o que envolve é apenas manipular algumas desigualdades.
-
Se você não está confortável com isso, sinta-se livre para pular este slide,
-
embora eu acho que muitos de vocês realmente gostam de ver os detalhes.
-
Então deixe-me lembrá-lo no ataque Wiener basicamente
-
nós estamos dando o módulo eo expoente RSA N e E,
-
e nosso objetivo é recuperar d, o expoente privado d,
-
e tudo o que sabemos é que d é basicamente menor do que a raiz quarta de N.
-
Na verdade, eu vou assumir que d é menor do que a raiz quarta de N dividido por 3.
-
Esta 3 realmente não importa, mas o termo dominante aqui é que d é menor do que a raiz quarta de N.
-
Então vamos ver como fazê-lo. Então, primeiro de tudo, lembrar que
-
porque e e d são RSA expoentes públicas e privadas,
-
sabemos que e d vezes é um modulo phi (N). Bem, o que isso significa?
-
Isto significa que existe algum inteiro k tal que e tempos d é igual a k vezes phi (N), acrescido de 1.
-
Basicamente é o que significa para os tempos e d ser um modulo phi (N).
-
Basicamente múltipla algum inteiro de phi (N) mais 1.
-
Então agora vamos olhar para esta equação um pouco.
-
E na verdade, esta equação é a equação-chave no ataque.
-
E o que nós vamos fazer é antes de tudo dividir ambos os lados por d vezes phi (N).
-
E na verdade eu vou mover este termo aqui para a esquerda.
-
Então, depois que eu dividir por d vezes phi (N), o que eu vejo é que
-
e dividido pelo phi (N) menos k dividido por d é igual a 1 ao longo d vezes phi (N).
-
Ok, então tudo que eu fiz é que eu só dividido por d vezes phi (N)
-
e mudei o k vezes phi prazo (N) para o lado esquerdo.
-
Agora, apenas para os pedaços que eu estou indo para adicionar valores absolutos aqui.
-
Estes irão tornar-se útil em apenas um minuto, mas é claro que eles não mudam essa igualdade em tudo.
-
Agora, phi (N), claro, é quase N; phi (N) é muito, muito perto de N, como dissemos anteriormente.
-
E tudo que eu vou precisar de então para essa fração é só para dizer que
-
é inferior a 1 sobre raiz quadrada de N. Na verdade, é muito, muito menor
-
do que 1 sobre raiz quadrada de N, na verdade é da ordem de 1 por N, ou até mais do que isso,
-
mas para nossos propósitos tudo o que precisamos é que essa fração for inferior a 1 sobre raiz quadrada de N.
-
Agora vamos olhar para essa fração por apenas um minuto.
-
Você percebe que esta fração à esquerda aqui é uma fração que nós realmente não sabemos.
-
Sabemos e, mas não sabemos phi (N), e, como resultado, não sabemos e sobre phi (N).
-
Mas temos uma boa aproximação e mais de phi (N). Ou seja, sabemos que phi (N)
-
está muito perto de N. Portanto, e mais de phi (N) está muito próximo e mais de N.
-
Portanto, temos uma boa aproximação a esta fração lado esquerdo, e nomeadamente sobre N.
-
O que realmente queremos é a fração lado direito,
-
porque uma vez que temos a fração lado direito,
-
basicamente, que vai envolver d, e então nós vamos ser capazes de recuperar d. Ok, então vamos ver
-
se substituirmos e sobre phi (N) por e sobre N, vamos ver que tipo de erro que vamos conseguir.
-
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
-
que phi (N) é basicamente N - p - q + 1,
-
o que significa que menos phi N (N) vai ser menor do que p + q.
-
Na verdade, eu deveria, para ser mais preciso, eu realmente deveria escrever p + q + 1, mas você sabe,
-
que se preocupa com este 1, que não é, ele realmente não afeta nada.
-
Então, eu estou indo só para ignorá-lo pela simplicidade.
-
Ok, então N - phi (N) é menor que p + q. Ambos p e q são mais ou menos metade do comprimento de N,
-
assim você sabe, eles são os dois tipos de da ordem de raiz quadrada de N,
-
Então, basicamente p + q vamos dizer é menos do que 3 vezes a raiz quadrada de N.
-
Ok, então vamos usar essa desigualdade em apenas um minuto.
-
Mas agora vamos começar a usar o fato de que sabemos algo sobre d,
-
a saber, que d é pequena. Então, se olharmos para esta desigualdade aqui,
-
d for inferior a quarta raiz de N dividido por 3.
-
É realmente bastante fácil de ver que se eu quadrado ambos os lados
-
e eu só manipular as coisas um pouco, é [não] difícil ver que
-
isso implica diretamente a seguinte relação,
-
basicamente um mais de 2 d quadrado menos 1 sobre raiz quadrada de N é maior do que 3 sobre raiz quadrada de N.
-
Como eu disse, este segue basicamente por quadratura ambos os lados, em seguida, tendo o
-
inverso de ambos os lados, e então eu acho que multiplicando um lado pelo meio.
-
Ok, então você pode facilmente obter essa relação, e vamos precisar essa relação em apenas um minuto.
-
Então, agora vamos ver, o que gostaria de fazer é obrigado
-
a diferença de e mais de N e K sobre d. Bem, o que sabemos?
-
Pela desigualdade triangular, sabemos que isso é igual a
-
a distância entre e ao longo e por cima e N phi (N), além
-
a distância a partir de e ao longo phi (N) para k ao longo d.
-
Este é apenas o que é chamado de uma desigualdade triangular, esta é apenas uma propriedade de valores absolutos.
-
Agora, este valor absoluto aqui, nós já sabemos como vinculado.
-
Se você pensar sobre isso é basicamente o limite que nós já derivada.
-
Então, nós sabemos que este valor absoluto aqui é basicamente menor do que 1 sobre raiz quadrada de N.
-
Agora, o que nós sabemos sobre esse valor absoluto aqui? O que é e mais N menos e mais de phi (N)?
-
Bem, vamos fazer denominadores comuns e ver o que conseguimos.
-
Assim, o denominador comum que vai ser N vezes phi (N),
-
o numerador e, neste caso, vai ser vezes e phi (N) menos N.
-
Que sabemos desta expressão aqui é menos do que três vezes a raiz quadrada de N.
-
Então, realmente o que esta numerador vai ser é o e três vezes a raiz quadrada de N.
-
O numerador vai ser menor do que e 3 vezes a raiz quadrada de N.
-
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.
-
Em outras palavras, se eu apagar e apagar e eu phi (N) Eu só fez a fração maior.
-
Ok, então esse valor inicial absoluta é agora vai ser
-
menor do que 3 raiz quadrada de N sobre N, que é simplesmente,
-
3 raiz quadrada de N sobre N é simplesmente 3 sobre raiz quadrada de N.
-
Ok, mas o que sabemos sobre a 3 sobre raiz quadrada de N?
-
Nós sabemos que é menos de 1 por 2 d quadrado menos 1 sobre raiz quadrada de N.
-
Ok, então esse é o fim da nossa derivação.
-
Portanto, agora sabemos que o primeiro valor absoluto é menor do que 1 sobre 2 raiz d quadrado menos quadrado da N.
-
O segundo valor absoluto for inferior a 1 sobre raiz quadrada de N.
-
E, portanto, a soma é inferior a 1 sobre 2 d quadrado.
-
E esta é a expressão que eu quero que você olhar.
-
Então, aqui, deixe-me rodear-lo um pouco. Então deixe-me circular esta parte e esta parte.
-
Agora, vamos olhar um pouco neste fração aqui.
-
E o que vemos é, antes de tudo, como antes, agora sabemos o valor de e mais de N,
-
eo que nós gostaríamos de saber é o valor k sobre d.
-
Mas o que sabemos sobre este k fração sobre d?
-
Nós sabemos de alguma forma que a diferença entre essas duas frações é muito pequeno;
-
é inferior a 1 sobre 2 d quadrado. Agora, isso acaba por acontecer muito raramente,
-
que k mais d aproxima e mais de N tão bem que
-
a diferença entre os dois é menor do que o quadrado do denominador de k ao longo d.
-
Acontece que isso não pode acontecer muitas vezes.
-
Acontece que há muito poucas frações da forma k mais d que a fração de outra aproximada
-
tão bem que a sua diferença é inferior a 1 durante 2 d quadrado.
-
E, de facto, o número de tais fracções vai ser, no máximo, em N. logarítmica
-
Portanto, agora há um algoritmo de fração contínua. É uma fração muito famoso
-
que, basicamente, o que ele vai fazer é, a partir do e fração sobre N,
-
ele vai se recuperar de log (N) possíveis candidatos para k sobre d.
-
Então, nós apenas julgá-los todos, um por um até encontrar o k correto sobre d.
-
E, então, está feito. Estamos a fazer, porque sabemos que,
-
bem vezes e d é 1 k mod, portanto d é relativamente privilegiada para k,
-
por isso, se nós apenas representam k mais d como uma fração racional numerador, você sabe, por denominador,
-
o denominador deve ser d. E assim acabou recuperado, você sabe,
-
nós tentamos todos os possíveis log (N) e frações que mais aproximado N tão bem
-
que a diferença é inferior a 1 durante 2 d quadrado.
-
E, então, basta olhar para o denominador de todas as frações, e um dos denominadores deve ser d.
-
E, então, está feito; acabamos recuperou a chave privada.
-
Portanto, este é um ataque muito bonito. E mostra, basicamente, como,
-
se o expoente privado é pequeno, menor do que a quarta raiz de N,
-
então podemos recuperar d completamente, com bastante facilidade. Ok, então eu vou parar por aqui.