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

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:$p$$q$

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?

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.

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.

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$

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 $pq$$e,$$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.)$v \equiv m^e \mod pq$

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

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 $d$$m \equiv v^d$ . (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.

$\log_e C$$\mathbb{Z}_{m}$$e$$m$$C$

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.