Rompen encriptación RSA de 768 bits

Ya no se puede confiar en nadie

Si pensaban que "asdf" era un password débil, y se sintieron culpables cuando les adivinaron la contraseña, no se preocupen. En realidad, podrían haber elegido algo mucho más complejo y seguirían casi igual de expuestos.

En un paper publicado hace pocos días, un conjunto de investigadores contó que fue capaz de factorizar una llave AES de 768 bits, un algoritmo de llave pública que hoy en día se usa plenamente en la industria.

Como sabrán, porque es obvio y cualquiera lo sabe (en realidad yo no lo sabía, lo reconozco), el principio criptográfico detrás de estas llaves se basa en números enormes que son el producto de dos números primos. La cosa es que si conoces los dos números primos conoces su producto y sabiendo ese número es trivial decodificar los datos encriptados con esa llave.

cryto

Si no conoces los números primos que originan la llave entonces tienes que empezar a probar por fuerza bruta y eso demanda bastante potencia de cálculo. En el paper que mencionamos, esa factorización tomó varios años en un núcleo Opteron de 2.2Ghz. Claro que como los investigadores tenían a su disposición el cluster de la universidad, en realidad se demoraron media hora.

El procedimiento utilizado para factorizar la llave se llama "sieving" (tamizar) y se define como:

Buscar elementos que existan en dos dominios: el conjunto de los números  enteros y el anillo algebraico definido por el polinomio f que se elige al principio. En particular, hay un homomorfismo que cumple con a + b m --> a + b * alpha donde m es una de las raíces de f módulo N, siendo N el número que se quiere factorizar, y alpha una raíz algebraica de f sobre los enteros.

No entiendo lo que traduje y estoy seguro de que Johannes Trithemius se está revolcando en su tumba, pero de todos modos esta prueba de concepto implica que el uso de una llave de 768 bits para encriptar datos ya no es segura, y habría que cambiarse a una de 1024 bits. Esta última será segura todavía por algunos años... o meses, por lo menos.

Link: 768-bit RSA cracked, 1024-bit safe (for now) (Ars Technica)

powered byDisqus