¿Qué papel juegan los números primos en la teoría de la información y la criptografía?

De todos es sabido que un número entero es un número primo si tiene la propiedad de que solo es divisible por sí mismo y por la unidad. Esta característica los hace especialmente atractivos porque no es sencillo saber a priori y sin el uso de calculadoras y ordenadores, cuándo un número es primo si su tamaño es de más de tres cifras. Los números que no son primos se denominan compuestos y se pueden escribir como producto de números primos elevados a potencias.

Si el número entero es pequeño, digamos de una o dos cifras, es relativamente sencillo decidir acerca de su primalidad. Así, podemos afirmar rápidamente que 23 es primo, porque fácilmente podemos comprobar que no tiene otros divisores que el 1 y el propio 23. Sin embargo, no es tan sencillo llegar a la respuesta correcta si el número es mayor, como puede ser 9876543211. Por el contrario, 63 es compuesto porque 63 = 3²·7, es decir, factoriza como producto de números primos.

Otro concepto relacionado con la primalidad es el de la primalidad relativa entre dos números: dos números se dicen primos entre sí, si el único divisor que tienen en común es el 1, esto es, si su máximo común divisor (mcd) es 1. Es evidente que si los dos números son primos, son primos entre sí; pero puede darse el caso de que uno de ellos sea primo y el otro no (7 y 9) o que los dos sean compuestos (4 y 9) y sean primos entre sí.

La propiedad que permite la definición de número primo es la que los convierte en una herramienta muy útil en determinadas parcelas de las matemáticas y de la ciencia en general, como su uso en la teoría de números, simulaciones, generación de números (pseudo)aleatorios, blockchain, etc. En este caso, por razones de espacio y sencillez, nos vamos a ocupar de uno de sus usos más relevantes en la actualidad: el relacionado con la seguridad de la información y, más concretamente, con la criptografía.

Los números primos en criptografía

Para entender por qué los primos son tan importantes en criptografía, recordemos que esta ciencia que se encarga de convertir cualquier tipo de información en algo ilegible, de modo que quede garantizada su confidencialidad o secreto. Lo que se pretende, en definitiva, es impedir que su contenido sea accesible a otras personas y, a la vez, se desea que esta información pueda ser conocida para aquellos a los que tal información va dirigida. Es decir, la criptografía permite el cifrado y el descifrado de información haciendo uso de algoritmos que utilizan como entrada una clave y la información a cifrar (el “texto claro”), para producir la información cifrada (el “texto cifrado”); de tal manera que su contenido se convierte en secreto y no puede ser conocido si no se tiene la clave de descifrado, esto es, la que deshace el proceso anterior. 

Existen muchos sistemas de cifrado o criptosistemas y en casi todos ellos los números primos son el fundamento que permite garantizar que un adversario no será capaz de descifrar el texto cifrado. Es decir, los números primos son la base de las claves que se emplean en algunos de estos criptosistemas. Para concretar un poco más, vamos a revisar uno de ellos, precisamente el más empleado en la actualidad y que se conoce como RSA, debido a las iniciales de sus tres inventores: Rivest, Shamir y Adleman. En este caso, el RSA es un sistema de cifrado asimétrico porque utiliza una clave para el cifrado de la información y otra diferente para el descifrado. La primera es conocida públicamente y permite que cualquier usuario cifre información destinada al propietario de dicha clave; mientras que este guarda en secreto la clave privada y la utiliza para descifrar tal información.

Es claro que si ambas claves realizan procesos inversos: cifrar y descifrar, están relacionadas de alguna manera. Sin embargo, esta relación no debe permitir que conocida la clave de cifrado se pueda obtener la clave de descifrado. La garantía de que esto es así se basa en utilizar problemas matemáticos difíciles de resolver.

Veamos cómo cada usuario obtiene estas dos claves

1. El usuario genera dos primos grandes^[1] al azar, p y q, calcula su producto, n =p·q y el valor de (p–1)(q–1)=f.
2. Elige otro número entero, e, de modo que sea primo^[2] con f, es decir que mcd(e,f )=1.
3. Calcula el inverso^[3] de e con relación a f, es decir, el número d que cumple la siguiente propiedad: e·d =1+r·f, siendo r  un número entero^[4].
4. Hechos estos sencillos cálculos, el par (n,e) es la clave pública mientras que d es la clave privada.

En todo caso, los valores de p, q y f han de mantenerse en secreto para evitar que un adversario pueda calcular la clave privada. En efecto, si los números primos p o q fueran conocidos o fácilmente computables, sería muy sencillo calcular f y entonces la determinación de d sería inmediata.

A modo de ejemplo, una de estas claves públicas podría ser el par dado por los números e=2¹⁶+1=65537 y n=25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357, que tiene 617 dígitos (2048 bits), es decir, es el producto de dos números primos, p y q, de 308 y 309 dígitos (1024 bits), respectivamente.

Pudiera parecer que este tipo de clave queda fuera de nuestra vida diaria por ser un número excesivamente grande; pero no es así porque todos tenemos en el DNIe una clave pública de este tamaño y otra privada, que nos permite firmar documentos electrónicamente.

Además del algoritmo de generación de claves, se emplean algoritmos para el cifrado y descifrado, que se salen del tema a tratar en este artículo.

Factorizar y determinar números primos no es tan sencillo

Como ya hemos apuntado, la seguridad del RSA se fundamenta en que debe ser muy difícil calcular los números primos p y q, conociendo el valor de n=p·q, incluso aunque el adversario disponga de los mejores ordenadores y algoritmos. Esto es, n debe ser difícilmente factorizable, por lo que los primos, p y q, deben verificar, entre otras condiciones, ser del mismo tamaño porque si uno de ellos, sea p, es mucho menor que el otro, entonces sería fácilmente computable, con lo que q se calcularía de forma inmediata: q=n/p. Así pues, una pregunta básica que dejamos abierta es: ¿cuándo el problema de la factorización es lo suficientemente complejo como para garantizar la seguridad del RSA?

Por otra parte, queda el problema de decidir cuándo un número dado grande es primo, puesto que son imprescindibles para generar claves seguras. A lo largo de la historia se han desarrollado muchos algoritmos para decidir la primalidad de un número: desde la criba de Eratóstenes (276-194 a.C.), pasando por la prueba de divisiones sucesivas para comprobar que el número no es divisible por números menores, hasta los más recientes basados en herramientas matemáticas complejas. Todos ellos requieren de un tiempo excesivamente largo (cientos de años) para decidir con una garantía del 100%, que un número grande es primo.

Por ello, se recurre a los tests de pseudoprimalidad que comprueban si el número cuya primalidad se desea establecer, cumple ciertas condiciones que verifican todos los números primos. Si las cumple, el número es pseudoprimo; en caso contrario, es compuesto. Estos tests no garantizan que el número sea primo, dado que hay números que no son primos que también cumplen muchas de las propiedades que verifican los números primos, pero garantizan con una muy elevada probabilidad (más del 99,99999%) que el número declarado pseudoprimo es realmente primo.

A la vista de lo comentado hasta aquí, podemos concluir que tanto calcular los dos números primos que dividen a una clave pública RSA como decidir sobre la primalidad de un número entero grande, son dos problemas muy difíciles de resolver, incluso con los mejores ordenadores y algoritmos disponibles. En definitiva, podemos afirmar que los números primos son el fundamento matemático que garantiza la seguridad de los principales y más utilizados sistemas de cifrado de hoy en día.

^[1] Hoy en día, en criptografía, se habla de números grandes cuando estos tienen más de 300 cifras, es decir, al menos, 1024 bits.

^[2] La comprobación de que mcd(e,f )=1 es un cálculo muy sencillo y eficiente pues basta con ejecutar el algoritmo de Euclides (ca. 325 a.C.-265 a.C.), que se limita a realizar una serie de divisiones sucesivas.

^[3] El cálculo de este inverso se realiza mediante el algoritmo de Euclides extendido, que también es un algoritmo que requiere poco tiempo de computación, aunque los números que intervengan sean grandes.

^[4] Esta relación suele escribirse como e·d=1 (mod f ), lo que se traduce en la propiedad de que e·d da de resto 1 cuando se divide entre f. 

Cortesía de Muy Interesante

Dejanos un comentario: