Si se resuelve el problema P vs. NP, ¿se vuelve obsoleto el software criptográfico moderno? ¿Si es así, cómo?

TL; DR: Si P = NP, nuestras definiciones teóricas actuales de seguridad quedarían obsoletas. Pero prácticamente, aún podríamos ser capaces de construir criptosistemas útiles.

Versión larga:
El tiempo de ejecución asintótico de un ataque contra un sistema criptográfico es útil porque nos dice cuánto más trabajo tenemos que hacer a medida que aumenta el poder computacional de un atacante. Pero una vez que elegimos un sistema específico para usar, solo nos da una regla general de cuán seguro es un sistema.

Para aplicaciones prácticas, la seguridad se mide en términos de la cantidad de operaciones que necesitaría un atacante para romper el sistema. Por ejemplo, se cree que RSA-1024 proporciona aproximadamente 80 bits de seguridad, lo que significa que un atacante necesitaría 2 ^ 80 operaciones para romper el sistema. Para una sola computadora que funciona a 1 GHz, esto tomaría aproximadamente 2 ^ 50 segundos, o aproximadamente 30 millones de años (si mis cálculos son correctos). Esto se ha considerado bastante seguro hasta ahora, pero muchos sistemas se convertirán a RSA-2048 pronto, lo que se cree que proporciona 112 bits de seguridad. (Fuentes: ¿Qué tamaño de clave se debe utilizar?; Longitud mínima de clave pública RSA: ¿directrices o reglas?)

Si P = NP, entonces nuestras definiciones teóricas de seguridad serían imposibles de lograr. Pero si el algoritmo más rápido para 3SAT tiene un tiempo de ejecución O (n ^ 100), o incluso O (n ^ 10), aún podríamos ser capaces de construir un criptosistema práctico que proporcione una seguridad razonablemente buena.

En el mejor de los casos, nuestra situación podría ser similar a la que enfrentaban las matemáticas a principios del siglo XX, después de que se descubriera que la ingenua teoría de conjuntos conducía a paradojas. Se sacudieron los cimientos de las matemáticas y hubo que construir nuevos cimientos, pero la mayor parte del campo escapó ileso. Si se demuestra que nuestra definición actual de algoritmos eficientes (es decir, que se ejecutan en tiempo polinomial) es igualmente ingenua, desarrollaremos nuevas definiciones de seguridad y reexaminaremos el trabajo realizado en los últimos 40 años. Gran parte podría ser rescatable.

El principal inconveniente sería que nuestras definiciones de seguridad ya no serían tan sólidas. Por ejemplo, las máquinas de pila, las máquinas de Turing y las máquinas de RAM son todas equivalentes a un factor polinomial, por lo que al considerar eficiente cualquier algoritmo de tiempo polinómico, podemos abstraernos de la implementación de la computadora utilizada por nuestro atacante. * Pero si necesitamos para considerar el tiempo de ejecución exacto, nuestra teoría sería mucho menos elegante.

* Una posible excepción a esta regla son las computadoras cuánticas, pero afortunadamente para los criptógrafos, todavía parecen estar a décadas de ser construidas. Para obtener más información, busque el algoritmo de Shor.

Probablemente quisiste preguntar, ¿qué sucede si se demuestra que P = NP? El “problema de P vs. NP” es la cuestión de si P es igual a NP, y se puede resolver probando que este no es el caso. De hecho, la mayoría de la gente cree que este es, con mucho, el resultado más probable.

Otro punto que vale la pena destacar es que es completamente posible que la criptografía de clave pública no exista en absoluto (en el sentido teórico) incluso sin que algo tan devastador como P = NP sea cierto.

Finalmente, como explicó Alok, si P = NP, entonces la criptografía de clave pública es teóricamente imposible, pero en la práctica puede seguir siendo una opción viable en el sentido de que los recursos necesarios para romper una clave pública podrían ser prohibitivos. De hecho, no estar en P no es necesario ni suficiente para que una instancia de un problema sea difícil en la práctica.

Hice un PRNG cripto-seguro no rastreable : ¿podría resolverse el problema P versus NP para 2020? ¿Cuánto progreso se ha hecho al respecto? Entonces la criptografía funcionará bien, pase lo que pase.