¿Por qué ECC es más vulnerable que RSA en un mundo post-cuántico?

El desafío actual en la construcción de una computadora cuántica es agregar suficientes "qubits", enredados en un nivel cuántico para Tiempo suficiente. Para romper un módulo RSA de 1024 bits, necesita una computadora cuántica con 1024 qubits. Para romper una curva elíptica de 160 bits, que tiene una "fuerza similar" (con respecto a las computadoras clásicas), necesita algo como 320 qubits. No es que las curvas elípticas sean intrínsecamente más débiles; por el contrario, todavía parecen algo más fuertes que RSA para el mismo "tamaño". Más bien, la relación de resistencia para un tamaño dado no es la misma cuando se consideran las computadoras clásicas en lugar de las computadoras cuánticas.

El factor limitante para un atacante que usa una computadora cuántica es la cantidad de qubits que pueden mantener enredados el tiempo suficiente para realizar un cálculo. Los qubits necesarios para descifrar las claves RSA se estiman en 2 bits, mientras que ECC es aproximadamente 6 • bits, pero las claves RSA son generalmente mucho más largas, por lo que terminan tomando más qubits; aproximadamente 3x en el extremo inferior (2048 vs 224) y 10x en el extremo superior (4096 vs 384) ver nota .

Aquí hay una tabla muy simplificada que compara el número aproximado de qubits necesarios para descifrar la longitud de las claves comunes:

|           RSA       |           ECC       |
| Key Length | qubits | Key Length | qubits |
|------------|--------|------------|--------|
| 1024       | 2048   | 163        | 1000   |
| 2048       | 4096   | 224        | 1300   |
| 3072       | 6144   | 256        | 1500   |
| 4096       | 8192   | 383        | 2300   |
| 15360      | 30720  | 512        | 3000   |

En los últimos 20 años, no hemos descubierto cómo construir una computadora cuántica de pleno derecho con más de un puñado de qubits. Entonces, para comparar cuánto tiempo le tomará a una computadora cuántica descifrar una clave RSA en comparación con una clave ECC "equivalente", básicamente tenemos que asumir que un fabricante descubrirá la decoherencia de una manera que puede ampliarse. Entonces se convierte en una cuestión de qué tan rápido ocurrirá la escalada.

Suponiendo tasas lineales de crecimiento (con 2048 RSA frente a 224 ECC al final y 4096 RS frente a 384 ECC en el extremo alto) RSA obtiene una bonificación de ~ 5-10 años a 500 qubits / año, ~ 3-5 años a 1K qubits / año, y ~ 1.5-3 años a 2K qubits / año.

Si asumimos tasas de crecimiento exponenciales, una vez que podamos descifrar una clave ECC de 224 bits (la clave ECC común más débil) estamos a una generación de descifrar una clave RSA de 4096 bits (la clave RSA común más fuerte). Al ritmo de la ley de Moore (~ 2 años) RSA obtiene una bonificación de ~ 2 años. Aunque la computadora cuántica adiabática de DWAVE no es útil para este tipo de problemas, han sido duplicando su número de qubits aproximadamente cada 4 años .

Entonces, la diferencia es en realidad relativamente pequeña: de 2 a 5 años más tiempo para el avance de la fabricación.

Nota 4096 bit RSA y 383 ECC no son directamente comparables en términos de fuerza de clave simétrica. La clave RSA de 4096 bits es aproximadamente equivalente a una clave simétrica de 142 bits, mientras que una clave ECC de 383 bits es equivalente a una clave simétrica de 192 bits. Los comparo directamente arriba porque son los tamaños de clave más comúnmente compatibles.