Dado el RSA, ¿por qué no sabemos si es posible la criptografía de clave pública?

23

Estaba en Wikipedia en la lista de problemas informáticos no resueltos y encontré esto: ¿es posible la criptografía de clave pública?

¿Pensé que el cifrado RSA era una forma de criptografía de clave pública? ¿Por qué es esto un problema?

Namster
fuente
55
Ni siquiera sabemos si la criptografía simétrica puede ser segura, y esa es una conjetura mucho más débil que la seguridad del cifrado de clave pública.
CodesInChaos
@CodesInChaos Eso es cierto siempre que estemos hablando de seguridad basada en la complejidad computacional. Pero si está considerando la seguridad teórica de la información, existen construcciones probadamente seguras, como la plataforma de un solo uso para el cifrado y Wegman-Carter para la autenticación de mensajes.
Kasperd

Respuestas:

31

No sabemos con seguridad si RSA es seguro. Podría ser que RSA se puede romper en tiempo polinómico, por ejemplo, si la factorización se puede hacer de manera eficiente. Lo que está abierto es la existencia de un criptosistema de clave pública demostrablemente seguro . No sabemos con certeza si tal criptosistema existe en absoluto; por lo que sabemos, cada criptosistema podría romperse de manera eficiente.

Un problema diferente y no relacionado con RSA es que puede ser roto por computadoras cuánticas. Este es un problema no relacionado ya que la definición de un criptosistema seguro de clave pública solo requiere que el criptosistema no sea rompible por computadoras clásicas (no cuánticas).

Sin embargo, en términos prácticos, RSA parece seguro y se usa todo el tiempo. Esto se debe a la brecha entre la teoría y la práctica. Si bien, en teoría, no sabemos con certeza si RSA es seguro, prácticamente hablando tenemos que usar un sistema de cifrado de clave pública, y RSA es una buena opción ya que las personas han intentado romperlo y han fallado. En términos generales, un criptosistema conocido que preocupa a las personas es más seguro que uno oscuro, ya que se ha resistido a los intentos de los criptógrafos. Esto no constituye una prueba de que es seguro, puede que no lo sea, pero es lo mejor que podemos hacer.

Yuval Filmus
fuente
44
En pocas palabras: seguro hasta que se rompa.
Ismael Miguel
2
Gran respuesta. También agregaría que cualquier criptografía solo se entrega con un marco de tiempo de baja probabilidad de que se rompa. Nadie entrega un sistema criptográfico y declara que es seguro. Siempre dicen que no es probable que se rompa en los próximos 5 años más o menos. Esto es un problema para las ventas, ya que, a menudo, los clientes no técnicos ven esto como una debilidad declarada.
RSinohara
Esto es en realidad una deficiencia general en la informática: CS es muy bueno para demostrar cuánto tiempo llevará un algoritmo, pero muy débil para poder demostrar que no hay algoritmos más rápidos.
RBarryYoung
3

Aquí hay algunos otros ángulos / detalles sobre esta pregunta, más específicos y en general. Como YF escribe en un comentario, a pesar de las apariencias, no se ha demostrado que RSA sea al menos tan difícil como factorizar. Romper RSA implica el problema de registro discreto que, por supuesto, está estrechamente relacionado con la factorización de la complejidad, pero no se ha demostrado que sea la misma complejidad. Pero (como se señaló) ni siquiera se ha demostrado que el factoring sea difícil.

YF también menciona la computación cuántica. Como los conocedores saben, RSA no es seguro contra el cálculo cuántico, que se ha demostrado que es capaz de factorizar el tiempo P utilizando algoritmo Shors . El algoritmo de Shors se consideró un gran avance en ese momento. Y otro avance importante para mencionar en un área "cercana" es el algoritmo de primalidad AKS que demostró que la prueba de primalidad está en P. Los avances teóricos en la teoría de la complejidad son raros pero no desconocidos.

YF no menciona, pero siempre está al acecho en el fondo de estas preguntas, la "gran pregunta" de P =? NP todavía está abierta. En general, se cree que "la criptografía algorítmica podría ser imposible" (a excepción de los pads de una sola vez) si P = NP, que generalmente no creen los expertos.

Una excelente manera de conceptualizar científicamente esto es Impagliazzos 5 worlds , descripción general de Kabanets . Sorprendentemente, los teóricos de la complejidad no saben "en cuál de los 5 mundos vivimos", aunque hay evidencia circunstancial que se inclina de alguna manera. El mundo en el que vivimos depende de las conjeturas de la teoría de la complejidad abierta. También se relacionan con problemas abiertos en existencias de funciones de trampillas y funciones unidireccionales . (Se conjetura que RSA es ambos). Hubo una conferencia de investigación de 2009 sobre los mundos Impagliazzos con el último pensamiento informado.

vzn
fuente
1
véase también el estado de los mundos Impagliazzos / Ciencias de la computación teóricas . en resumen, aproximadamente, los expertos consideran que RSA es seguro o probable, pero no seguro, y esa brecha atraviesa muchas de las preguntas abiertas más importantes en el campo.
vzn
2

Una cosa que debe definirse aquí es la definición de posible. Hay dos formas de responder esto. La primera es: ¿puede un criptosistema de clave pública considerarse información teóricamente segura? En el sentido más amplio, esto requiere que el algoritmo sea seguro incluso cuando está sujeto a un ataque que involucra una potencia informática infinita. Hay un sistema conocido que ha logrado esto, el pad de una sola vez, sin embargo, esto es solo en teoría, ya que no podemos crear los números verdaderamente aleatorios requeridos, y es la clave privada. La segunda forma en que se puede ver la pregunta es, ¿puede un criptosistema de clave pública considerarse incondicionalmente seguro? Esta segunda definición es más flexible. En el caso de RSA, si alguien demostrara que la factorización de enteros era tan difícil como creemos actualmente, y demuestra que no hubo otras suposiciones o fallas en el sistema, entonces RSA sería incondicionalmente seguro. La seguridad incondicional elimina el requisito de poder de cómputo infinito y lo relaja hasta ser imposible en el universo físico. Dado que todos nuestros algoritmos de clave pública se basan en suposiciones masivas sobre la computabilidad, no cumplen con la segunda definición.

lPlanta
fuente
Romper RSA no es equivalente a factorizar; Es potencialmente más fácil.
Yuval Filmus
Esta respuesta es confusa. El pad de una sola vez no es un criptosistema de clave pública, por lo que no es correcto que el pad de una sola vez haya logrado esto. La respuesta a "¿puede un criptosistema de clave pública considerarse información teóricamente segura?" no es". Además, no hay pruebas conocidas de que "factorizar sea difícil" implica que "RSA es seguro"; de hecho, hay razones para sospechar que podría no haber ninguna reducción de esa forma.
DW