Primos muy grandes y encriptación de mensajes

Tratar de hallar números grandes, a pesar de ser una tarea de gran dificultad (nos referimos a números de, por ejemplo, 200 cifras), no parece a primera vista que tenga aplicaciones inmediatas para nuestra vida cotidiana. Pero, como sucede a menudo con las matemáticas, las apariencias engañan. En efecto, en la actualidad, el problema de la factorización (descomposición de un número en producto de otros) se utiliza para resolver el problema de la seguridad de los datos mandados a través de la red. Empecemos por un rápido recorrido por la larga historia de los números primos y la factorización, ya desarrollada por los antiguos griegos.

Mientras la infinitud de los números primos ya fue demostrada por Euclides en sus Elementos, los métodos para determinar si un número grande es primo o no han ido evolucionando lentamente desde entonces hasta nuestros días, con un cambio radical con la aparición de los ordenadores. En la escuela aprendimos el método llamado criba de Eratóstenes, en recuerdo del director del Museo de Alejandría, que fue contemporáneo de Euclides. Según este método, para saber si un número es primo es suficiente ver que no es divisible por ninguno de los primos menores que la raíz cuadrada del número en cuestión. Sin embargo, este sencillo y transparente método es muy poco útil, por no decir totalmente inútil cuando tenemos un número grande. Xavier Xarles afirma que el número de cálculos necesarios al aplicar la criba de Eratóstenes, para comprobar si un número de 50 cifras es primo, en el caso que lo sea, es superior a todos los cálculos realizados hasta hoy por toda la humanidad.

En realidad, lo que el método anterior hace es tratar de hallar un divisor de un número, de modo que si esto ocurre el número es compuesto, y si no, es primo. En cierto modo el método permite factorizar un número, algo que, desde el punto de vista de los cómputos, todavía es más complejo que la determinación de la primalidad. Entonces el problema consiste en tratar de determinar si un número es primo sin tener que factorizarlo y para ello, curiosamente, lo que constatamos es que es posible hacerlo para hallar si un número es compuesto. Seguramente la primera propiedad en este sentido fue la dada por Fermat, que podemos enunciar de esta manera:

Así, para determinar si un número n es compuesto, podemos elegir un número a no divisible por n y ver si a^p-1 – 1 es o no divisible por n. Un caso particular sería: si un número impar n no es un divisor de 2^n-1 –1, entonces n es compuesto. Esto sirve para detectar compuestos pero no para detectar primos, en el sentido que si no cumple la propiedad aún podría ser compuesto (por ejemplo, para n = 341, resulta que n divide a 2^n-1 – 1, pero es compuesto: 341 = 11 · 31).

Para ver si un número grande es divisible (o no) por otro menor, utilizamos las congruencias (o clases de restos módulo n), en concreto el hecho de que el resto de dividir una suma (o un producto) por n, es igual a la suma (o al producto) de los restos de dividir cada número por n. Esto permite ampliar el pequeño teorema de Fermat que puede formularse así:


Esto significa que existe un elemento tal que todos los elementos del grupo son una potencia de aquel. Además, los únicos elementos cuyo cuadrado es 1, son +1 y -1.

Podemos preguntarnos si es posible saber con cierta rapidez si 2^n-1 – 1 es divisible por n y la respuesta no sólo es afirmativa sino que existe un método para hallarlo.

La cuestión de la “rapidez” para números muy grandes nos lleva hablar de los distintos tipos de algoritmos. Así, tenemos algoritmos lineales, o más en general polinómicos, y algoritmos exponenciales. La diferencia entre ellos depende de cómo aumenta el número de operaciones elementales a realizar, cuando aumenta el número. En los algoritmos lineales el número de operaciones está acotado por el número de cifras de n; de manera análoga, en los polinómicos la cota es un polinomio que también depende del número de cifras de n, mientras que en los exponenciales, la cota depende de n y por lo tanto es una función exponencial con respecto a las cifras de n.

En 1979, Rivest, Shamir y Adleman desarrollaron el primer sistema para encriptar mensajes, dentro de los conocidos como sistemas criptográficos de clave pública, llamado RSA, letras iniciales del apellido de sus creadores. Aún en la actualidad este método sigue siendo el más utilizado de entre los algoritmos para encriptar mensajes.

En cualquier sistema de clave pública, cada usuario dispone de dos claves: una pública y otra privada. Cuando se quiere enviar un mensaje, el emisor busca la clave pública del receptor, cifra su mensaje con esa clave, y una vez que el mensaje cifrado llega al receptor, este puede descifrarlo utilizando su clave privada.

El funcionamiento del método de encriptación RSA, y en particular aquello que lo hace seguro, se basa en la dificultad para determinar si un número entero muy grande es primo o compuesto, en particular en los casos que este número es el producto de dos primos muy grandes. De acuerdo con esto, se eligen dos primos muy grandes al azar y se multiplican obteniendo un número compuesto que es la clave pública del sistema, mientras que la clave privada es uno de los dos números primos. El tamaño de estos números supera ya, actualmente, las 200 cifras y será necesario ir aumentándolo a medida que los ordenadores sean capaces de factorizar números grandes utilizando cada vez un tiempo menor.

Para ver como se obtienen las claves, supongamos que A quiere mandar un mensaje cifrado a B y que este debe poder descifrarlo. Entonces A manda un número k (menor que otro n) y genera un mensaje cifrado c, de modo que c ≡ k^e (mod. n), donde e es la clave pública de B. En realidad la clave pública es el par (n, e). Cuando B recibe el mensaje cifrado lo que debe hacer es realizar la operación inversa, que vendrá dada por la operación k ≡ c^d (mod. n), donde d es la clave privada que B conoce.

Para realizar este proceso es necesario utilizar la función de Euler, φ (n), que para cada número me da la cantidad de números menores que n y primos con él. En efecto, al elegir e es necesario que este sea menor y coprimo con φ (n), por lo que primero hay que calcular φ (n), algo que se hace utilizando las propiedades de dicha función y teniendo en cuenta que n = p · q, donde p y q son primos, por lo que resultará que: φ (n) = (p - 1) (q - 1).

Por otro lado, para determinar d (la clave privada), se debe verificar que:



Estas propiedades se derivan del llamado pequeño teorema de Euler, referido a la función φ (n) y cuyo enunciado es el siguiente: "Si n es un entero, n > 1, y la función de Euler φ (n) nos da la cantidad de enteros entre 1 y n-1 que son primos con n, entonces para cualquier entero a primo con n se tiene que: a^φ(n) ≡ 1 (mod n).

Entonces, si n = p · q, donde p y q son dos primos distintos, resulta que:



Los métodos de encriptación llamados de clave pública, de los cuales el RSA es el más difundido y utilizado, pueden explicarse mediante una analogía física. Como dice el profesor Xarles, imaginemos que queremos recibir un paquete que nadie pueda abrir antes que nosotros. Repartimos candados abiertos (la clave pública) de los cuales solo nosotros tenemos la llave para abrirlos una vez cerrados (clave secreta). Quien nos quiera enviar un paquete tiene que mandarlo en una caja cerrada con uno de nuestros candados. Si el paquete y el candado son los suficientemente fuertes para que no puedan romperse, nadie que intercepte nuestro paquete podrá abrirlo, algo que sólo nosotros podremos hacer ya que disponemos del método para abrir el candado.

Es interesante notar que tanto la descomposición en factores primos de un número, como la función de Euler, dos ideas clave de la teoría de números, cuyo origen y desarrollo ha estado durante mucho tiempo alejado de posibles aplicaciones más allá de las matemáticas, al final encuentran su aplicación en un problema tan importante para el mundo actual como es el cifrado de mensajes, sin el cual muchas de las transacciones que se hacen cada día en la actualidad no podrían realizarse por falta de seguridad.

Para profundizar en estos temas recomiendo encarecidamente la lectura del artículo de Xavier Xarles, que lleva por título Els primers, desvelats, publicado en 2018 en el Butlletí de la Societat Catalana de Matemáticas, vol. 33, núm. 1, muchas de cuyas ideas, escritas a la vez con claridad y rigor, he utilizado en este texto.