Notxor tiene un blog

Defenestrando la vida

Algoritmo de cifrado RSA

2022-07-21

Una de las cosas que, de siempre, me han llamado la atención es el cifrado y la criptografía. Pienso que no soy el único y que a la mayoría de la gente le resulta interesante, o al menos el tema les puede parecer curioso. La necesidad que tenemos de ocultar nuestros mensajes a la mirada indiscreta de los demás. No sólo los importantes mensajes de estado, o los juegos de espías, también nuestros asuntos individuales se pueden ver afectados por la necesidad de intimidad. Algo de lo que soy especialmente consciente, cuando trabajo como psicólogo y debo gestionar información muy sensible para las personas que han depositado su confianza en mí. Además, como uno de mis pasatiempos es no dejar que esas curiosidades que me surgen caigan en el vacío, me dio por examinar algún algoritmo de cifrado. Este artículo son las notas que voy tomando sobre el algoritmo RSA. Como sé que este tipo de problemas me pican en la punta de los dedos, estoy seguro de que al final intentaré escribir un programa que codifique y descodifique una cadena, sólo para decir que soy capaz.

RSA

Como dije antes, el algoritmo elegido es el llamado RSA. Que también parece un nombre, un tanto, críptico. En realidad son las iniciales de los apellidos del trío de personas que lo publicaron: Ron Rivest, Adi Shamir y Leonard Adleman, en 1977. Esto fue en el MIT y llegó a ser patentado para esa institución, sin embargo, parece ser que el primero en describirlo fue el matemático Clifford Cocks, en 1973, cuyo trabajo no trascendió porque estaba en un documento interno de una agencia de seguridad inglesa y sólo se conoció la existencia de ese trabajo tras la desclasificación de dicho documento.

El algoritmo se basa en la idea de la dificultad que implica revertir un cálculo. Por ejemplo: si nos dicen que 681.013 es el resultado de multiplicar dos números primos y nos piden que digamos cuáles son, con lápiz y papel... bueno tardaremos, si somos capaces de hacerlo, una infinidad de tiempo más que cuando hacemos directamente la operación \(773 \times 881\). Ir probando cada número primo hasta dar con uno que divida de forma exacta el número dado, a mano, nos llevaría toda una vida. Con el uso de ordenadores, que los hemos fabricado para que cada vez calculen más rápido, la cosa se simplifica un bastante. Por eso, el tamaño de la clave recomendada es de 1024 bits y no de 20, como es en nuestro ejemplo, lo que alarga el proceso de cálculo inverso hasta situarlo en un punto en el que no merece la pena la espera. Según se van acelerando los procesadores hay que elegir claves más largas. Pero al final, la seguridad de una clave dependerá de los recursos que el atacante esté dispuesto a gastar para obtener la información y lo que para él suponga tenerla.

Expresado de otro modo. Es posible que alguien, cuidando de su intimidad, envíe una lista de la compra cifrada a su pareja para que se pase por el super al volver del trabajo. Es posible, que dicha información fuera del agrado de alguna gran corporación de las que viven del BigData, pero ¿les merece la pena pasar meses de cómputo para obtenerla?... El calentamiento global agravado porque gúguel quiere saber que compras garbanzos y bacalao porque vas a perpetrar un potaje... en fin.

Entrando un poco más en materia, de forma matemática, el algoritmo se basa en que es fácil encontrar tres números enteros positivos (grandes), \(e\), \(d\) y \(n\), con \(m\) cumpliendo \(0 \leq m < n\)

\[(m^d)^e \equiv m \quad (mod \: n)\]

Esa equivalencia expresa que si dividimos \((m^d)^e\) por \(n\) obtendremos el mismo resto que si calculamos el resto de \(m / n\). Es decir, lo que se conoce cómo congruencia de módulo. Además, para algunos cálculos es conveniente que ambos exponentes puedan intercambiarse en el orden de cálculo, lo que implica que también debe cumplirse:

\[(m^e)^d \equiv m \quad (mod \: n)\]

Todas estas congruencias se buscan para hacer fácil la codificación y decodificación de los mensajes. De manera que en la clave pública se compartirán el módulo, \(n\) y un exponente, \(e\). De este modo la codificación será la operación:

\[c = m^e \; (mod \: n)\]

donde \(m\) es el mensaje que se quiere transmitir y \(c\) el mismo mensaje codificado.

Para descodificarlo se empleará la clave privada, que contendrá, al menos, el mismo módulo \(n\) y el otro exponente \(d\). El cálculo inverso que se realiza es:

\[m = c^d \; (mod \: n)\]

Es decir, tengo que realizar un cálculo con unos datos y para deshacerlo necesito otros datos. Por tanto, la historia consiste en compartir los datos que realizan el cálculo de cifrado, guardando los de descifrado. En este caso se generan dos claves una pública, la que comparto y otra privada, la que guardo. Puesto que lo que comparto es la parte que sirve para cifrar, podemos poner el símil cerrajero de un candado: lo que envío es un candado y me guardo en el bolsillo la llave que lo abre.

Teniendo más o menos claro cómo funciona, voy a repasar qué necesito implementar para realizarlo:

  1. Necesito calcular el módulo \(n\):
    • Para ello necesito encontrar dos números primos, \(p\) y \(q\), grandes. Deberían seleccionarse al azar y diferir en unos pocos bits para hacer más difícil su factorización.
    • No hace falta decir que hay que mantenerlos en secreto.
  2. Necesito determinar también dos exponentes, \(e\) y \(d\), uno de ellos, \(e\), irá en la clave pública junto con el módulo \(n=p \cdot q\)... Es decir:
    • Clave pública: formada por \(e\) y \(n\)
    • Clave privada: formada por \(d\) y \(n\) 1

Hasta aquí, tengo la sensación de que entiendo todo (pa' lo cortito que soy yo). Claro, que me he saltado toda la parte de las demostraciones matemáticas y confío a ciegas en lo que dicen los matemáticos expertos. ¿Quién soy yo para llevarles la contraria? Además, seguro que yo sería incapaz de hacer ninguna de esas demostraciones, así que, a lo práctico: voy con el algoritmo para encontrar esos cuatro datos que necesito calcular. A ver si no se me complican mucho las cosas (que seguro que sí, o no). En todo caso, los pasos complejos o largos, si lo prefieres expresar así, son la generación de claves. El cifrado y descifrado, teniendo las claves calculadas, son relativamente menos exigentes.

Algoritmo

Viendo las consideraciones anteriores podemos hacernos una idea general de cuál será el algoritmo. Sólo hace falta detallar un poco cómo vamos a calcular según qué parámetros y sobre qué otros algoritmos nos apoyaremos para hacerlo. Otro punto de apoyo serán las recomendaciones PKCS donde tratan de estandarizar las distintas herramientas que utilicen este algoritmo.

  1. Calcular los dos números primos.

    Esto también conlleva bastante complejidad. Determinar si un número es primo o no, la prueba de primalidad, es otro de esos problemas matemáticos que son interesantes. De hecho, existen algoritmos probabilísticos como el de Miller-Rabin, que suele ser el más utilizado en criptografía, o test de primalidad segura como el algoritmo AKS.

  2. Se calcula n, el módulo a partir de los números primos obtenidos en paso anterior. Este es un paso bastante fácil, ya que \(n=p \cdot q\). Ese valor se utilizará tanto para la clave pública como para la privada.
  3. Calcular el mínimo común múltiplo de \(p-1\) y \(q-1\), es decir, calcular \(\lambda(n)=mcm(p-1,q-1)\), puesto que \(\phi(n)=\lambda(n)\) siendo \(p\) y \(q\) primos2.
  4. Escoger \(e\), el primer exponente, de manera que se cumplan las siguientes condiciones:
    • \(1 < e < \lambda(n)\): es decir, un entero mayor que uno y menor que \(\lambda(n)\)
    • \(mcd(e, \lambda(n)) = 1\): es decir, que ambos números, \(\lambda(n)\) y \(e\) deben ser coprimos (no divisibles entre sí).
    • Tener en cuenta que valores pequeños de \(e\) tienen más riesgo de ser descifrados.
  5. Calcular \(d\), el segundo exponente dado que \(d \equiv e^{-1} \; (mod \, \lambda(n))\). Como ya se dijo antes \(d\) es parte de la clave privada y debe mantenerse en secreto.

Con este algoritmo, y en cinco complejos pasos, se puede montar ya un par de claves de cifrado-descifrado para criptografía asimétrica. Las recomendaciones son que en las claves figure la siguiente información:

  • Clave pública:
    • Información obligatoria
      • \(n\): El módulo compuesto por la multiplicación de dos números primos.
      • \(e\): Exponente de cifrado.
    • No se recomienda ninguna otra información adicional.
  • Clave privada:
    • Información obligatoria:
      • \(n\): El módulo. También presente en la clave pública.
      • \(d\): El exponente de descifrado.
    • Información sugerida: Para agilizar cálculos de descifrado se recomienda almacenar también en la clave privada lo siguiente:
      • \(p\): El primer factor primo.
      • \(q\): El segundo factor primo.
      • \(dP\): Un entero positivo tal que \(e \cdot dP \equiv 1 \; (mod \, (p-1))\)
      • \(dQ\): Un entero positivo tal que \(e \cdot dQ \equiv 1 \; (mod \, (q-1))\)
      • \(qInv\): Un entero positivo tal que: \(qInv < p\) y, además, \(q \cdot qInv \equiv 1 \; (mod \, p)\)

De momento no voy a mirar, siquiera, las especificaciones de cómo almacenar esas claves para hacerlas accesibles a otros programas de software. Aunque no descarto que en el futuro no me sea interesante tener mi programita listo para poder intercambiar claves, poder cifrar información mediante una clave generada con gnupg o enviar una clave pública, generada por él y que la pueda utilizar otro software. En la actualidad la prioridad es que funcione. De momento todo es humo que flota en el ambiente.

Conclusión

Como bien podéis ver, no he concluido nada. Sólo he explicado por encima cómo funciona el algoritmo RSA y poco más. Ahora bien, habiendo comprendido en qué consiste, el reto consistirá en implementarlo de aquí en uno o dos artículos. Supongo que, como en todo, el demonio está en los detalles y ya superar el primer paso, el de elegir los números primos es capaz por sí solo de tragarse otro, u otro par artículos. En fin, estoy hablando sobre expectativas, veremos cómo se desarrollan finalmente las cosas.

Así pues, creo que se acerca una de esas series en que me pongo a programar tontás porque me gusta el reto. Ya siento aburriros3, pero algo tendré que hacer este verano.

Footnotes:

1

En la clave privada suelen encontrarse otra serie de datos que facilitan los cálculos de descifrado. En la pública se omiten porque darían demasiadas pistas para poder factorizar la privada. Pero lo veremos más adelante.

3

¡Qué va! No tendré ningún remordimiento en ello ;-)

Categoría: criptografia

Comentarios

Debido a algunos ataques mailintencionados a través de la herramienta de comentarios, he decidido no proporcionar dicha opción en el Blog. Si alguien quiere comentar algo, me puede encontrar en Mastodon y en Diaspora con el nick de Notxor.

También se ha abierto un grupo en Telegram, para usuarios de esa red.

Disculpen las molestias.