Podemos convertir cualquier mensaje en un número, por ejemplo, asignándole un código de dos dígitos a cada letra y haciendo una cadena con esos números. La forma más sencilla sería sustituir las letras así: A = 01, B = 02, etc.
Esta sería una forma válida de encriptar un mensaje.
La encriptación de mensajes existe desde al menos la época de los romanos, de hecho se llama cifrado Cesar al tipo de cifrado que consiste en reemplazar cada letra del texto original, por otra letra que se encuentra un número fijo de posiciones más adelante en el alfabeto. Por ejemplo, si fijamos las posiciones en 4, la «A» del mensaje original sería sustituida por la «E», la «B» por la «F», etc. Esta forma de cifrado es el que utilizaba Julio Cesar para enviar mensajes cifrados.
A esto es a lo que se llama encriptación simétrica, la misma clave sirve tanto para encriptar como para desencriptar.
El problema de este tipo de cifrado es cómo hacer llegar al destinatario la clave.
Se ve muy claro si imaginamos una caja fuerte que contiene el mensaje que queremos enviar, si introducimos el mensaje en la caja y esta, la cerramos con llave, el destinatario podrá leer el mensaje si tiene la llave que abre la caja. El problema es hacer llegar la llave al destinatario.
¿Y qué pasa si la caja fuerte tiene dos llaves?, una llave que solo sirva para abrir la caja fuerte y otra llave que solo sirva para cerrarla. Podemos enviar la caja fuerte abierta con la llave para cerrarla y decirle al «emisor» del mensaje, que introduzca el mensaje en la caja fuerte y la cierre con la llave que ha recibido y me envíe la caja. Solo el destinatario tiene la llave que abre la caja y aunque en el camino nos copiasen la llave que hemos enviado, no valdría para nada porque esa llave solo sirve para cerrar la caja, pero no para abrirla. En esto consiste la encriptación asimétrica. Es decir, o dicho de otra forma, lo bueno de la criptografía asimétrica está en el hecho de que hay pares de operaciones matemáticas en las que una es la opuesta de la otra y que una es muy sencilla y la otra es muy complicada. Veámoslo con un ejemplo:
Multiplicar dos números primos es una operación muy sencilla, pero si nos dan un número del cual sabemos que es el producto de dos primos, descomponer/factorizar dicho número, para encontrar los dos primos originales es una operación bastante complicada si estos dos números son realmente grandes -más de 700 dígitos cada uno-, entendiendo por complicada que requiere mucho tiempo de cálculo con los ordenadores actuales. Algo parecido a mezclar sal y azucar, hacerlo es fácil, pero deshacerlo ya…
Con la criptografía asimétrica, podemos enviarle un mensaje a alguien conociendo el valor del producto de dos números primos, pero para descifrarlo tendríamos que conocer cuáles son esos dos primos.
El algoritmo más famoso y común hoy en día que utiliza encriptación asimétrica para encriptar mensajes es el algoritmo RSA. Este algoritmo fue inventado por Ted Rivest, Adi Shamir y Leonard Adleman en 1978 y elimina el principal problema de la encriptación simétrica, que es el intercambio de la clave.
Matemáticamente hablando, este algoritmo utiliza números primos muy grandes para poder generar las llaves/claves. Estamos hablando de números primos realmente grandes de por ejemplo 100 dígitos. Veamos cómo funciona.
Encriptar es una forma de convertir un mensaje dado en otro mensaje. Como cualquier mensaje hemos visto que lo podemos convertir en un número, encriptar puede pensarse como un modo de convertir un número dado en otro número.
Para ello vamos a utilizar dos números primos muy, pero que muy grandes.
Elegimos dos números primos $p$ y $q$ y los multiplicamos $p\cdot q=n$. El método público para codificar el mensaje convertirá a este (al mensaje) en un número y luego hará un cálculo basado en el número $n$.
Si no decimos públicamente qué es $p$ o $q$, no se podrá decodificar el mensaje, a menos que puedan averiguar el valor de $p$ o $q$. Pero eso requiere factorizar $p\cdot q$, un número de al menos doscientos dígitos y hoy eso es imposible incluso con el ordenador más potente del mundo. De momento y hasta la llegada de los ordenadores cuánticos, no hay nada que hacer.
Siguiendo con el símil de la caja fuerte ya que es muy gráfico, el destinatario es el que tiene que crear las dos llaves, una para poder cerrarla (pública) y otra para poder abrirla (privada).
Para entenderlo, vamos a utilizar dos números primos pequeños.
Escogemos, por ejemplo, $p=3$ y $q=11$
Calculamos $n= p \cdot q$, en nuestro caso $n= p \cdot q =3 \cdot 11=33$
Calculamos $s=(p-1) \cdot (q-1)$ (función phi de Euler).
$s=(3-1) \cdot (11-1)=20$
Escojamos un número $k$ entre 1 y $s$ que no tenga ningún factor común con $s$, i.e, que sea coprimo con $s$. Podemos encontrar los factores comunes de dos números utilizando el «algoritmo de Euclides». Benditas matemáticas…
Tenemos varias opciones, valores de $k$ como pueden ser 7, 11, 13, 17 o 19 nos valen. 5 es primo, pero no es co-primo de $k$ puesto que 20 es divisible por 5. El 3 también valdría, pero no lo vamos a escoger por coincidir con $p$, de forma que compliquemos un poco más las cosas.
Elegimos $k=7$ (si eligiésemos el 19 sería aún mejor para complicar los cálculos a los hackers).
La «clave pública» va a ser la dupla $(n,k)$, es decir (33,7).
La aritmética modular nos dice que existe un único número $j$ entre 1 y $s$ para el cual el producto $j \cdot k$ deja un resto 1 en la división entre $s$. Esto es $j \cdot k$ mod $s = 1$. Calculamos este número j. Mantenemos p, q, s y j en secreto y designamos a $j$ como la «clave privada».
En nuestro caso, tendríamos que encontrar j tal que
$k \cdot j$ mod $s= 1$, es decir, $7 \cdot j$ mod $20 =1$, dicho de una forma más sencilla, busquemos j tal que $\frac{7 \cdot j}{20}$ sea una división con resto 1.
Como estamos trabajando con números tan pequeños, se ve fácilmente que $\frac{21}{20}$ tiene resto 1, por lo que, para este caso particular, $7 \cdot j = 21$, de modo que $j=3$.
$j=3$ es la «clave privada».
Para encriptar un mensaje, primero lo pondríamos como un número m (mensaje), ya vimos al principio de este artículo como podíamos hacerlo. Luego calculamos $c ≡ m^k$ mod $n$. Este (el número $c$) es el mensaje codificado que enviaríamos al destinatario.
$mensajeCodificado = (mensajePlanoConvertidoEnNúmero)^k$ mod $n$
El destinatario, como conoce la clave privada j, puede decodificar el mensaje calculando $c^j$ mod $n$. Un teorema de teoría de números que es una pequeña extensión del teorema de Fermat, nos dice que el resultado es el mismo que en el mensaje original $m$.
$mensajePlanoConvertidoEnNúmero = (mensajeCodificado)^j$ mod $n$
Si alguien intentara decodificar el mensaje, tendría que averiguar j, sin saber s. Esto se reduce a conocer p – 1 y q – 1 o, lo que es lo mismo, p y q. Para ello tendría que factorizar n lo cual es francamente difícil.
Veamos un ejemplo práctico:
Tenemos un mensaje que como ya hemos comentado, se puede transformar en un numero, en un número por fila, palabra,… como queramos. Al final tenemos un número o muchos números, supongamos que solo uno para hacerlo fácil. Supongamos que queremos enviar un mensaje de una única letra, la N y a esta letra le corresponde el número 18, la relación de cada letra con un número es público para que el que va a encriptar pueda hacerlo sin problema. Es decir:
Sea el mensaje m=18
El mensaje codificado sería mensajeCodificado=$18^7$ mod 33 = 6
Partiendo del mensaje 18, lo que enviaríamos al destinatario es un 6.
El destinatario lo decodifica así m= $c^j$ mod $n$, es decir $6^3$ mod $33=$ 18.
Ya fuera del tema de esta entrada y por estar relacionado con el envío de información, me parece interesante comentar que cuando se transmiten mensajes, estos pueden llegar incorrectamente por mil motivos. Supongamos que queremos enviar un mensaje a una nave espacial, de manera que 1 signifique que aterrice en Marte y 0 que no aterrice y continúe.
Si nos equivocásemos y enviásemos un 0, habríamos cometido un grave error. Compliquemos entonces el mensaje un poco más. Enviemos 11 para indicar aterrizar y 00 para indicar continuar viaje. Claro, aquí si la nave recibe un 01 sabría que había habido un error, pero no sabría si el mensaje era un 00 o un 11.
Si el código es un poco más largo la cosa mejora, si codificamos el mensaje aterrizar en marte como 111 y no aterrizar y continuar como 000, si la nave recibe 001, se podríadetectar y corregir el error sobreentendiendo que se quería haber transmitido 000 y se ha cometido un error -sobreentender que el mensaje bueno es 111 implica que en el mensaje hay dos errores.
Esta misma idea es la que utilizan los correctores de texto para autocorregir palabras y saber que cuando escribimos «iglisia» realmente queremos decir «iglesia».
Juanjo Bravo