Matemáticas | AmarellOcio

Archive for the 'Matemáticas' Category

Desmitificando RSA de 1025 bits

Damián Marzo 13th, 2009

Cuando se habla de RSA, se suele especular o fantasear sobre supuesta tecnología ultrasecreta que pudieran tener las agencias de seguridad de los gobiernos de naciones poderosas como Rusia, China o EEUU. Sobre todo se especula que los módulos de 1024 bits podría ya ser factorizables en tiempos razonables. Por lo que muchos, incluyéndome, se preguntan ¿entonces de cuántos bits debería generar mis llaves si mis temores fueran ciertos?

El NIST, la agencia encargada de definir los estándares tecnológicos para las agencias federales de EEUU, establece que la información con vigencia menor a 2010 debe usar al menos 1024 bits, con vigencia menor a 2030 deberá usar al menos 2048 bits y con vigencia mayor a 2030 deberá usar 3072.

Bruce Scheiner por otro lado en 2002 ratificó una tabla publicada anteriormente por él mismo en donde establece los bits recomendados según seas un individuo, una corporación o el gobierno. Ahí estipula que para 2005 los individuos ya deberían usar llaves de 1280 bits, y el gobierno ya debería estar usando 2048 bits.

Algunos más “inteligentes” que los anteriores, dicen que todos exageran, y recomiendan 1025 bits, razonando superfluamente que eso duplica la complejidad de la factorización. Ese razonamieto surge de pensar que el mejor algoritmo de factorización es por “fuerza bruta” sobre los posibles factores, probando todos los números entre $2^{511}$ y $2^{512}-1$ para factorizar un módulo de 1024 bits, pues sus factores primos son de 512 bits.

La realidad es otra, y desde hace tiempo, desde Fermat de hecho, existen métodos sublineales de factorización de enteros respecto al tamaño del entero y los mismos algoritmos son subexponenciales respecto al número de bits del entero. Por lo que aumentar un bit la llave no es tan drástico como aumentarlo en otros algoritmos como AES, como no es tan drástico multiplicar por dos el tamaño del entero, pues eso no duplicaría el tiempo necesariamente. ¿Pero qué tanto aumenta el tiempo un bit más?

Criba General de Campos Numéricos (GNFS)

GNFS es el mejor algoritmo de factorización de enteros, conocido a la fecha, para enteros de 130 digitos al menos (que son aproximadamente 432 bits). En 2005 el algoritmo se utilizó para romper el récord de factorización RSA para un entero de 640 bits, hazaña que fue llevada acabo por un equipo de investigación alemán. Lo interesante de este algoritmo es su complejidad, y en base a ella voy a realizar algunos cálculos para esclarecer qué tan fuerte es aumentar un bit más a un módulo RSA.

La complejidad del algoritmo está dada por

$O\left(\displaystyle e^{\displaystyle \left(c+o(1)\right)ln (n)^{1/3}ln(ln(n))^{2/3} }\right)$

donde $c$ es una constante dada por la heurística utilizada en el algoritmo y $n$ es el número a factorizar (no los bits del número). Carl Pomerance, creador del segundo mejor método de factorización, indica que en este caso $c = \left( {\frac{64}{9}}\right)^{1/3}$ . Por otro lado tenemos que $o(1)$ es una función asintótica que tiende a cero, por lo que para los cálculos se va a considerar como cero, pues Pomerance así lo toma.

Teniendo eso, lo que se puede hacer ahora es calcular el tiempo del algoritmo para factorizar un número de 1024 bits y comprarlo respecto al tiempo para factorizar uno de 1025 bits. Por lo que vamos a denotar $T_{1024}$ al tiempo de 1024 bits y $T_{1025}$ al tiempo de 1025 bits.

Sabemos que un número de 1024 bits se aproxima a $2^{1024}$ y uno de 1025 bits a $2^{1025}$ , por lo que se van a tomar esas aproximaciones para simplificar la exponenciación. Tenemos entonces que

$\displaystyle\dfrac{\displaystyle T_{1025}}{\displaystyle T_{1024}} = \displaystyle\dfrac {k e^{\displaystyle c (ln (2^{1025})^{1/3}ln(ln(2^{1025}))^{2/3}) } } {k e^{\displaystyle c (ln (2^{1024})^{1/3}ln(ln(2^{1024}))^{2/3}) }}$

donde $k$ es la constante de la notación asintótica.

Por lo tanto tenemos que

$\frac{T_{1025}}{T_{1024}} = 1.0259$

Que es muy poco. Pues si el gobierno de algún país contara con los recursos para romper un módulo de 1024 bits en 24 semanas (6 meses), entonces romper uno de 1025 bits les llevaría casi 25 semanas. Esto en el mejor caso, puesto que la complejidad del algoritmo está dada en notación O, así que el algoritmo podría comportarse aún mejor de lo estimado y ser más rápido.

Si hacemos lo mismo y comparamos un módulo de 1024 respecto a uno de 1280, tenemos que $\frac{T_{1280}}{T_{1024}} = 447.43$ . Que es bastante decente, y suponiendo que se pudiera factorizar el módulo de 1024 en una semana, entonces tardarían 8 años y medio en factorizar el de 1280; lo que le da bastante más confiabilidad a ese módulo que a uno de 1025. Aunque un cálculo más correcto sería considerando una ecuación diferencial porque la capacidad de cálculo no va a permanecer 8 años igual, va a ir aumentando.

Pragmáticamente hablando

Seguramente alguno va a desconfiar de este análisis, y necesitará una prueba más terrenal, sin tanta matemática. En ese caso lo invito a bajar un paquete que tenga implementado el algoritmo y factorice un número de unos 450 bits, que se puede hacer en un tiempo bastante decente (unos minutos) y vaya aumentando de bit en bit, para comparar los tiempos. Implementaciones hay varias y se pueden encontrar en la página de la wikipedia sobre GNFS.

¿Cómo se calcula numéricamente sen(x) o ln(x)?

Damián Diciembre 15th, 2007

¿Nunca se han preguntado cómo es que la calculadora puede darles el valor de sen(x) o arctan(x) para todos los valores que le metan? ¿Acaso tiene una tabla de todos los valores? (Obviamente no). En este post voy a presentarles herramienta matemática interesante y reveladora, que ilustra cómo se aproximan funciones que no se pueden calcular con operaciones elementales (suma, multiplicación, división, resta).

Crackeando un candado de combinación

Eduardo Febrero 20th, 2007

Éste video me ha dejado bastante interesado en el asunto, pues sería buen saber como es que logró llegar a hacer eso, me imagino que debe haber toda una teoría matemática que lo respalde.

How To Crack A Combination Lock – video powered by Metacafe

General , Matemáticas , Videos
Comments(1)

La foto más famosa de la ciencia

Paco Febrero 17th, 2007

En ésta foto aparecen muchos de los más grandes científicos que han existido, muchos de ellos ganadores de premios Nobel.

Square-And-Multiply

Damián Enero 18th, 2007

Seguramente a estas alturas ya les habrán pedido que programen la exponenciación entera de un número para ilustrarles algunas estructuras de control, pero es muy probable que no se hayan preguntado cómo se podría hacer más eficiente una exponenciación o de plano pensaron que es lo mejor que se puede hacer (hacer todas y cada una de las multiplicaciones).

Aqui les voy a exponer un método sencillo y muy usado para exponenciar en grande de una manera más eficiente.

Una historia de matemáticas y matemáticos

Damián Diciembre 23rd, 2006

Casi al terminar de leer un libro titulado: “El Teorema del Loro” de Denis Guedj, encontré un párrafo que me dejó pensando largo tiempo en porqué me había fascinado tanto ese libro aunque lo que se enseñaba ahí sobre matemática era ya conocido por mi. El párrafo dice:

El Factorial Continuo

Damián Noviembre 23rd, 2006

$fractal.jpg$ Como todos sabemos el factorial de un número está definido para números naturales, pero seguramente se habrán preguntado ¿qué pasa si yo quiero el factorial de un número real positivo? Pues…

Un niño de 10 años dedujo la progresión aritmética

Eduardo Noviembre 22nd, 2006

Cuenta la leyenda que cuando un matemático llamado Gauss tenía 10 años era muy inquieto en la clase, entonces un día su maestra le dijo: “quiero que me sumes los 100 primeros numeros naturales y me des el resultado”, ésto para que estuviera un poco más tranquilo, y el pequeño Gauss pensó en lo siguente: