davidruiz.eu/blog

‘
Disclaimer: hoy explicamos cómo y por qué funciona la criptografía asimétrica, que será la que usemos en el siguiente capítulo. Advierto que es inevitable ponerse a contarlo sin resultar un poco plasta, así que este capítulo es totalmente prescindible para aquellos que queráis cifrar vuestros correos pero que no sintáis inquietud por saber cómo funciona el asunto, cuál es la matemática subyacente que hace que se codifiquen, descodifiquen y firmen los correos. Lo escribo, de todas formas, para probar que la explicación existe, y que confiar en la seguridad de lo que viene después no es ningún acto de fe.

Esta semana fue noticia un comunicado de Google donde dice que ha sido objeto de un ataque informático, que pretendía hacerse con un cerro de contraseñas y cambiar reglas de envío y reenvío de correo. A mí me puso los pelos de punta descubrir que Google guarda todas nuestras contraseñas (en lugar de emplear algún algoritmo para descubrir, cuando las tecleamos, si son la correcta, como hace cualquier programa mínimamente seguro). ¿Qué pasaría si el ataque hubiera tenido éxito? ¿Qué pasaría si alguien tuviera acceso a nuestro buzón de correo y pudiera leer lo que hay en él, o escribir en nuestro nombre? Cuando pregunto eso me suelen poner cara de “ya está David con su ataque de paranoia de los viernes”, pero ya lo veis: alguien lo intentó, y nos lo contaron. ¿Y si hubiera tenido éxito? ¿Y si no nos hubiéramos enterado? ¿Y si ni Google se hubiera enterado?

Vamos a seguir con nuestra serie de criptografía. Tras este capítulo y el siguiente, nos va a dar bastante igual que un pirata chino entre a Google y lea nuestro correo: aquello que nos interese no podrá entenderlo, y a aquellos en quienes confiemos no podrá escribirles sin que se den cuenta del fraude.

En criptografía se dice que un sistema de cifrado es de clave simétrica si la misma clave que sirve para cifrar el mensaje sirve para descifrarlo, como sucede en los ejemplos que hemos estado viendo en capítulos anteriores: Alicia quiere mandarle un mensaje a Bernardo, y entonces deben ponerse de acuerdo en la clave y ambos deben disponer de ella.

Eso da unos cuantos problemas. Alicia y Bernardo tienen que ponerse a buscar un medio por el que transmitir la clave de manera segura, lo que puede ser complicado (imaginemos que por ejemplo a Bernardo le envía su empresa a trabajar un mes a Pernanbuco. ¿Qué va a hacer Alicia? Obviamente no va a enviárselo por Gmail). Si Alicia se descuida y alguien descubre su contraseña, obviamente ya no necesita la de Bernardo, porque son la misma. Y lo mismo sucede con Bernardo.

Por eso a mediados del siglo pasado los matemáticos dedicados a esto se pusieron a pensar en sistemas asimétricos, donde Alicia tenga una clave y Bernardo tenga otra. Así surgió por ejemplo el sistema criptográfico RSA, que es del que vamos a hablar hoy (y una variante más simple del que usarán los programas que veremos por fin en el siguiente capítulo de esta oda a la privacidad paranoide).

Antes de nada, hay que decir una obviedad: todo este asunto fue abordado por matemáticos porque a fin de cuentas todo mensaje es traducible a un número. Fue así desde principios del siglo XX (ya vimos que se equiparaban números y letras, y lo mismo era “03 01 03 01″ que “caca”), y más aún desde que la informática se hizo omnipresente: todo archivo es una acumulación de unos y ceros, o sea, de un número binario. Un ordenador entiende la letra ‘a’ como el caracter número 97 de su lista, o lo que es lo mismo, como la cadena de unos y ceros 01000011. Esto implica que un mensaje no deja de ser un número, y una clave otro número. Y en matemáticas ¡sabemos hacer cosas con los números! ¡Si hasta tenemos una rama enterita que se llama Teoría de Números!

El RSA funciona dando a Alicia y a Bernardo un par de claves a cada uno. Una de ellas será pública: Bernardo puede imprimirla y colgarla de la pared de su despacho, publicarla en su página web (la mía, por ejemplo, está en la sección de contacto del blog), incluso enviársela a Clara. La otra es privada, y cada uno debe mantenerla en secreto, y eso incluye al otro: Alicia no necesita saber la clave privada de Bernardo, ni Bernardo necesita la de Alicia.

Entonces cuando Alicia quiere enviarle un mensaje a Bernardo, lo primero que hace es pedirle su clave pública y enviarle la suya. Pueden enviárselas como quieran: por un correo sin cifrar, por carta, en una postal, recitándola por teléfono, gritándosela lo suficientemente fuerte. Entonces Alicia escribe su mensaje, lo cifra utilizando la clave pública de Bernardo, y después lo firma, utilizando su clave privada. Le sale otro número, o texto, o archivo, que es lo que envía a Bernardo. Entonces Bernardo lo descifra utilizando su clave privada, y la clave pública de Alicia, y puede ver el mensaje descifrado. Sabe que es de Alicia porque si no, no podría haberlo leído utilizando la clave pública de ella. Y sólo él puede leerlo (aparte de Alicia, que lo escribió, y que por tanto sabe qué dice) porque nadie más que él tiene su clave privada.

Todo esto funciona gracias a las propiedades de la aritmética modular. ¡Que nadie salga corriendo cuando digo aritmética modular!: no es tan complicado. La aritmética modular lo único que hace es considerar a los números en función de otro, el módulo, e interesarse sólo por el resto que cada número da cuando se lo divide por ese módulo. Ya lo hemos estado haciendo: cuando en el capítulo anterior considerábamos un alfabeto de 26 letras y decíamos que la A era el 1, la B el 2, y así hasta la Z que era el 26, entonces sumar dos Aes daba un 2, o sea una B, y sumar una M (que sería la letra 13) con una Q (la 17ª letra) daría 30, que como solo hay 26 sería como dar la vuelta y quedarnos con la D, que sería la letra número 4, es decir, hemos dividido 30 entre 26, que da 1 y resto 4, y nos hemos quedado con el resto de la división. También hacemos aritmética modular habitualmente con los relojes, porque si sabemos que un reloj marca las 11 y lo miramos 100 horas después marcará las 3, porque 111 entre 12 da 9 y resto 3, porque 111 = 3 + (12 x 9), y con los ángulos, porque sabemos que si tenemos un ángulo de 90º y le sumamos 720º seguimos teniendo un ángulo de 90º, o lo que es lo mismo, que si miramos al frente y damos dos vueltas sobre nosotros mismos, seguiremos mirando hacia el mismo sitio, porque calculamos módulo 360º.

Vamos poco a poco con el método RSA: para generar sus claves pública y privada, Bernardo escoge dos números primos. Pongamos por ejemplo (un poco absurdo porque al final Bernardo no va a escoger números: ya lo hará algún programa criptográfico por él. Y un poco simple porque, bueno, vamos a poner un ejemplo con primos de 2 dígitos, pero luego todo esto funciona con primos de unos 600 dígitos de largo, lo que complicará hasta lo virtualmente imposible la tarea de quien quiera adivinarlos) que escoge los números 43 y 29. Luego los multiplica, y le sale n = pq = 43 x 29 = 1247, y ese será el módulo de sus cuentas. Entonces calcula E = (p – 1) x (q – 1) = 1176, y escoge un número e que esté entre 1 y E y que no tenga divisores comunes con E (es decir, que no sea divisible por ningún número que divida a E). Como 1176 = 7 x 7 x 3 x 2 x 2 x 2, le vale con coger cualquier número que no sea 2, 3 o 7. Pero Bernardo está especialmente perezoso y como no quiere andar haciendo esa cuenta que acabo de hacer yo, se limita a elegir un primo, 19, y ver que 19 no divide a 1176, así que e = 19. Y finalmente calcula el número que multiplicado por e módulo E da 1: esto puede provocar sudores fríos, pero no es tan complicado: es ir multiplicando 19 por si mismo E – 1 veces, y cuando en el transcurso de una de esas multiplicaciones nos sale un número mayor que E lo cambiamos por su resto módulo E. Así obtenemos 619. Y Bernardo construye sus claves con dos pares de números cada una:

clave pública de Bernardo: n = 1247, e = 19
clave privada de Bernardo: n = 1247, d = 619

De la misma manera, Alicia se genera otro par de contraseñas. Partiendo de los números 37 y 53 le sale n = 1961, entonces E = 1872, escoge e = 29, y calcula el inverso de e módulo 1872, que resulta ser 581, de manera que sus propias claves pública serán:

clave pública de Alicia: n’ = 1961, e’ = 29
clave privada de Alicia: n’ = 1961, d’ = 581

Entonces si Alicia quisiera enviar un mensaje que, convertido a número, fuera 97, lo que haría sería calcular 97 elevado a 19 módulo 1247. Eso podría ser un problema si se pusiera a hacer la potencia de la forma habitual y luego dividirla, porque multiplicar 97 por si mismo 19 veces da un número de 38 cifras, pero hay una serie de trucos algebraicos que, al poder deshechar todo lo que es mayor que 1247, permiten hacer fácilmente este tipo de cuentas. Por ejemplo en Haskell la función que estoy utilizando yo para calcular estas potencias para los números de esta explicación tiene esta pinta:

– Como la base elevada a uno da la base:
potenciaMod base 1 modulo = base
– Y si elevamos a algo mayor que uno, es tomar el modulo de multiplicar la base por la potencia elevada al exponente menos uno:
potenciaMod base exponente modulo = (base * (potenciaMod base (exponente – 1) modulo)) `mod` modulo

Lo que escrito en prosa significa que vamos multiplicando la base por sí misma tantas veces como diga el exponente pero que cada vez que nos sale algo mayor que el módulo, seguimos adelante con el resto de lo que nos sale.

Cuando hace la cuenta, a Alicia le sale 833.

Y si Bernardo recibe ese mensaje, repite la operación pero con su clave privada, calcula 833 elevado a 619 módulo 1247, y obtiene el número 97: el mensaje original.

Pero Alicia no ha utilizado nada más que la clave pública de Bernardo: Clara podría cifrar mensajes con ella y mentir diciendo que es Alicia y podría engañar a Bernardo. Es por eso que Alicia firma su mensaje, y eso lo hace utilizando su clave privada, como si estuviese intentando descifrar ella el mensaje: calcula 833 elevado al exponente de su clave privada, 581, módulo el módulo de su calve privada, 1961: sale 355, que es el mensaje que envía.

Cuando Bernardo lo recibe, recibe también un aviso de que está firmado por Alicia, luego lo primero que debe hacer es deshacer la firma de Alicia, y eso lo hace usando la clave pública de ella. Calcula 355 elevado a 29 módulo 1961, y obtiene 833, que es el mensaje cifrado. Entonces lo descifra con su clave privada, elevándolo a 619 módulo 1247, y obtiene 97, el mensaje original.

(Dicho esto, en realidad no suele firmarse así un mensaje cifrado: lo que se hace es generar lo que se llama un hash, una secuencia de números que equivale al mensaje, y comprobar con él que el mensaje no está alterado y que sólo ha podido escribirlo la persona que lo envía. Pero la idea es la misma)

Como para descifrarlo Bernardo ha necesitado la clave pública de Alicia, sabe que ella lo firmó usando su clave privada, y como sólo la conoce ella, sabe así de manera inequívoca que ella escribió el mensaje. Como para descifrarlo necesita su clave privada, tanto él como Alicia saben que sólo él podrá leer el mensaje.

La seguridad del RSA descansa en la complicación de dos problemas matemáticos que se entrelazan: la factorización de números grandes, y encontrar la enésima raíz de un número según un módulo. Si multiplicar dos números es un asunto trivial, descubrir los divisores de un gran número es una tarea terriblemente complicada: para calcularlo hay que ir buscando entre sus divisores (y para complicar el asunto, en nuestros números sólo hay dos divisores) y encontrar uno de ellos. Y estamos hablando de números de 600 cifras (de nuevo hay que hacer malabares para hacernos a la idea de la inmensidad del número: es tan grande que es siete veces más largo que el número de átomos que se estima que hay en el universo observable): la cantidad de divisores es tal que el problema es virtualmente indescifrable.