Números Primos: El Fundamento Invisible de la Criptografía y el Comercio Electrónico

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 o blockchain. En este caso, 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 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. El sistema más empleado en la actualidad se conoce como RSA, debido a las iniciales de sus tres inventores: Rivest, Shamir y Adleman. 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.

Generación de Claves RSA y su Aplicación

Veamos cómo cada usuario obtiene estas dos claves:

1. El usuario genera dos primos grandes al azar, p y q, y calcula su producto, n = p·q, así como el valor de (p-1)(q-1) = f. (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. Elige otro número entero, e, de modo que sea primo con f, es decir, que mcd(e,f )=1. (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.)
3. Calcula el inverso 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.

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). Este número 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. La robustez de este sistema se basa en la dificultad de factorizar números grandes. Se buscan dos números primos muy grandes y se multiplican.

Factorizar y Determinar Números Primos: Una Tarea Compleja

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. La fortaleza de este algoritmo reside en el elevado coste computacional de hallar los dos factores primos de un número lo suficientemente grande resultado del producto de ambos, aunque este último sea público y, por tanto, pueda ser conocido por cualquiera, ya que esta tarea no es factible en un tiempo razonable con los algoritmos de factorización conocidos que se pueden implementar hasta la fecha y con la potencia de cálculo de los ordenadores actuales, por mucha de esta última de la que se disponga.

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.

Criptografía y Comercio Electrónico: La Teoría de Números en Acción

En un mundo cada vez más digital, donde nuestras compras, mensajes y transacciones ocurren en línea, es fácil olvidar que todo eso se sostiene sobre una estructura invisible: la matemática. Más precisamente, sobre una rama antigua y fascinante llamada teoría de números. En este contexto entra en juego la criptografía, que es la ciencia de diseñar sistemas que permiten proteger información mediante técnicas de codificación, de forma que solo quien tenga la clave pueda acceder al contenido. Desde hace décadas se ha transformado en el escudo de nuestra vida digital.

Uno de los sistemas más usados hoy es RSA, un algoritmo de encriptación que se basa en propiedades profundas de los números primos y en la aritmética modular, dos conceptos clásicos de la matemática. Lo más fascinante es que, aunque hay infinitos primos, no sabemos con certeza dónde está el próximo. La esencia de RSA reside en la belleza de la teoría de números y la aritmética modular. No hace falta ser un genio para apreciar la elegancia de este sistema. En principio, hay que tener en cuenta una verdad matemática fundamental: el Teorema Fundamental de la Aritmética, que establece que todo número entero mayor que 1 puede escribirse de una única manera como producto de números primos. Por ejemplo, el 30 puede expresarse únicamente como el resultado de multiplicar 2, 3 y 5. Esto muestra a los primos como los átomos de la matemática: indivisibles y esenciales.

Por lo que la clave está en tomar dos números primos muy grandes, que se mantienen en secreto. Se los multiplica para obtener un número enorme, de cientos de cifras, que sí se hace público. Ese número, junto con otro valor llamado exponente público, forma la clave pública. Luego, usando una fórmula matemática basada en la aritmética modular, se calcula una clave privada, que solo puede obtenerse si se conocen los primos originales. RSA se basa en un sistema de claves pública y privada: cualquiera puede cifrar un mensaje con la clave pública, pero solo el dueño de la clave privada puede descifrarlo.

Factorizar un número de cientos de cifras para saber qué producto de números primos lo conforman sigue siendo un problema prácticamente imposible para cualquier computadora moderna. Los números primos se suelen utilizar en criptografía, en el llamado sistema RSA. También se le conoce como asimétrico o de clave pública, y es el que utilizan los certificados digitales. Cada usuario tiene una clave pública, que puede entregar a cualquier persona, y una privada, que solo él conoce. El remitente solo necesita una copia de la clave pública del destinatario y cifrar con esta el mensaje, mientras el receptor usará su clave privada para poder acceder al texto.

La Búsqueda de Números Primos y el Impacto en Blockchain y Criptomonedas

La sociedad se digitaliza y la necesidad de seguridad es constante. Un descubrimiento matemático realizado por programadores informáticos, que utilizaron una ecuación de 350 años para encontrar un número primo récord, podría brindar respuestas a la desmedida demanda de electricidad de bitcoin. El proyecto de la «Gran Búsqueda en Internet de los Primos Mersenne» (GIMPS, en sus siglas en inglés) se nutre de una red de voluntarios que, mediante computación distribuida, dedican potentes ordenadores para buscar estos números. Un total de 360.000 computadoras y más de 150 billones de cálculos por segundo.

Great Internet Mersenne Prime Search halló y confirmó el número primo más grande conocido, una cifra con 23 millones de dígitos descubierta con el cálculo del monje francés del siglo XVI Marin Mersenne. Ese esfuerzo, amén de otros métodos informáticos colaborativos, están haciendo evolucionar la ciencia de la criptografía, que es esencial para crear y rastrear los bitcoins. El descubrimiento de este singular número será clave para encriptar y proteger datos, y es muy posible que en poco tiempo tenga una gran aplicación en los servicios online para banca online, compras por internet y mensajería. Con este descubrimiento se fortalecen las fórmulas para asegurar la seguridad en nuestras transacciones.

“Estas ideas podrían estar conectadas intelectualmente”, dijo Seth Schoen, tecnólogo sénior en la Electronic Frontier Foundation (EFF) de San Francisco, que ofrece un botín de US$150.000 a la primera persona o al grupo que descubra un número primo de 100 millones de dígitos. “La minería de criptomonedas podría considerarse un descendiente indirecto de los proyectos informáticos distribuidos”. El proceso de buscar números primos -que constituyen la base de la criptografía- demuestra que resolver ecuaciones tediosas puede traer aparejados avances científicos con aplicaciones prácticas.

El ascenso meteórico de bitcoin y otras criptomonedas agita el debate en los niveles más altos de la formulación de las políticas monetarias. Los adeptos apuestan a que la confianza en la tecnología de cadena de bloques para hacer un seguimiento de las transacciones revolucionará a la larga la forma de almacenar y transmitir valor. Los detractores señalan la enorme energía que consumen las computadoras que se utilizan para resolver las mundanas ecuaciones matemáticas que hacen funcionar el sistema.

La energía siempre ha sido parte del ADN del bitcoin. La persona a la cual se atribuye la creación de la moneda, identificada solo como Satoshi Nakamoto, concibió el sistema que otorga monedas virtuales por resolver acertijos complejos y emplea un libro mayor digital encriptado para seguir todo el trabajo y todas las transacciones. “A esta energía se le da un uso productivo en un sentido -confirmar la autenticidad de las transacciones con bitcoin-”, escribió Schoen en un correo electrónico. “Pero resulta desproporcionada en muchos sentidos, sobre todo si se pudiera encontrar otra alternativa técnica para confirmar las transacciones utilizando al mismo tiempo mucha menos energía”.

El tecnólogo de la EFF, que lleva más de 20 años trabajando en codificación, enfatizó que los métodos en colaboración utilizados para detectar números primos muy grandes tienen más impacto en la criptografía que las cifras mismas. Hasta que se produzca el advenimiento de la computación cuántica, la mayoría de la gente está a salvo con la codificación de tres dígitos. Se está acelerando la búsqueda de un compromiso, y algunos científicos están tratando de reducir la energía necesaria para el procesamiento informático.