Significado de: "'Si factorizar números enteros grandes es difícil, romper RSA es difícil' no está probado"

30

Estaba leyendo CLRS y se dice:

Si factorizar enteros grandes es fácil, entonces romper el criptosistema RSA es fácil.

Lo que tiene sentido para mí porque con el conocimiento de p y q , es fácil crear la clave secreta que el conocimiento de la clave pública. Sin embargo, explica la declaración inversa, que no entiendo del todo:

La afirmación inversa, que si factorizar números enteros grandes es difícil, entonces romper RSA es difícil, no está probado.

¿Qué significa formalmente la declaración anterior? Si suponemos que la factorización es difícil (de alguna manera formal), ¿por qué eso no implica que romper el sistema criptográfico RSA sea difícil?

Ahora considere que si asumimos que la factorización es difícil ... y que descubrimos que significaba que el criptosistema RSA es difícil de romper. ¿Qué significaría eso formalmente?

Charlie Parker
fuente
3
Se podría implicar que romper RSA es difícil, pero no se ha demostrado .
Tom van der Zanden
2
El problema del logaritmo discreto en el corazón de la ruptura de RSA, mientras que "muy similar" no ha demostrado ser equivalente a la factorización, es una gran pregunta abierta del campo (tanto criptografía como TCS)
vzn
1
¿No debería el segundo usar un guión en lugar de comas? ¿No se usa un guión cuando hay comas dentro de la cláusula dependiente? The converse statement -- that if factoring large integers is hard, then breaking RSA is hard -- is unproven.
Czipperz
@ruakh: Vaya, sí ... Incluso me aseguré de comprobarlo dos veces, pero aún así me equivoqué. Sigo olvidando que se supone que debes reducirlo a un problema que sabes que es fácil, no un problema que sabes que es al menos tan difícil como el actual. :-) Gracias por eso, lo eliminé.
Mehrdad
Argumento matemático: "si , entonces B " significa lo mismo que "si no es B , entonces no es A ". No se puede decir nada sobre "si no es A , entonces no B ". ABBAAB
drzbir

Respuestas:

50

La forma más fácil de pensarlo es pensar en el contrapositivo.

La declaración:

si factorizar números enteros grandes es difícil, entonces romper RSA es difícil

es equivalente a lo siguiente:

si romper RSA es fácil, entonces factorizar enteros grandes es fácil

Esta declaración no ha sido probada.

Lo que están diciendo es, supongamos que tenemos un algoritmo que resuelve la factorización en tiempo polinómico. Entonces podemos usarlo para construir un algoritmo que resuelva RSA en tiempo polinómico.

Pero, podría haber alguna otra forma de descifrar RSA que no implique factorizar enteros. Es posible que descubramos que podemos descifrar RSA de una manera que no nos permita factorizar números enteros en tiempo polinómico.

En resumen, sabemos que RSA es al menos tan fácil como factorizar. Hay dos resultados posibles: RSA y factoring son de dificultad equivalente, o RSA es un problema estrictamente más fácil que factoring. No sabemos cuál es el caso.

jmite
fuente
10
"al menos tan fácil": esa es una forma de interpretar las reducciones que deberían enseñarse de manera más expresa y al revés.
G. Bach
Puede hacerlo de cualquier manera, si X es al menos tan difícil como Y, Y es al menos tan fácil como X.
jmite
2
Eso es lo que quise decir: casi todos probablemente han escuchado "X es al menos tan difícil como Y", pero "Y es al menos tan fácil como X" se explica muy raramente, aunque es igual de útil.
G. Bach
1
Me parece recordar vagamente que Donald Knuth mencionó un algoritmo que, dado que una máquina que puede descifrar mágicamente mensajes cifrados RSA arbitrarios, podría factorizar productos de dos números primos grandes. Podría tener esto mal :-(
gnasher729
31

La existencia de un camino difícil no implica que no haya un camino fácil.

Puede haber varias formas de romper el RSA y solo necesitamos encontrar una de ellas.


Una de estas formas es factorizar un número entero grande, por lo que si eso es fácil, podemos hacerlo de esta manera y se rompe el RSA. Esta es también la única forma en que lo sabemos todavía. Si no es factible hacer eso, todavía podemos encontrar otro, computacionalmente menos exigente camino para llevar a cabo nuestra tarea sin la necesidad de calcular explícitamente p y q de n .


Para demostrar que RSA está roto, debemos demostrar que una forma de hacerlo es fácil.

Para demostrar que RSA es seguro, debemos demostrar que todas las formas de hacerlo son difíciles.


Finalmente, su declaración no está probada porque no está comprobado que no exista otro método más fácil que extraiga información de un texto cifrado.

Rainer P.
fuente
1
Podríamos demostrar que RSA y factoring son igualmente difíciles si pudiéramos producir un algoritmo que pueda factorizar productos de dos primos grandes generando algunos mensajes cifrados RSA especiales, descifrándolos y luego haciendo algunos cálculos más. Eso significaría que RSA no es más fácil que factorizar. No significa que sea fácil o difícil.
gnasher729
@ gnasher729 ¿Sería eso suficiente? ¿Si el algoritmo pudiera factorizar productos de dos números primos grandes, pero no productos que involucren más de 2 números primos, o productos que involucren números primos pequeños?
otakucode
@ Creo que RSA solo depende de los factores coprimos. Así que moverse por productos de múltiples factores sería sencillo.
Taemyr
10

Una forma adicional de verlo es que romper el RSA requiere solo un caso especial de factorización, lo que puede o no ser fácil independientemente de la cuestión general de la factorización.

3

Sonó.
fuente
7

Significa que el problema RSA parece (en este momento) ser más específico que la factorización.

pqe,v,mvmemodpq

El problema de factorización es este: conociendo un semiprime encuentre y .p qpq,pq

Si puede resolver eficientemente el problema de factorización, entonces puede resolver eficientemente el problema RSA: tome el semiprime, factoréelo, use algunos teoremas sobre módulos primos para calcular un exponente inverso que revele todos los textos cifrados como . (De hecho, estos teoremas son cómo funciona la configuración de RSA: conocemos los dos primos durante la fase de configuración).m v ddmvd

Sin embargo, se no sabe que la solución de este problema anterior para los mensajes arbitrarios le dirá nada acerca de los factores del módulo o los exponentes involucrados. Puede o no puede ser; No lo sabemos Es probable que muchas personas inteligentes hayan analizado el problema, pero nada obvio ha saltado a ninguno de ellos. Por lo tanto, no se sabe que el problema de factorización se resuelve con soluciones al problema de RSA (más esfuerzo polinómico), solo que el problema de RSA se resuelve con soluciones al problema de factorización (más esfuerzo polinómico).m

De hecho, en 1998, Boneh y Venkatesan publicaron una prueba de que una cierta clase simple de algoritmos (más, tiempos, exponentes, nada de tipo XOR / NAND) no se puede usar para convertir una solución del problema RSA en un algoritmo de factorización. El argumento tenía un ingenio simple: al manipular matemáticamente esas operaciones aritméticas, podemos descubrir que el "algoritmo de reducción" (por precisión: este es el algoritmo que usa un "oráculo" RSA para un semiprime para factorizar ese semiprime) fuera a ser un algoritmo de factorización por derecho propio, para que podamos modificarlo a una variante que no haga llamadas a su oráculo. Entonces tenemos una tricotomía: (a) no existe tal algoritmo de reducción, o (b) el algoritmo de reducción no tiene una buena interpretación aritmética o (c) la factorización es de tiempo polinomial al igual que el algoritmo de reducción.

CR Drost
fuente
“No se sabe que encontrar este exponente inverso d en cualquier e dado le dirá algo sobre los factores del módulo” ¿No es así? Se puede calcular y dado , yq n e dpqned . El algoritmo expresado es obviamente PP, ¿no se sabe que está en P?
Gilles 'SO- deja de ser malvado'
@Gilles en realidad creo que tienes razón, así que arreglé mi respuesta en consecuencia.
CR Drost
3

RSA depende de dos tareas matemáticas abstractas que se consideran difíciles: la factorización de enteros, como usted sabe, pero también el problema del logaritmo discreto . Puede romper RSA si puede factorizar rápidamente un número que es el producto de dos primos desconocidos grandes; pero puede también romper RSA si se puede encontrar rápidamente en el grupo finito , donde y son el exponente RSA pública y módulo, y es el texto cifrado.Z m e m ClogeCZmemC

Estas dos tareas matemáticas están relacionadas, pero (si no recuerdo mal) se cree que una solución para una no implicaría una solución para la otra. No sé si son las dos únicas formas de romper matemáticamente RSA.

zwol
fuente
Creo que podrías estar recordando mal las cosas. Esos no son realmente dos problemas diferentes: si puede encontrar el módulo de registro discreto , entonces puede factorizar . En otras palabras, una solución al problema de registro discreto ciertamente implica una solución al problema de factorización. mmm
DW