¿Cuáles son las posibles amenazas para un algoritmo RSA y cuáles son sus contramedidas?

Una respuesta previa es absolutamente correcta. El algoritmo de Shor es la mayor amenaza para la criptografía RSA según lo veo.

La razón de esto es porque romper RSA se reduce a encontrar los factores primos de un entero grande. Afortunadamente, el problema de factorización tiene una gran cantidad de estructura que es explotable por algoritmos cuánticos. Sin una estructura para explotar, los algoritmos cuánticos en el mejor de los casos tienen algo como una raíz cuadrada, lo que no es lo suficientemente bueno.

El siguiente ejemplo está tomado de Scott Aaronson, los parafrasearé aquí. La estructura que nos interesa se conoce como período de búsqueda.

Considere la secuencia de poderes de dos:
2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 …

Y los poderes de dos mod 15:
2, 4, 8, 1, 2, 4, 8, 1, 2, 4, …
Tenga en cuenta la periodicidad que ha surgido.

Ahora considere el número N, que es un producto de dos primos p y q.
La secuencia
[matemáticas] xmod [N], x ^ 2mod [N], x ^ 3mod [N]… [/ matemáticas]
siempre que x no sea divisible por p o q, esta secuencia termina teniendo cierta periodicidad que divide de manera uniforme (p-1) (q-1).

Ahora, este período es grande. Con una computadora clásica, no ayuda exactamente saber esto porque es posible que tengamos que pasar por algo del orden de N. Pero, con un sistema cuántico, podemos crear alguna superposición de todos los números
[matemáticas] xmod [N], x ^ 2mod [N], x ^ 3mod [N]… [/ matemáticas]
lo que hace que las cosas sean mucho más fáciles por razones que omitiré.

La conclusión es que ahora, en lugar de buscar algunos factores primos súper evasivos, solo necesitamos encontrar la periodicidad de esta secuencia de números, que es una propiedad global y mucho más fácil.

Para más detalles y una continuación, vea el blog de Scott Aaronson, creo que hace un muy buen trabajo.
Shor, lo haré

Desafortunadamente, los sistemas de qubit de última generación residen actualmente en algún lugar cercano a los 9 qubits. ¡Aún no es suficiente para ser un dispositivo eficaz de craqueo RSA! No estoy seguro de si eso califica como una contramedida, pero en teoría podría seguir usando números primos cada vez más grandes para tratar de superar el desarrollo de la computación cuántica. Sin embargo, esa es una batalla perdida, porque el algoritmo de Shor reduce la escalabilidad del problema de factorización. En una computadora clásica, se escala exponencialmente con el tamaño del número en cuestión, pero se convierte en una escala polinómica con el algoritmo cuántico. Es decir, es mucho más fácil ponerse al día. ¿La mejor contramedida en mi opinión? Un nuevo sistema criptográfico, preferiblemente mecánico cuántico.

Una amenaza muy importante para RSA sería una solución a la hipótesis de Riemann. Por lo tanto, no se ha demostrado que una solución exista ni exista. El desarrollo de la hipótesis de Riemann está actualmente relativamente estancado. Sin embargo, si se encontrara una solución, los números primos serían demasiado fáciles de encontrar y RSA se desmoronaría. Sin lugar a dudas, se seguirán desarrollando algoritmos mucho más sofisticados que RSA a medida que los matemáticos descubran más en los campos de la teoría de números y el criptoanálisis.

La comprobación de números primos utilizando el algoritmo de Shor (cuántico). La única contramedida es detener la existencia de una computadora cuántica.