RSA

Criptosistemas de clave pública. El cifrado RSA

Criptosistemas de clave pública

Como ya se ha visto en el apartado de introducción a la criptografía, los criptosistemas de clave pública (también llamados criptosistemas asimétricos) se caracterizan por utilizar claves distintas para el cifrado y descifrado de la información. Su principal ventaja es que facilitan el proceso de distribución e intercambio de claves entre los participantes de la comunicación segura, que era un problema importante de los criptosistemas simétricos o de clave privada.

Los algoritmos asimétricos emplean generalmente longitudes de clave mucho mayores que los simétricos, que usan una única clave secreta. Por ejemplo, mientras que para algoritmos simétricos se considera segura una clave de 128 bits, para la mayoría de algoritmos asimétricos (incluido el del RSA), se recomiendan actualmente claves de al menos 1024 bits de longitud. Además, la complejidad de cálculo que comportan los algoritmos de los criptosistemas asimétricos los hace considerablemente más lentos que los algoritmos de cifrado simétricos. Por eso en la práctica los métodos asimétricos se emplean principalmente para codificar la clave de sesión (simétrica) de cada comunicación o transacción particular.

La criptografía basada en criptosistemas de clave pública es relativamente reciente, pues los primeros algoritmos asimétricos aparecen después de 1975. El criptosistema de esta clase más importante y extendido hoy en dia es el RSA, que utiliza la exponenciación modular para cifrar y descifrar y basa su seguridad en la complejidad del problema de la factorización de enteros grandes.

El criptosistema RSA

De entre todos los algoritmos asimétricos, RSA es el más usado y también quizás el más sencillo de entender e implementar. Una peculiaridad de este algoritmo es que sus dos claves sirven indistintamente tanto para cifrar como para autenticar. Debe su nombre a sus tres inventores: Ronald Rivest, Adi Shamir y Leonard Adleman, que publicaron por primera vez el método RSA en 1977. Ha estado bajo patente de los Laboratorios RSA hasta el 20 de septiembre de 2000, por lo que su uso comercial estuvo restringido hasta esa fecha.

RSA, como ya se ha indicado, se basa en la difcultad que presenta la factorización de números grandes. Las claves pública y privada se calculan a partir de un número que se obtiene como producto de dos primos grandes. Un atacante que quiera recuperar un texto claro a partir del criptograma y de la clave pública, tiene que enfrentarse a dicho problema de factorización.

El problema de la factorización de números grandes

Ya conocemos una forma posible de descomponer un número n en sus factores: probar a dividirlo por todos los números enteros positivos comprendidos entre 2 y la raíz de n. Pero cuando hablamos de un número de tamaño 1024 bits, este método es computacionalmente impracticable. Por supuesto, a lo largo del tiempo los matemáticos han inventado otros métodos de factorización más eficientes, pero ninguno ha conseguido un algoritmo con un orden de complejidad que permita factorizar en un tiempo razonable números de tamaños como los empleados en RSA actualmente, aun con la potencia computacional disponible hoy en día.

De hecho el problema de la factorización de enteros se considera que es un problema de clase NP, es decir, un problema para el que existe uno o más algoritmos que lo resuelven, pero ninguno de los algoritmos conocidos se ejecutan en un tiempo polinomial (que pueda ser expresado polinómicamente en función del tamaño de los datos de entrada), y por lo tanto son ineficientes o intratables para datos de entrada muy grandes.

El algoritmo RSA

(1) Generación del par de claves

Para generar un par de claves (KP ; Kp), en primer lugar se eligen aleatoriamente dos números primos grandes, p y q (de unas 200 cifras cada uno, por ejemplo). Después se calcula el producto n = p.q

Escogeremos ahora un número e primo relativo con (p-1) y con (q-1). Este par de números (e,n) pueden ser conocidos por cualquiera, y constituyen la llamada clave pública

e por tanto debe tener un inverso módulo (p-1)(q-1), al que llamamos d. Por supuesto se cumple que ed ≡ 1 mod((p-1)(q-1)), que es lo mismo que decir que ed = 1+k (p-1)(q-1) para algún entero k. La clave privada será el par (d,n). Este número d debe mantenerse secreto y sólo será conocido por el propietario del par de claves.

(2) Cifrado del mensaje con la clave pública

Hay que hacer notar que con este algoritmo los mensajes que se cifran y descifran son números enteros de tamaño menor que n, no letras sueltas como en el caso de los cifrados César o Vigènere.

Para obtener el mensaje cifrado C a partir del mensaje en claro M, se realiza la siguiente operación:
C= Me (mod n)

(3) Descifrado del mensaje con la clave privada

Para recuperar el mensaje original a partir del cifrado se realiza la siguiente operación:
M= Cd (mod n)

Justificación del método

Cd (mod n)= (Me)d (mod n) = M1+k(p-1)(q-1)(mod n) = (M(p-1)(q-1))k.M (mod n) [i]

Si recordamos, la función de Euler φ(n)= (p-1)(q-1), y que en general, salvo azar improbable, se tendrá que mcd(M,p)=mcd(M,q)=mcd(M,n)=1. Y por tanto según el teorema de Euler-Fermat, Mφ(n) ≡ 1 (mod n) ⇒ (M(p-1)(q-1))k ≡ 1 (mod n) [ii]

De [i] y [ii] se obtiene que Cd (mod n) = 1.M (mod n) = M, para 0 < M < n

Conmutatividad del cifrado y descifrado en RSA

Por las propiedades de la exponenciación modular, el cifrado y descifrado son conmutativos:

M = (Me mod n)d mod n = Md.e mod n = (Md mod n)e mod n = M

Esto supone que si cifrando M con la clave pública e y a continuación descifrando el resultado con la privada d obtenemos de nuevo M, también podemos cifrar M con la clave privada d y descifrar el resultado con la clave pública e, volviendo a obtener M.

Esta propiedad es importante porque nos permite utilizar RSA no sólo para cifrar un mensaje, sino también para autenticar el mensaje, como veremos en el tema siguiente.

Criptoanálisis del RSA

Para romper un cifrado RSA, podemos probar varias vías. Aparte de factorizar n, que ya sabemos que es un problema computacionalemente intratable en un tiempo razonable, podríamos intentar calcular φ(n) directamente, o probar por un ataque de fuerza bruta tratando de encontrar la clave privada d, probando sistemáticamente con cada uno de los números posibles del espacio de claves. Ambos ataques son, para n grandes, incluso aún más costosos computacionalmente que la propia factorización de n.

Anterior Arriba Siguiente

‏Source www.dma.fi.upm.es