¿Cuáles son las probabilidades de que la NSA haya descifrado el factorización de enteros en el tiempo polinómico?

Answer 1

Casi cero

Snowden cree que la criptografía sólida funciona, y mirando los documentos publicados de Snowden, la NSA está haciendo cosas que no tendrían que hacer si tuvieran un algoritmo de factorización rápido. Por ejemplo, parecen estar aprovechando la intranet interna de Google y Yahoo, y no tendrían que hacer eso si pudieran factorizar grandes números.

Además, está bastante claro que la NSA ha roto efectivamente el RSA-1024 con fuerza bruta, y no gastarían tanto esfuerzo en retrasar el cambio a RSA-2048 si pudieran romper el 2048.

Algo para recordar es

1) si Dios ha decidido que los números enteros no se pueden factorizar en tiempo polinómico, entonces esa es la forma en que es el universo, y no hay nada que la NSA pueda hacer al respecto.
2) si Dios ha decidido que los números enteros * pueden * factorizarse en tiempo polinómico, entonces es algo que la NSA probablemente no pudo mantener en secreto por mucho tiempo. Una vez que mencionas el “truco básico” a un teórico de números, él puede mencionarlo a otra persona, y muy pronto todos lo sabrán. Esto no es como los secretos de las bombas nucleares en los que tienes que hacer un buen trabajo de ingeniería, una vez que le cuentas a un teórico de números el “truco básico” y probablemente puedas escribir eso en un párrafo, pueden descubrir el resto.

Una cosa que hemos encontrado en Snowden es que la NSA es decente para descifrar la criptografía, pero no son muy buenos para guardar secretos.

Answer 2

Personalmente, actúo como si no tuvieran esta capacidad.

Obviamente, si la NSA hubiera resuelto esto, sería uno de los mayores secretos de seguridad nacional de todos los tiempos, por lo que es poco probable que obtengamos una respuesta definitiva a esta respuesta en Quora. Es el tipo de cosas en las que incluso si el código abierto descubriera un método para factorizar enteros, y se generalizara, el hecho de que el USG tuviera esa capacidad durante años antes, y cómo se había utilizado, probablemente permanecería clasificado para las vidas restantes de cualquier político que gobierne durante ese período, y probablemente la mayoría del personal, fácilmente más de 25 años, y tal vez incluso 50-75.

Personalmente, asumo que nadie en el mundo tiene esta capacidad en este momento, y que es poco probable que sea una capacidad pública desarrollada en código abierto en el futuro previsible. Esto se debe a que no creo que la NSA tenga la capacidad y porque, por necesidad, cualquier uso de esa capacidad estaría tan estrictamente controlado que solo se usaría en las circunstancias más extremas. Vimos lo mismo en la Segunda Guerra Mundial con la situación Enigma / Ultra: a menos que se pueda fabricar una historia de portada plausible sobre por qué existía la inteligencia dada, las interceptaciones de Enigma rara vez se podían usar en el campo, por temor a revelar al enemigo que su criptosistema había sido comprometida.

No creo que la NSA dedique una gran cantidad de recursos para tratar de desarrollar esta capacidad: es muy incierto si gastar incluso el 100% del presupuesto de la NSA produciría un buen resultado, y hay tantos ataques de umbral inferior en los sistemas implementados que no sería prudente dedicar recursos al factoring que podrían gastarse en capacidad de ataque activo, inteligencia de señales, romper otros sistemas criptográficos, insertar puertas traseras en sistemas clave, etc.

Obviamente, RSA-512 ya brinda por solo ataques convencionales, y RSA-768 brinda por casi todas las aplicaciones, excepto las claves efímeras de valor extremadamente bajo. RSA-1024 está bien en sistemas ya implementados, pero RSA-2048 (o la fuerza equivalente en ECC u otros sistemas criptográficos) es la opción correcta para la mayoría de las implementaciones actuales, a menos que haya restricciones únicas.