Ataque académico a tamaños de clave RSA de 768 bits


El algoritmo RSA de criptografía de clave pública se basa en una propiedad de la aritmética modular que hace casi imposible calcular la clave privada a partir de la clave pública, aunque ambas están matemáticamente vinculadas. Un componente común de las dos claves es el valor n que procede de multiplicar dos números primos p y q. Dado que la labor de la factorización de un número en sus componentes primos es crecientemente costosa conforme aumenta el tamaño del número, está claro que los avances matemáticos en técnicas de factorización harán paulatinamente menos seguros los sistemas que empleen tamaños de clave “relativamente” pequeños.

Este es el caso de la noticia que se puede encontrar en varios medios, como El Mundo:

Un grupo internacional de investigadores consiguió descomponer en sus factores primos una cifra de 232 dígitos, un récord que apunta a que relativamente pronto los códigos de seguridad habituales en Internet quedarán caducos.

Así lo informó la Universidad de Bonn, cuyo Instituto de Matemáticas participó en el proyecto.

Los códigos de seguridad habituales en Internet se basan en la dificultad para descomponer grandes cifras en sus factores primos.

“Lo que cualquier estudiante de primaria consigue sin problemas con 21=7×3 resulta casi imposible con cifras lo suficientemente grandes”, explica la universidad a través de un comunicado.

La cifra descompuesta por el grupo de investigadores tiene 768 bits, lo que equivale a decir que tiene 768 dígitos en el sistema de numeración binario que, traspasados al sistema decimal, se convierten en 232 dígitos.

Se considera que una clave de seguridad lo suficientemente segura actualmente debe tener por lo menos 1024 bits.

Para descomponer la cifra de 232 dígitos se utilizó una red de varios ordenadores, ya que según la universidad un solo ordenador normal hubiese necesitado cerca de 2.000 años para conseguirlo.

En el récord conseguido participaron, además de la Universidad de Bonn, el Departamento Federal de Seguridad en la Tecnología Informática, el Centro Wiskunde&Informatika de Holanda y la Escuela Federal Politécnica de Lausanne (Suiza), entre otras instituciones.

El ‘software’ utilizado fue desarrollado en buena parte en el Instituto de Matemáticas de la Universidad de Bonn.

Según el profesor Jens Franke, la descomposición en factores primos de una clave de 1024 bits será claramente más difícil y necesitaría modificaciones importantes en el ‘software’ utilizado.

Sin embargo, Franke considera que antes del final de esta década se logrará por primera vez descifrar una clave de 1024 bits.

Por ello, recomienda, para garantizar un alto nivel de seguridad a largo plazo, empezar a utilizar claves de seguridad de 2048 bits.

Otro artículo, en inglés, con más detalle técnico es el de Ars Technica, de John Timmer:

With the increasing computing power available to even casual users, the security-conscious have had to move on to increasingly robust encryption, lest they find their information vulnerable to brute-force attacks. The latest milestone to fall is 768-bit RSA; in a paper posted on a cryptography preprint server, academic researchers have now announced that they factored one of these keys in early December.

Most modern cryptography relies on single large numbers that are the product of two primes. If you know the numbers, it’s relatively easy to encrypt and decrypt data; if you don’t, finding the numbers by brute force is a big computational challenge. But this challenge gets easier every year as processor speed and efficiency increase, making “secure” a bit of a moving target. The paper describes how the process was done with commodity hardware, albeit lots of it.

Their first step involved sieving, or identifying appropriate integers; that took the equivalent of 1,500 years on one core of a 2.2GHz Opteron; the results occupied about 5TB. Those were then uniqued and processed into a matrix; because of all the previous work, actually using the matrix to factor the RSA value only took a cluster less than half a day. Although most people aren’t going to have access to these sorts of clusters, they represent a trivial amount of computing power for many organizations. As a result, the authors conclude, “The overall effort is sufficiently low that even for short-term protection of data of little value, 768-bit RSA moduli can no longer be recommended.” 1024-bit values should be good for a few years still.

Given that these developments are somewhat inevitable, even the authors sound a bit bored by their report. “There is nothing new to be reported for the square root step, except for the resulting factorization of RSA-768” they write. “Nevertheless, and for the record, we present some of the details.” Still, they manage to have a little fun, in one place referencing a YouTube clip of a Tarantino film following their use of the term “bingo.”

2 pensamientos en “Ataque académico a tamaños de clave RSA de 768 bits

  1. Pingback: Curvas elípticas « Confianza en la red

  2. Pingback: Ataque académico a tamaños de clave RSA de 768 bits | Shadow Security

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s