Significado de: “'Se fatorar números inteiros grandes é difícil, quebrar a RSA é difícil', não está comprovado”

30

Eu estava lendo o CLRS e disse:

Se fatorar números inteiros grandes for fácil, é fácil quebrar o sistema de criptografia RSA.

O que faz sentido para mim porque, com o conhecimento de e , é fácil criar a chave secreta que é o conhecimento da chave pública. No entanto, explica a declaração inversa, que eu não entendo direito:pq

A declaração inversa, de que se fatorar números inteiros grandes é difícil, a quebra do RSA é difícil, não está comprovada.

O que a declaração acima significa formalmente? Se assumirmos que o fatoramento é difícil (de alguma forma formal), por que isso não implica que a quebra do sistema de criptografia RSA seja difícil?

Agora considere que se assumimos que o fatoramento é difícil ... e descobrimos que isso significa que o sistema de criptografia RSA é difícil de quebrar. O que isso significa formalmente?

Charlie Parker
fonte
3
Isso pode significar que quebrar o RSA é difícil, mas não foi comprovado .
Tom van der Zanden
2
o problema do logaritmo discreto no coração de quebrar RSA enquanto "muito similar" não foi provado ser equivalente ao factoring, é uma grande questão em aberto do campo (ambos criptografia e TCS)
vzn
1
O segundo não deveria usar um traço em vez de vírgulas? Um traço não é usado quando há vírgulas dentro da cláusula dependente? The converse statement -- that if factoring large integers is hard, then breaking RSA is hard -- is unproven.
Czipperz
@ruakh: Opa, sim ... Eu até fiz questão de checar novamente, mas ainda entendi errado. Eu continuo esquecendo que você deve reduzir a um problema que você sabe ser fácil, não um problema que você sabe que é pelo menos tão difícil quanto o atual. :-) Obrigado por isso, eu o removi.
Mehrdad
Argumento matemático: "se , então B " significa o mesmo que "se não B , então não A ". Você não pode dizer nada sobre "se não A , então não B ". ABBAAB
Drzbir 8/03

Respostas:

50

A maneira mais fácil de pensar sobre isso é pensar no contrapositivo.

A declaração:

se fatorar números inteiros grandes for difícil, é difícil quebrar o RSA

é equivalente ao seguinte:

se quebrar o RSA é fácil, é fácil calcular números inteiros grandes

Esta afirmação não foi comprovada.

O que eles estão dizendo é, suponha que tenhamos um algoritmo que resolve o fatoramento em tempo polinomial. Em seguida, podemos usá-lo para construir um algoritmo que resolve o RSA em tempo polinomial.

Mas, poderia haver outra maneira de decifrar o RSA que não envolvesse números inteiros de fatoração. É possível descobrirmos que podemos quebrar o RSA de uma maneira que não nos permita fatorar números inteiros no tempo polinomial.

Em resumo, sabemos que o RSA é pelo menos tão fácil quanto fatorar. Há dois resultados possíveis: RSA e fatoração são de dificuldade equivalente, ou o RSA é um problema estritamente mais fácil do que fatorar. Não sabemos qual é o caso.

jmite
fonte
10
"pelo menos tão fácil" - essa é uma maneira de interpretar as reduções que devem ser ensinadas mais expressamente, juntamente com o contrário.
G. Bach
Você pode fazê-lo de qualquer forma, se X é pelo menos tão duro como Y, Y é pelo menos tão fácil como X.
jmite
2
Isso foi o que eu quis dizer - quase todo mundo provavelmente já ouviu falar que "X é pelo menos tão difícil quanto Y", mas "Y é pelo menos tão fácil quanto X" raramente é explicado - embora seja igualmente útil.
G. Bach
1
Parece-me lembrar vagamente que Donald Knuth mencionou um algoritmo que, dado que uma máquina que pode quebrar magicamente mensagens arbitrárias criptografadas por RSA seria capaz de fatorar produtos de dois primos grandes. Eu poderia estar errado :-(
gnasher729
31

A existência de um caminho difícil não implica que não haja caminho fácil.

Pode haver várias maneiras de quebrar o RSA e precisamos encontrar apenas uma delas.


Uma dessas maneiras é fatorar um número inteiro grande; portanto, se isso for fácil, podemos fazê-lo dessa maneira e o RSA será quebrado. Esta é também a única maneira que sabemos ainda. Se for inviável fazer isso, ainda podemos encontrar uma outra, computacionalmente menos exigente maneira de realizar a nossa tarefa sem a necessidade de explicitamente calcular p e q do n .


Para provar que o RSA está quebrado, precisamos provar que um maneira de fazer isso é fácil.

Para provar que o RSA é seguro, precisamos provar que todas as maneiras de fazê-lo são difíceis.


Por fim, sua declaração não é comprovada, pois não existe outro método mais fácil que extraia informações de um texto cifrado.

Rainer P.
fonte
1
Poderíamos provar que o RSA e o fatoração são igualmente difíceis se pudéssemos produzir um algoritmo que pode fatorar produtos de dois primos grandes, gerando algumas mensagens criptografadas RSA especiais, quebrando-as e fazendo mais alguns cálculos. Isso significaria que a RSA não é mais fácil do que fatorar. Isso não significa que seja fácil ou difícil.
gnasher729
@ gnasher729 Isso seria suficiente? Se o algoritmo pudesse fatorar produtos de dois primos grandes, mas não produtos que envolvam mais de 2 primos ou produtos que envolvam primos pequenos?
Otakucode
@ Acho que o RSA depende apenas dos fatores que estão sendo coprime. Portanto, conhecer produtos de vários fatores seria simples.
Taemyr 16/12/2015
10

Uma maneira adicional de analisar isso é que a quebra da RSA requer apenas um caso especial de fatoração, que pode ou não ser fácil, independentemente da questão geral da fatoração.

Como um exemplo simples, considere o fato de que fatorar é realmente difícil, mas apenas para números com fatores diferentes. Fatorar números compostos com apenas dois fatores diferentes (como usado no RSA) ainda pode ser fácil.3

Tocou.
fonte
7

Isso significa que o problema da RSA parece (no momento) ser mais específico do que fatorar.

Portanto, o problema da RSA é o seguinte: conhecer um semiprime e algum expoente e , e um valor v , encontre m de modo que v m epqe,v,m . (Na verdade, eu entendi errado na minha resposta original, de modo que minha redação do problema da RSA era equivalente a levar em conta algum algoritmo PP. Opa! Então você não está sozinho em ficar confuso com os detalhes aqui.)vmemodpq

O problema de fatoração é o seguinte: conhecendo um semiprime , encontre p e q .pq,pq

Se você conseguir resolver com eficiência o problema de fatoração, poderá resolver com eficiência o problema da RSA: pegue o semiprime, fatore-o, use alguns teoremas sobre módulos primos para calcular um expoente inverso que revele todos os textos cifrados como m v ddmvd . (De fato, esses teoremas são como a configuração do RSA funciona: conhecemos os dois números primos durante a fase de configuração.)

m

De fato, em 1998, Boneh e Venkatesan publicaram uma prova de que uma certa classe simples de algoritmos (mais, horários, expoentes, nenhum material do tipo XOR / NAND) não pode ser usada para transformar uma solução de problema de RSA em um algoritmo de fatoração. O argumento tinha uma engenhosidade simples: manipulando matematicamente essas operações aritméticas, podemos descobrir que o "algoritmo de redução" (para precisão: este é o algoritmo que usa um "oráculo" RSA para um semiprime para fatorar o semiprime) é um algoritmo de fatoração por si só, para que possamos modificá-lo para uma variante que não faça chamadas para o seu oráculo. Portanto, temos uma tricotomia: (a) não existe um algoritmo de redução ou (b) o algoritmo de redução não possui uma boa interpretação aritmética ou (c) o fatoramento é em tempo polinomial, como era o algoritmo de redução.

CR Drost
fonte
@ Gilles, na verdade, acho que você está certo, por isso resolvi minha resposta.
CR Drost
3

logeCZmemC

Essas duas tarefas matemáticas estão relacionadas, mas (se bem me lembro) acredita-se que uma solução para uma não implicaria uma solução para a outra. Não sei se são as duas únicas maneiras de quebrar matematicamente o RSA.

zwol
fonte
mm