RSA: ¿Cómo funciona este algoritmo de cifrado?

Publicado por Diego Córdoba en

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

rsa
Ronald L. Rivest

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?

rsa
Adi Shamir

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.

rsa
Leonard Adleman

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.

rsa key clave generacion cifrado descifrado

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 este 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 k y z no tengan ningún divisor común más que el 1. 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.
  6. Ahora se calcula la clave privada. Para ello, se elige un número j que verifique la siguiente ecuación (congruencia lineal):
    k*j=1 (mod z)
    En este caso:
    7*j=1 (mod 20), es decir, un valor que verifique que
    7*j)/20 sea una división con resto «1«.
    Esta ecuación de congruencia tiene infinitos resultados. Para trabajar con números chicos en este ejemplo, podríamos decir que 21/20 nos devuelve «algo» con resto 1, por lo que, para este caso particular, (7*j) = 21, de modo que j=3. Esta es la clave privada.

Cifrando un mensaje

Suponiendo que tenemos un mensaje en texto plano (sin cifrar) denotado por P, vamos a cifrarlo utilizando esta ecuación matemática:

P^k = E ( mod n )

Donde:

  • P es el mensaje en texto plano
  • n y k son la clave pública
  • E es el mensaje cifrado

Sustituyendo los valores:

14⁷ = E (mod 33)

Así, elevamos 14 a la potencia de 7, y luego lo dividimos por 33 y calculamos el resto entero. Calculamos la potencia:

14⁷ = 105413504

Ahora dividimos por 33 (n)

105413504 / 33 = 3194348.606

Calculamos el resto entero (nótese el redondeo de decimales)

3194348.606 - 3194348 = 0.606
0.606 * 33 = 19.998 ~ 20

Por lo tanto, E=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.

Puede calcularse de manera más sencilla el texto cifrado utilizando la siguiente ecuación equivalente:

E = P^k mod n

Así, sustituyendo, y suponiendo que en la calculadora que usemos, el módulo se calcule con el operador %, tenemos:

E = (14^7) % 33 = 20

Descifrando el mensaje

Ahora, suponiendo que el destinatario, que sí posee su clave privada, recibe el mensaje cifrado E=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:

E^j = P (mod n)

Esta es la operación de descifrado, donde:

  • E es el mensaje cifrado
  • j la clave privada
  • P el mensaje en texto plano
  • n es parte de la clave pública del destinatario.

Sustituimos los valores:

20³ = P (mod 33)

Calculando:

20³ = 8000

O sea que hay un valor que resulta de dividir a 8000 por 33 (n) y que devuelva P como resto entero de la división. Veamos:

8000/33 = ? con resto P, de modo que calculemos este resto:

8000/33 = 242,242242...

El resultado entero del cociente es:

242*33 = 7986

Por lo que el resto, P, o el mensaje original en texto plano, será

8000-7986 = 14 = P

Como era de esperarse 🙂

Al igual que en el caso anterior, puede calcularse nuevamente el texto plano con la siguiente ecuación equivalente:

P = E^j mod n

Sustituyendo y verificando:

P = 20^3 % 33 = 14

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.

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!


¿Comentarios? ¿Preguntas?

Si queres dejarnos tus comentarios y consultas te esperamos en el grupo de Telegram de la comunidad JuncoTIC!


Diego Córdoba

- Ingeniero en Informática - Mg. Teleinformática - Tesis pendiente - Docente universitario - Investigador