criptografía - algoritmos criptográficos

criba general del cuerpo de números (del inglés general number field sieve (GNFS) es el más eficiente algoritmo clásico conocido para factorizar enteros mayores de 100 dígitos. Heurísticamente, su complejidad para factorizar un entero n (consistente en log₂ n bits) es de la forma

(en notación L), donde ln es el logaritmo en base e.¹ Es una generalización de la criba especial del cuerpo de números: mientras que el último puede factorizar únicamente números de una cierta forma especial, la criba general del cuerpo de números puede factorizar cualquier número aparte de potencias primas (que es trivial factorizar tomando raíces). Cuando el término en inglés number field sieve (NFS) es usado sin calificación, este se refiere a la criba general del cuerpo de números.

El principio de la criba del cuerpo de números (ambas, especial y general) se puede entender como una mejora de la más simple criba racional o criba cuadrática. Cuando se usan tales algoritmos para factorizar un número grande n, es necesaria la búsqueda de números lisos (i.e. números con factores primos pequeños) de orden n^1/2. El tamaño de esos valores es exponencial en el tamaño de n (véase después). La criba general del cuerpo de números, por otra parte, gestiona la búsqueda de números lisos que sean subexponenciales en el tamaño de n. Puesto que esos números son más pequeños, son más propensos a ser lisos que los números evaludados en los algoritmos anteriores. Esta es la clave de la eficiencia de la criba del cuerpo de números. Con el fin de lograr esta aceleración, la criba del cuerpo de números tiene que realizar los cálculos y factorizaciones en cuerpos numéricos. Esto resulta en muchos aspectos lo más complicado del algoritmo, si lo comparamos con la más simple criba racional.

Nótese que log₂ n es el número de bits en la representación binaria del n, que es el tamaño de la entrada para el algoritmo, así que cualquier elemento de orden n^c para una constante c es exponencial en log n. El tiempo de ejecución de la la criba del cuerpo de números es super-polinomial pero sub-exponencial en el tamaño de la entrada.

Factorizar números grandes es difícil. Desafortunadamente para los diseñadores de algoritmos, se está haciendo más fácil. Peor aún, se está haciendo más fácil de lo que los matemáticos esperaban. En 1976 Richard Guy escribió: "Me sorprendería si alguien factorizara habitualmente números del tamaño 10^80, sin forma especial, en el siglo actual." En 1977 Ron Rivest dijo que factorizar un número de 125 dígitos llevaría 40.000 billones de años. En 1994 se factorizó un número de 129 dígitos. Si hay alguna lección en todo esto, es que hacer predicciones es una tontería.

La Tabla 1 muestra récords en la pasada docena de años. El algoritmo más rápido por aquel entonces era la criba cuadrática.

Tabla 1: factorización usando la criba cuadrática 


Año	nº de dígitos decimales	cuántas veces más difícil
	factorizados	factorizar un número de 512 bits
1983	71	> 20 millones
1985	80	< 2 millones
1988	90	250.000
1989	100	30.000
1993	120	500
1994	129	100

Estos números son algo escalofriantes. Hoy no es raro ver números de 512 bits usados en sistemas operacionales. Factorizarlos, y por tanto comprometer su seguridad, está bien dentro del rango de posibilidades: un gusano durante un fin de semana en Internet podría hacerlo.

La potencia de computación se mide habitualmente en mips-año: un ordenador de un millón de instrucciones por segundo, funcionando durante un año, o unas 3*10^13 instrucciones. Por convención, una máquina de 1 mips es equivalente al DEC VAX 11/780. Por tanto, un mips-año es un VAX 11/780 funcionando durante un año, o su equivalente

La factorización de un número de 71 dígitos requirió 0.1 mips-años; la factorización de un número de 129 dígitos en 1994 requirió 5000. Este incremento dramático en potencia de cómputo resultó fundamentalmente de la introducción de cómputo distribuido, usando el tiempo inerte de una red de estaciones de trabajo. La factorización de 1983 usó 9.5 horas de CPU en un único Cray X-MP; la factorización de 1994 usó el tiempo muerto de 1600 ordenadores a lo largo del mundo durante unos ocho meses. Los métodos modernos de factorización se prestan a esta clase de implementación distribuida.

El cuadro se hace aún peor. Un nuevo algoritmo de factorización ha tomado el relevo de la criba cuadrática: la criba general de campo numérico. En 1989 los matemáticos te hubiesen dicho que la criba general de campo numérico nunca sería práctica. En 1992 te hubiesen dicho que era práctica, pero sólo más rápida que la criba cuadrática para números mayores que unos 130-150 dígitos. Hoy se sabe que es más ráipda que la criba cuadrática para números bien por debajo de 116 dígitos. La criba general de campo numérico puede factorizar un número de 512 bits más de 10 veces más rápido que la criba cuadrática. El algoritmo necesitaría menos de un año en un Intel Paragon de 1800 nodos. La Tabla 2 da el número de mips-año necesarios para factorizar números de diferentes tamaños, dadas las implementaciones actuales de la criba general de campo numérico.

Tabla 2: Factorización usando la criba general de campo numérico 


Nº de bits	mips-año necesarios
512	30.000
768	2*10^8
1024	3*10^11
1280	1*10^14
1536	3*10^16
2048	3*10^20

Y la criba general de campo numérico aún se está haciendo más veloz. Los matemáticos siguen saliendo con nuevos trucos, nuevas optimizaciones, nuevas técnicas. No hay razón para pensar que esta tendencia no continuará. Un algoritmo relacionado, la criba especial de campo numérico, ya puede factorizar números de una cierta forma - números no usados habitualmente en criptografía - mucho más rápidamente que la criba general de campo numérico para números del mismo tamaño. No es irrazonable suponer que la criba general de campo numérico pueda ser optimizada para correr igual de rápido; es posible que la NSA [Agencia de Seguridad Nacional] ya sepa hacerlo. La Tabla 3 da el número de mips-año requeridos para que esta criba especial de campo numérico factorice números de distintas longitudes.

Tabla 3: Factorización usando la criba especial de campo numérico 


Nº de bits	mips-año necesarios
512	< 200
768	100.000
1024	3*10^7
1280	3*10^9
1536	2*10^11
2048	4*10^14

En un "workshop" [reunión de trabajo] del Instituto Europeo de Seguridad en Sistemas, en 1992, los participantes estuvieron de acuerdo en que un módulo de 1024 bits sería suficiente para seguridad a largo plazo hasta el 2002. Sin embargo, advirtieron: "Aunque los participantes de esta reunión se sienten cualificados en sus áreas respectivas, esta declaración (respecto a la seguridad duradera) debe tomarse con precaución." Este es un buen consejo.

El criptógrafo sabio es ultraconservador cuando elige longitudes de claves públicas. Para determinar durante qué longitud de clave necesita, se mira tanto a la seguridad y vida útil pretendida para la clave como al estado de la tecnología de la factorización. Hoy se necesita un número de 1024 bits para obtener el nivel de seguridad que se tenía con una clave de 512 bits a principios de los ochenta. Si quieres que tus claves permanezcan seguras durante 20 años, 1024 bits es probablemente demasiado poco.

Incluso si tus secretos particulares no valen el esfuerzo necesario para factorizar tu módulo, puedes estar en peligro. Imagina un sistema de banca automatizado que use RSA para su seguridad. Mallory puede aparecer en el juicio y decir: "¿Leyó vd. en el periódico, en 1994, que se rompió RSA-129, y que los números de 512 bits pueden ser factorizados por cualquier organización que pueda gastarse unos cuantos millones de dólares y esperar unos meses? Mi banco usa números de 512 bits para su seguridad, y por cierto, yo no hice esas siete transferencias." Incluso si Mallory miente, el juez probablemente exigirá que el banco lo demuestre.

Antes, dije que hacer predicciones era una tontería. Ahora voy a hacer algunas. La Tabla 3 da mis recomendaciones para longitudes de claves públicas, dependiendo de durante cuánto tiempo necesitas que sea segura. Hay tres longitudes de clave para cada año: una segura contra un individuo, una segura contra una gran corporación, y la tercera segura contra un gran gobierno.

He aquí algunas de las suposiciones de los matemáticos que factorizaron RSA-129:

Creemos que podríamos obtener cien mil máquinas sin esfuerzos superhumanos o no éticos. Esto es, no liberaríamos un gusano o virus por Internet para encontrar recursos para nosotros. Muchas organizaciones tienen varios millares de máquinas cada una en la red. Hacer uso de sus instalaciones requeriría una sabia diplomacia, pero no debería ser imposible. Suponiendo potencia media de 5 mips y un año de tiempo, no es demasiado irrazonable embarcarse en un proyecto que requiere medio millón de mips-año.

El proyecto para factorizar el número de 129 dígitos reunió un total estimado del 0.03% del poder total de computación de Internet, y ni siquiera lo intentaron seriamente. No es descabellado suponer que un proyecto con publicidad pudiese reunir 0.1% de la potencia computacional del mundo durante un año.

Supongamos que un criptoanalista dedicado pudiese echar mano a 10.000 mips-año, una gran empresa pudiese conseguir 10^7 mips-año y que un gran gobierno tuviese 10^9 mips-año. Supongamos asimismo que la potencia de computación crecerá en un factor de diez cada cinco años. Y, finalmente, supongamos que los avances en matemáticas de factorización nos permitiesen factorizar números ordinarios a la velocidad de la criba especial de campo numérico. La Tabla 4 recomienda diferentes longitudes de clave para seguridad a lo largo de diferentes años.

Tabla 4: Tamaño recomendado de claves públicas (en bits). 


Año	contra I	contra C	contra G
1995	768	1280	1536
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

Recuerde tener en cuenta el valor de la clave. Las claves públicas se usan frecuentemente para asegurar cosas de gran valor durante mucho tiempo: la clave maestra del banco para un sistema de dinero digital, la clave que el gobierno usa para certificar su pasaporte, la clave de firma digital de un notario. Probablemente no vale la pena pasar meses de tiempo de computación para romper la clave privada de un individuo, pero si puedes imprimir tu propio dinero con una clave rota la idea se hace más atractiva. Una clave de 1024 bits es lo bastante grande como para firmar algo que será verificado en una semana, o mes, o incluso unos cuantos años. Pero no te gustaría estar en un juicio dentro de veinte años con un documento firmado digitalmente, y que el contrario demuestre cómo falsificar documentos con la misma firma.

Hacer predicciones más allá del futuro próximo es aún más tonto. ¿Quién sabe qué clases de avances en computación, interconexión y matemáticas sucederán hacha el 2020? No obstante, si miras al cuadro global, en cada década se pueden factorizar números el doble de largos que en la década pasada. Esto nos lleva a la Tabla 5

Tabla 5: Predicciones de factorización a largo plazo.  Tamaño recomendado de claves públicas (en bits). 


Año	Longitud de clave (en bits)
1995	1024
2005	2048
2015	4096
2025	8192
2035	16384
2045	32768

No todo el mundo está de acuerdo con mis recomendaciones. La NSA manda claves de 512 a 1024 bits para su Digital Signature Standard [Estándar de Firma Digital], bastante menos de lo que yo recomiendo para seguridad a largo plazo. PGP tiene una clave RSA de longitud máxima de 1280 bits. Lenstra, el factorizador más exitoso del mundo, rehúsa hacer predicciones a más de diez años vista. Y la Tabla 6 da las recomendaciones de Ron Rivest, originalmente hechas en 1990, que yo considero demasiado optimistas. Aunque su análisis parece bueno sobre el papel, la historia reciente ilustra que las sorpresas son cosa habitual. Tiene sentido elegir las claves para que sean resistentes contra futuras sorpresas.

Tabla 6: Recomendaciones optimistas de Rivest sobre tamaño de claves (en bits). 


Año	Baja	Media C	Alta
1990	398	515	1289
1995	405	542	1399
2000	422	572	1512
2005	439	602	1628
2010	455	631	1754
2015	472	661	1884
2020	489	677	2017


La estimación baja supone un presupuesto de $25.000, algoritmo de criba cuadrática y un avance tecnológico del 20% anual. La estimación media supone un presupuesto de $25 millones, el algoritmo de criba general de campo numérico y una tecnología que avanza al 33% anual. La estimación alta supone un presupuesto de $25.000 millones, un algoritmo en criba general de campo numérico que corre a la velocidad de la criba especial de campo numérico y un avance tecnológico del 45% anual.

Siempre existe la posibilidad de que un avance en factorización me sorprenda también a mi, pero lo creo improbable. Aunque, ¿por qué deberíais confiar en mí? Acabo de probar mi propia tontería al hacer predicciones.