Hoy hablaremos sobre el algoritmo de cifrado asimétrico RSA, sus fundamentos matemáticos, y analizaremos un ejemplo muy sencillo de su funcionamiento interno.

Este artículo forma parte de la Serie sobre Criptografía Aplicada publicada en este blog. Pueden visitar el índice de la serie para acceder a todo el contenido.

El nombre RSA proviene de las iniciales de sus tres creadores, Rivest, Shamir y Adleman, allá por 1997. Se trata de un algoritmo de cifrado asimétrico, o de clave pública, y es uno de los más utilizados en la actualidad. De hecho, la mayor parte de los sitios web hoy integran seguridad SSL/TLS, y permiten la autenticación mediante RSA.

RSA, al ser un cifrador asimétrico, trabaja con dos claves, una pública y una privada. Todo el contenido de texto plano, o contenido sin cifrar, que se haya encriptado con la clave pública, podrá ser descifrado mediante la clave privada, y viceversa, todo contenido cifrado con la clave privada podrá ser descifrado mediante la clave pública.

¿Cual es la necesidad de algoritmos como RSA?

Imaginemos que necesitamos enviar por Internet una dato confidencial, y queremos que solo el destinatario pueda verla. Una forma de hacerlo sería meter la información en una caja fuerte y cerrarla con una determinada combinación. Luego enviamos la caja fuerte al destinatario, y el destinatario podrá ver su contenido siempre y cuando sepa la misma combinación que se utilizó para cerrarla.

Este es el concepto de criptografía simétrica, una sola clave o combinación para abrir la caja. Este esquema tiene un problema: el intercambio de la clave. ¿Cómo hacemos para hacerle llegar la clave al destinatario sin que nadie la vea? Claro está que si el origen le envía una carta simple con la clave al destinatario, cualquiera que pueda interceptar la caja fuerte y la carta en el camino, podrá abrir la caja.

Imaginemos ahora otro escenario. Supongamos que la caja fuerte ahora tiene dos cerraduras, cada una con una llave, una para cerrarla, y otra para abrirla. Supongamos que ninguna llave puede duplicarse solamente teniendo la otra llave, y que la llave que cierra no puede usarse para abrir la caja, ni la llave que abre puede usarse para cerrar la caja.

Supongamos que el destinatario tiene esta caja y nos la envía, junto con la llave para cerrarla, mientras que él se queda con la llave para abrirla. Nosotros podríamos introducir el mensaje en dicha caja, cerrarla con la llave provista, y enviársela al destinatario. Nadie en la ruta podrá abrir la caja puesto que todos los que vieron pasar la caja y la llave, podrán haber duplicado la llave, pero no podrán usarla para abrir la caja, ya que la llave solamente sirve para cerrarla.

Esta es la base de la criptografía asimétrica, y uno de los algoritmos asimétricos más comunes hoy es el algoritmo RSA. Así la criptografía asimétrica elimina uno de los principales problemas de la criptografía simétrica: el intercambio de la clave.

Ahora bien, no todas son rosas para el cifrado asimétrico, también consume más recursos de cómputo, y demora más tiempo en calcularse… pero eso es tema de otro post 🙂

El procedimiento general de generación de claves, cifrado y descifrado utilizando este algoritmo se puede ver en la siguiente imagen. A continuación se detallan los cálculos y se muestra un ejemplo de su funcionamiento.

Generando las claves RSA

Antes de que podamos enviarle un mensaje a alguien más, ese destinatario habrá generado las claves. Veamos, matemáticamente, cómo hace este proceso.

Si lo igualamos a nuestro ejemplo del uso de la caja fuerte, sería equivalente a que el destinatario creara las llaves, una para poder cerrar la caja (llave pública) y otra para poder abrirla (llave privada). Este esquema sirve para lograr el denominado servicio de confidencialidad, pero puede usarse también para lograr autenticidad, aunque excede el tópico de este artículo.

1. Se eligen dos números primos, por ejemplo, p=3 y q=11
2. Calcula el producto n=p*q.
   En nuestro caso: n = 3 * 11 = 33
3. Calcula z=(p-1)*(q-1).
   En nuestro caso: z=( 3 - 1 ) * ( 11 - 1 ) = 20
4. Elige un número primo k, tal que k sea coprimo a z, es decir, que el máximo común divisor de ambos sea 1, esto es: gcd(k,z) = 1 para algún valor de k.
   Tenemos varias opciones en este ejemplo, los valores de k pueden ser 3, 7, 11, 13, 17 o 19. 5 es primo, pero no es coprimo de z puesto que 20 (z) 5 (k) son divisibles por 5.
   Elijamos a k=7, por ejemplo, para simplificarnos los cálculos con un número pequeño.
5. La clave pública va a ser el conjunto de los números (n,k), es decir, (33,7) en nuestro ejemplo. A n se lo conoce como módulo, y a k como el exponente público.
6. Ahora se calcula la clave privada. Para ello, se elige un número j entero, que verifique la siguiente ecuación (congruencia lineal): k*j = 1 (mod z).
   En la práctica esto puede resolverse buscando un j que sea entero, y que verifique j = (1+x*z)/k, para algún valor entero de x.
   Esta ecuación de congruencia tiene infinitos resultados. Podríamos probar para distintos valores de x (1, 2, 3, 4, etc), realizar la operación, y verificar que el resultado, j, sea entero. Para este caso elijamos el caso más sencillo: j=3 para un valor x=1.
   A j se lo conoce como exponente privado.

Cifrando un mensaje

Suponiendo que tenemos un mensaje en texto plano (sin cifrar) denotado por M, y cuyo valor es M=14, vamos a cifrarlo utilizando esta ecuación matemática:

C = M^k mod n

Así, sustituyendo, y suponiendo que en la calculadora que usemos, el módulo se calcule con el operador %, tenemos que el texto cifrado, denotado por C, es:

C = (14^7) % 33 = 20

Por lo tanto, C=20, que es el texto cifrado!

Esto significa que si nuestro mensaje original era el número 14, vamos a enviarle al destinatario el número 20, que es el número 14 cifrado con RSA utilizando la clave pública del destinatario. Cualquier intermediario que «vea» pasar el 20 no podrá obtener, en un tiempo útil (por lo menos hasta ahora) el valor 14 solo disponiendo del 20 y de la clave pública del destinatario, en este caso, n y k.

Descifrando el mensaje

Ahora, suponiendo que el destinatario, que sí posee su clave privada, recibe el mensaje cifrado C=20, ¿cómo hace para obtener el mensaje original? Recordemos que el destinatario tiene a su clave privada j, que en nuestro ejemplo, vale j=3.

Realizamos esta operación matemática:

M = C^j mod n

Sustituyendo y verificando:

M = 20^3 % 33 = 14

Como era de esperarse, obtuvimos el texto plano nuevamente.

Conclusiones

¿Y cómo opera RSA un sistema real?

Exactamente lo mismo que acabamos de ver, con una pequeña diferencia: los números primos tomados son muy grandes, puesto que este es un algoritmo que basa su seguridad en la complejidad computacional. En otra oportunidad profundizaremos sobre este tema.

Implementé una prueba de concepto de este algoritmo en Python, pueden descargar el código desde el repositorio Git de JuncoTIC. Espero pronto escribir el equivalente en lenguaje C 🙂

Debe aclararse que, más allá de los ejemplos simples que se mostraron, RSA es un algoritmo perfectamente seguro en la actualidad, es decir, no existe una computadora ni cluster de alto rendimiento que pueda romper el algoritmo en un tiempo aceptable.

No obstante, no es un algoritmo que pueda resistir al criptoanálisis cuántico, es decir, a un ataque realizado implementando un algoritmo cuántico como el de Shor en una computadora cuántica con cientos o miles de qubits, que además disponga de corrección de errores y un control aceptable del ruido.

En otra oportunidad hablaremos sobre criptografía cuántica y post-cuántica, y de los algoritmos criptográficos que se espera sean utilizados en un futuro no muy lejano 🙂

¡Espero les resulte interesante!