Del pequeño teorema de Fermat a la navegación en webs seguras

A pesar de ser abogado, Pierre de Fermat mantuvo una intensa actividad como «matemático amateur«. Al igual que con su otra conjetura más famosa, tampoco demostró el teorema del que quiero hablar hoy, alegando en una carta que «te mandaría la demostración si no temiera que es demasiado larga».

Se llama pequeño teorema de Fermat a la siguiente afirmación:

Sea p un número primo y a un entero cualquiera. Entonces, el resto de dividir a elevado a p-1 entre p es igual a 1. Es decir:

a^p-1 mod p= 1

Lo de «x mod y» quiere decir «el resto de dividir x entre y», es una notación común cuando se habla de aritmética modular.

Pues bien, éste teorema (y algo más) sirven para demostrar los fundamentos matemáticos en que se basa la navegación segura en webs hoy día.

Cuando navegamos, estamos viendo páginas, imágenes, etc. que no son más que una sucesión de números. Normalmente, esos números se mandan atravesando diversas redes hasta llegar a nuestro ADSL, Wifi o red 3G, y un navegador las representa en su forma de texto o imagen.

Como dichos datos pasan por muchas redes intermedias, e incluso por el aire si usamos un smartphone o una red Wifi, el acceso a material confidencial o el uso de números de tarjetas de crédito sería muy inseguro si no se usara algún tipo de cifrado.

El cifrado que se usa hoy día para navegación segura se llama RSA (por las siglas de sus inventores Rivest, Shamir y Adleman) y es un algoritmo de clave pública: esto quiere decir que se emplean dos claves:

Clave privada: Usada por el servidor para descifrar datos que se dirijan a él. Es fundamental que esta clave no sea divulgada.
Clave pública: La conoce todo dios, y se usa para cifrar mensajes que, entonces, sólo el que tiene su clave privada correspondiente sabe descifrar.

Es decir, cada clave privada tiene asociado su clave pública compañera. Van en parejas. ¿Por qué no se usan algoritmos de una sola clave? Está claro: si necesitamos enviar algo a un servidor, todo el mundo debería saber su clave, que al ser la misma que la usada para descifrar, no proporcionaría mucha seguridad que digamos.

El funcionamiento de RSA se puede resumir así: para generar un par de claves, lo primero es elegir (al azar) dos números primos muy grandes, p y q. Cuanto más gordos sean mejor, ya que la seguridad del método se basa precisamente en que factorizar números grandes es muy difícil.

Con respecto a las claves (que no son mas que números), llamaremos e a la clave púbica y d a la privada. Primero se escoge un valor para d que sea primo con respecto a (p-1)(q-1), y a partir de él existe una fórmula para calcular un valor de e (clave pública) tal que cumpla:

de = 1 mod (p-1)(q-1)

Ahora entra en juego el mensaje que queremos enviar desde nuestro cliente al servidor. Dicho mensaje informático siempre se podrá representar como un número muy grande (una ristra de 0s y 1s). En este caso, el máximo valor del número será pq pq-1, pero si se necesita enviar algo más grande simplemente se puede trocear y enviar un número más pequeño cada vez.

Llamamos a este mensaje M. Pues bien, RSA se basa en que si el mensaje cifrado C se obtiene elevando el mensaje al número que representa la clave pública y nos quedamos con el resto de dividir entre pq:

C = M^e mod pq

Podemos recuperar el mensaje original volviendo a elevar (de nuevo modularmente con respecto a pq) el mensaje cifrado por la clave privada d:

C^d = M^ed mod pq = M

Vamos a demostrar esto último partiendo del pequeño teorema de Fermat.

Como sabemos (por hipótesis) que

de = 1 mod (p-1)(q-1)

entonces para algún entero k tenemos:

de = 1 + k (p-1)(q-1)

por lo que el mensaje cifrado y descifrado (obviando por ahora la parte modular), es:

C^d = M^ed = M^{1+ k (p-1)(q-1)}

Jugando con el exponente de M:

M^ed = M^{1+ k (p-1)(q-1)} = M · M^{k (p-1)(q-1)}=M · (M^(p-1)(q-1))^k

Aplicamos ahora el pequeño teorema de Fermat, en las formas:

M^p-1 = 1 mod p

M^q-1 = 1 mod q

Para obtener las relaciones:

M^ed = M · (M^(p-1)(q-1))^k= M · (M^(p-1))^k(q-1)= M · (1)^k(q-1)mod p= M mod p

M^ed = M · (M^(p-1)(q-1))^k= M · (M^(q-1))^k(p-1)= M · (1)^k(p-1)mod p= M mod q

, respectivamente.

Ya sólo nos falta aplicar el teorema chino del resto, que nos dice que si el resto de dividir un número entre dos divisores distintos da el mismo resto, entonces obtendríamos el mismo resto al dividir por el producto de los divisores. En notación modular:

Teorema chino del resto: Sean dos primos relativos p y q. Para cualquier entero a que cumpla a = b mod p y a = b mod q, entonces tenemos que a = b mod pq.

Aplicando este resultado a las últimas dos ecuaciones de arriba:

M^ed = M mod pq

, es decir, que elevando (módulo pq) cualquier mensaje a la clave pública (e) y luego a la clave privada (d), obtenemos el mensaje original, quod erat demonstrandum.

Todo esto, y mucho más, es lo que hay detrás de ese icono del candado que aparece en los navegadores cada vez que visitamos una página con un https:// en lugar del inseguro http://.

Para leer (mucho) más: 1 2 3