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

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?

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.

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.

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.