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

Publicado por Diego Córdoba en

Hoy hablaremos sobre el algoritmo RSA, sus fundamentos matemáticos, y ejemplos prácticos de su uso.

rsa

Ronald L. Rivest

RSA es un algoritmo de cifrado asimétrico, o de clave pública, y es uno de los algoritmos más utilizados en la actualidad. De hecho, la mayor parte de los sitios hoy corren sobre SSL/TLS, y permiten la autenticación mediante cifrado asimétrico basado en RSA.

RSA sirve para cifrar y descifrar información, y por ello también provee servicios de autenticidad y de integridad, mediante lo que se conoce cono Infraestructura de clave pública.

Así es que 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 sea hecho 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.El nombre RSA proviene de las iniciales de los tres creadores, Rivest, Shamir y Adleman, allá por 1997.

¿Cual es la necesidad de algoritmos como RSA?

Imaginemos que necesitamos enviar por In

rsa

Adi Shamir

ternet una información confidencial, y queremos que solo el destinatario pueda verla. Un punto sería el de meter la información en una caja fuerte y cerrarla con una determinada combinación.

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… entonces, qué problema tiene? Básicamente, el intercambio de la clave… cómo hacemos para hacerle llegar la clave al destinatario sin que nadie la sepa… claro está que si el origen le grita la clave al destino, cualquiera que pueda interceptar la caja fuerte en el camino, y que haya escuchado el grito, podrá abrirla, verdad?

Imaginemos ahora otro esquema. Qué ocurriría si el destinatario tiene su caja fuerte con dos llaves, una para cerrarla, y otra para abrirla, y nos envía su caja fuerte abierta junto con su llave para cerrarla.

Nosotros podríamos introducir el mensaje en dicha caja, cerrarla con la llave, y enviársela al destinatario. Nadie en la ruta podrá abrir la caja puesto que, si bien algunos habrán visto la llave para cerrarla, esta llave no sirve para abrirla, y solo el destinatario poseedor de la caja es quien tiene dicha clave.

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.

rsa

Leonard Adleman

Como vemos, 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 🙂

Generando las claves

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 para poder cerrarla (pública) y para poder abrirla (privada).

  1. Se eligen dos números primos, por ejemplo, p=3 y q=11
  2. Calcula 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
    A esta función se la denomina Función Phi o Fi de Euler.
  4. Elige un número primo k, tal que k sea co-primo a z, por ejemplo, z no es divisible por k.
    Tenemos varias opciones aquí, valores de k como pueden ser 7, 11, 13, 17 o 19 son válidos. 5 es primo, pero no es co-primo de k puesto que 20 (z) es divisible por 5.
    Elegimos k=7 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).
  6. Ahora se calcula la clave privada. Para ello, se elige un número j que verifique la siguiente ecuación:
    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».
    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, y no debe ser revelada nunca.

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… manos a la obra:

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 que se comercialicen las computadoras cuánticas xD) el valor 14 solo disponiendo del 20 y de la clave pública del destinatario.

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

🙂

¿Y cómo hace 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.

Los pasos siempre son:

  1. Generar dos números primos muy grandes, p y q
  2. Hacer n=p*q
  3. Calcular z=(p-1)*(q-1)
  4. Elegir un pequeño número k, co-primo de z, de modo que el Máximo Común Divisor entre z y k sea 1, con 1<k<z
  5. Encontrar un número j tal que el (j mod z) sea 1
  6. Publicar k y n como la clave pública.
  7. Guardar j como la clave privada.

Luego, para el cifrado se usan estas expresiones, basadas en los anteriores valores:

mensaje_cifrado = (mensaje_plano)^k mod n

mensaje_plano = (mensaje_cifrado)^j mod n

Cabe aclarar, como mencionábamos arriba, que RSA es un algoritmo muy seguro en nuestros tiempos, pero no es un algoritmo de cifrado que pueda resistir un ataque cuántico. En otra oportunidad hablaremos sobre este tipo de criptografía, y qué algoritmos nos depara el futuro de la seguridad en Internet 🙂

¡Espero les resulte interesante!


Diego Córdoba

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