Devin factoriza RSA-260 con GPU por $400 000, 10 veces más barato que el récord anterior

Un investigador de Cognition ha factorizado en números primos el número RSA-260, de 260 dígitos decimales, con la ayuda de agentes Devin. Es un nuevo récord entre los problemas resueltos públicamente del RSA Factoring Challenge: el anterior, RSA-250, se estableció en febrero de 2020. Los cálculos requirieron unos 4 900 GPU-días (13,5 GPU-años) y costaron alrededor de $400 000 a precios de mercado. Según el autor, es 10 veces menos que el nivel público anterior.

El autor subraya que no hay avances algorítmicos. Se utilizó la criba general del cuerpo de números (GNFS), el método conocido más eficiente para números de más de unos 100 dígitos. La base es una versión muy reescrita de CADO-NFS. La mejora, según sus palabras, vino de «la buena y vieja ingeniería de rendimiento» adaptada a la organización de la memoria de las GPU. Tampoco hay ordenador cuántico, y nadie intentó adivinar a mano números primos de 130 dígitos.

De dónde salió la capacidad de cálculo

Los clústeres de Cognition para entrenamiento e inferencia de LLM se componen de racks NVL72, cada uno con 18 ordenadores nominales conectados por NVLink de alta velocidad. El planificador empaqueta las tareas en los racks y siempre queda algún nodo libre: una reserva por si hay fallos, un número impar de máquinas para una tarea que requiere un número par, 17 nodos en lugar de 18. En total, esto supone un porcentaje de un solo dígito de toda la capacidad.

El investigador configuró el planificador para rellenar esos huecos con tareas de un solo nodo y la prioridad más baja. Faltaba una fuente de tareas que pudieran interrumpirse en cualquier momento. La criba por retículas encajaba a la perfección: se paraleliza en miles de millones de pequeñas unidades de trabajo y admite ser desalojada al instante sin riesgo. Todos los récords públicos anteriores de GNFS calculaban esta etapa solo en CPU, porque en GPU estorbaban las ramificaciones y el acceso caótico a la memoria.

Cómo trabajó Devin

El prompt se envió el 13 de agosto a las 0:11:58, hora del Pacífico. La tarea era crear un reemplazo drop-in de la criba en CPU las de CADO-NFS que fuera más rápido que el original. Dos horas después, el autor añadió el requisito de cargar los parámetros de RSA-250 y se fue a dormir. Por la mañana, tras otras siete horas de iteraciones, Devin lo había conseguido.

A continuación, los agentes optimizaron el resto del flujo de trabajo. A lo largo de tres semanas funcionaron de media 3 sesiones en paralelo, con un máximo de 18. El autor revisaba el ciclo una vez cada un par de horas. Devin planteaba por sí mismo los experimentos, ajustaba los parámetros de la criba y del álgebra lineal, depuraba el código y lanzaba los cálculos en el clúster. El autor reconoce que no entiende a fondo las matemáticas y describe su papel como el de fijar prioridades, preparar benchmarks y detectar a tiempo los errores en la dirección del trabajo.

Se reescribieron casi todas las piezas: la versión en GPU de la primera etapa de selección de polinomios, la criba en GPU glas, dup/purge y merge/replay acelerados, una nueva implementación en GPU del algoritmo de Wiedemann por bloques y GPU-sqrt. Solo quedaron intactos cado-nfs.py, polyselect_ropt, makefb y dup1.

Las cifras del proyecto

• En total, unos 4 900 GPU-días, aproximadamente $400 000.
• Selección de polinomios: 643 GPU-días (una cifra anormalmente alta por errores del operador).
• Criba: 3 813 GPU-días.
• Álgebra lineal: 467 GPU-días, de los cuales cerca del 7% se perdió por fallos y por desalojos en favor de tareas más importantes.
• Se obtuvieron 8,3 mil millones de relaciones lineales sobre GF(2).
• El cálculo se ejecutó con unos pocos puntos porcentuales de la capacidad del clúster, sin coste marginal.

Qué pasa con las claves reales

Según el escalado estándar de GNFS, RSA-1024 requiere solo 78 veces más cálculo que RSA-260. El autor estima el coste en unos $30 millones por número y admite que podría reducirse otra mitad con más mejoras. En teoría, los hiperescaladores y los grandes laboratorios de IA pueden permitírselo. Sin embargo, el RSA de 1024 bits se considera obsoleto desde 2013, y las sospechas sobre las capacidades de los servicios de inteligencia se remontan a mediados de la década de 2000.

RSA-2048, el estándar actual, sigue siendo aproximadamente mil millones de veces más difícil que RSA-1024 y este trabajo no lo afecta. Han cambiado tres cosas: el precio, el número de posibles ejecutores (hacen falta GPU, no hardware especializado) y el hecho de que ahora en la optimización de la factorización pueden participar personas que no son criptógrafos.

Qué deben hacer los equipos

Los equipos de seguridad deberían comprobar si queda en su infraestructura alguna clave o certificado de 1024 bits, incluidos los dispositivos embebidos y los servicios internos antiguos. Para ellos, la migración lleva mucho tiempo atrasada. Con las claves de 2048 bits no hay urgencia, pero conviene tener en cuenta este resultado en los modelos de amenazas para datos de larga vida.

Para los equipos de ingeniería e investigación, la conclusión es más amplia. Las tareas de un solo nodo y desalojables pueden aprovechar los restos fragmentados de un clúster. Los agentes autónomos de programación pueden asumir la combinación de teoría especializada y optimización en GPU que antes exigía un equipo de especialistas durante meses.