É uma função RSA one-way? (17 min)

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.