Taller de Criptografía - Expediente 1


Eligiendo un tamaño de clave
 


De Schneier@chinet.chinet.com Vie 24 Feb 01:36:23 1995
Newsgroup: sci.crypt
(Comentarios bienvenidos - Bruce)

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.


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.

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.


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:

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.

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


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.


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.

Traducido por Arturo Quirantes Sierra (aquiran arroba ugr.es)
Vuelta a la sección Informes y expedientes