Supongamos que estoy usando RSA para mi sistema de seguridad. Ahora alguien descubre que encuentra un algoritmo de tiempo polinomial para RSA. Entonces, ¿qué medida se debe tomar para que RSA nunca rompa . Tal vez un gran número de bits utilizados o algo más.
Si se comprueba que P = NP, esto significa que existe un algoritmo de tiempo polinomial para romper RSA . Sin embargo, encontrar ese algoritmo puede ser desafiante. Por otro lado, P podría ser distinto de NP y, sin embargo, la factorización podría aceptar un algoritmo de tiempo polinómico. No se ha demostrado que la factorización de enteros sea un NP-complete problem .
Además, "polinomio" es un comportamiento asintótico, que describe cómo se comporta el tiempo de ejecución de un algoritmo en entradas suficientemente grandes . Nada dice que los tamaños de claves RSA comunes sean "suficientemente grandes" para que el comportamiento asintótico sea una estimación razonablemente precisa del rendimiento en estos tamaños de claves. Finalmente, "polinomio" no significa necesariamente "rápido"; un algoritmo con costo O (n 12 ) (para un módulo RSA de n bits) habría costado 2 120 para una clave RSA de 1024 bits, es decir, totalmente inalcanzable en la práctica.
Ese es el problema con el razonamiento en escenarios hipotéticos mal definidos: cualquier cosa puede pasar, realmente. Por lo tanto, la pregunta no puede ser respondida, excepto por instintos. Mis propias agallas me dicen que si se encuentra un algoritmo de factorización polinomial, entonces probablemente será bastante costoso para tamaños de enteros "normales", y use matemáticas lo suficientemente avanzadas que tendremos unos meses o años antes Aparecen implementaciones prácticas, que deberían dar tiempo suficiente para cambiar a otra cosa (por ejemplo, curvas elípticas). Pero, por supuesto, mis tripas son solo órganos digestivos, buenos para descomponer los alimentos en nutrientes; ¿Qué saben realmente sobre la criptografía?
Lea otras preguntas en las etiquetas cryptography encryption