Si combina todos los microprocesadores de la Tierra en un grupo de cómputo gigantesco, ¿qué tamaño de claves RSA podrían tener en cuenta en un tiempo razonable (digamos unos años)?
Sé por leer las respuestas a esto pregunta que el próximo objetivo en la vida real es 1024 bits, pero aquí me interesan más las respuestas puramente teóricas.
El registro actual de ruptura de RSA es de 768 bits. El único algoritmo conocido que es lo suficientemente eficiente como para poder visualizar estos tamaños de clave es el Tamiz de campo de número general . Este algoritmo consta de dos grandes partes, el tamizado y luego un poco de álgebra lineal.
Cuando GNFS se utilizó por primera vez para descifrar una clave RSA de 512 bits, el tamizado fue el cuello de botella; requiere muchas máquinas con cantidades de RAM que no eran triviales en ese momento. Sin embargo, para claves más grandes, es el álgebra lineal el que se convierte en el cuello de botella, porque no es fácil de paralelizar, y requiere una computadora realmente grande con mucho ( mucho ) de rápido ( muy rápido ) RAM.
Con todas las computadoras en la Tierra, podrías hacer el tamizado para un esfuerzo de factorización de 1024 bits; todo lo que se necesita son algunos miles de computadoras con unas pocas docenas de gigabytes de RAM cada una. Sin embargo, para el álgebra lineal correspondiente, todas estas computadoras equivaldrían a nada. En su lugar, tiene que construir una nueva computadora de propósito especial con una nueva arquitectura.
Por ejemplo, considere las las supercomputadoras más grandes que existen . Todos son acumuladores de muchos microprocesadores, son supercomputadoras orientadas a la CPU, muy buenas para realizar cálculos numéricos en tareas que pueden realizarse de forma paralela (muchos cálculos por unidad de transferencia de datos). Para la segunda mitad de GNFS, necesita un supercomputador orientado a RAM, mejor en las transferencias de datos entre la CPU que en los cálculos reales. Se ha estudiado la arquitectura teórica para una computadora de este tipo, y tenemos algunas buenas razones para creer que es tecnológicamente viable, pero aún sería un esfuerzo muy importante, comenzando justo en el paso de la fundición de chips.
Resumen: incluso con una red de bots que controla todas las computadoras de la Tierra, no rompería una clave RSA de 1024 bits. Con todo el efectivo de Apple, probablemente podría construir una máquina de propósito especial que pueda descifrar una clave RSA de 1024 bits (pero buena suerte al hacerlo discretamente : no puede gastar miles de millones de dólares sin aparecer, al menos, en estadísticas económicas). Para teclas más grandes (por ejemplo, 1536 bits o más): ni lo pienses.
Lea otras preguntas en las etiquetas brute-force rsa asymmetric distributed-computing