El criptosistema RSA
Este sistema de clave pública fué diseñado en 1977 por los
profesores del MIT (Massachusetts Institute of Technology)
Ronald R. Rivest, Adi Shamir y Leonard M. Adleman, de ahí
las siglas con las que es conocido. Desde entonces, este
algoritmo de cifrado se ha convertido en el prototipo de los
de clave pública.
La seguridad de RSA radica en la dificultad de la
factorización de números grandes: es fácil saber si un
número es primo, pero es extremadamente difícil obtener la
factorización en números primos de un entero elevado,
debido no a la dificultad de los algoritmos existentes, sino al
consumo de recursos físicos (memoria,
necesidades hardware...incluso tiempo de ejecución) de tales
algoritmos. Se ha demostrado que si n es el número de
dígitos binarios de la entrada de cualquier algoritmo de
factorización, el coste del algoritmo es , con un tiempo de
ejecución perteneciente a la categoría de los llamados
problemas intratables.
Veamos el funcionamiento del algoritmo RSA: si un usuario
A desea enviar información cifrada, en primer lugar tiene
que calcular un par de claves (pública y privada), para lo que
ha de elegir aleatoriamente dos números primos grandes (del
orden de cien dígitos), y , números que se han de mantener
en secreto; si llamamos ( se conoce como módulo) al
producto , el usuario ha de determinar otro entero, , llamado
exponente privado, que cumpla
es decir, y el producto , que llamaremos función de Euler y
denotaremos , han de ser primos. Con estos datos, ya
tenemos la clave privada del cifrado: el par ; para obtener la
clave pública, hallamos el inverso multiplicativo del número
respecto de , de la forma . Calculado este entero , llamado
exponente público, la clave pública será el par .
Una vez el emisor A dispone de sus claves pública y privada,
podría enviar un mensaje cifrado, que llamaremos , a un
posible receptor, mediante la operación
aplicada a cada elemento del mensaje.
Cuando el receptor del criptograma desee descifrar el
mensaje recibido, ha de realizar la operación
para obtener el texto en claro del mensaje que acaba de
recibir.
El sistema RSA ha permanecido invulnerable hasta hoy, a
pesar de los numerosos ataques de criptoanalistas;
teóricamente es posible despejar para obtener la clave
privada, a partir de la función de descifrado, resultando
Sin embargo, el cálculo de logaritmos discretos es un
problema de una complejidad desbordante, por lo que este
tipo de ataque se vuelve impracticable: la resolución de
congruencias del tipo , necesarias para descifrar el mensaje,
es algorítmicamente inviable sin ninguna información
adicional, debido al elevado tiempo de ejecución del
algoritmo. Aunque cuando los factores de son pequeños
existe un algoritmo, desarrollado por Pohlig y Hellman de
orden , éste es otro de los algoritmos catalogados como
intratables, vistos anteriormente.
El criptosistema RSA
Este sistema de clave pública fué diseñado en 1977 por los
profesores del MIT (Massachusetts Institute of Technology)
Ronald R. Rivest, Adi Shamir y Leonard M. Adleman, de ahí
las siglas con las que es conocido. Desde entonces, este
algoritmo de cifrado se ha convertido en el prototipo de los
de clave pública.
La seguridad de RSA radica en la dificultad de la
factorización de números grandes: es fácil saber si un
número es primo, pero es extremadamente difícil obtener la
factorización en números primos de un entero elevado,
debido no a la dificultad de los algoritmos existentes, sino al
consumo de recursos físicos (memoria,
necesidades hardware...incluso tiempo de ejecución) de tales
algoritmos. Se ha demostrado que si n es el número de
dígitos binarios de la entrada de cualquier algoritmo de
factorización, el coste del algoritmo es , con un tiempo de
ejecución perteneciente a la categoría de los llamados
problemas intratables.
Veamos el funcionamiento del algoritmo RSA: si un usuario
A desea enviar información cifrada, en primer lugar tiene
que calcular un par de claves (pública y privada), para lo que
ha de elegir aleatoriamente dos números primos grandes (del
orden de cien dígitos), y , números que se han de mantener
en secreto; si llamamos ( se conoce como módulo) al
producto , el usuario ha de determinar otro entero, , llamado
exponente privado, que cumpla
es decir, y el producto , que llamaremos función de Euler y
denotaremos , han de ser primos. Con estos datos, ya
tenemos la clave privada del cifrado: el par ; para obtener la
clave pública, hallamos el inverso multiplicativo del número
respecto de , de la forma . Calculado este entero , llamado
exponente público, la clave pública será el par .
Una vez el emisor A dispone de sus claves pública y privada,
podría enviar un mensaje cifrado, que llamaremos , a un
posible receptor, mediante la operación
aplicada a cada elemento del mensaje.
Cuando el receptor del criptograma desee descifrar el
mensaje recibido, ha de realizar la operación
para obtener el texto en claro del mensaje que acaba de
recibir.
El sistema RSA ha permanecido invulnerable hasta hoy, a
pesar de los numerosos ataques de criptoanalistas;
teóricamente es posible despejar para obtener la clave
privada, a partir de la función de descifrado, resultando
Sin embargo, el cálculo de logaritmos discretos es un
problema de una complejidad desbordante, por lo que este
tipo de ataque se vuelve impracticable: la resolución de
congruencias del tipo , necesarias para descifrar el mensaje,
es algorítmicamente inviable sin ninguna información
adicional, debido al elevado tiempo de ejecución del
algoritmo. Aunque cuando los factores de son pequeños
existe un algoritmo, desarrollado por Pohlig y Hellman de
orden , éste es otro de los algoritmos catalogados como
intratables, vistos anteriormente.
Una representación artística de una distribución de números primos. E. T.
CIENCIA MATEMÁTICAS
Se buscan números
primos… ¿pero para
qué?
El mayor número primo hasta ahora se ha dado a conocer este mes.
Se trata de una cifra larguísima, compuesta por más de 22 millones
de dígitos. ¿Cuál es la principal utilidad práctica de estos peculiares
números?
28 enero, 2016 01:45
1. MATEMÁTICAS
2. DESCUBRIMIENTOS CIENTÍFICOS
3. COMPUTACIÓN
Pablo Romero @pabloromero
Bien por tradición, por su utilidad presente -y futura-, por su belleza,
porque suponen un reto intelectual o incluso por dinero, algunos
matemáticos siguen dedicados a la búsqueda de números primos.
Un número primo es aquel natural mayor que uno y que sólo admite
dos divisiones distintas: por él mismo y por 1. Así, son primos el 2, el
3, el 5, el 7, el 11… pero no lo son el 4, el 6, el 8, el 9, el 12… Fueron
definidos por primera vez por Euclides en su obra Los
Elementos (alrededor del año 300 AC) y, desde entonces, muchos
matemáticos se han esforzado en aumentar esta particular e infinita
lista.
Lo cierto es que, en la vida diaria, tienen una utilidad limitada. "Los
números primos se suelen usar en criptografía, en el llamado
sistema RSA, conocido por las iniciales de sus creadores: Ron Rivest,
Adi Shamir y Leonard Adleman, del MIT", comenta Manuel de León,
investigador del Instituto de Ciencias Matemáticas (ICMAT).
El cifrado RSA, también conocido como asimétrico o de clave
pública, se basa en la dificultad de factorizar números grandes y
funciona así: un mensaje de texto puede transformarse en una serie
de cifras fruto del producto de dos números primos grandes elegidos
al azar. Cada usuario tiene una clave pública, que puede entregar a
cualquier persona, y guarda una privada, que sólo él conoce. El
remitente sólo necesita una copia de la clave pública del destinatario
y cifrar con ésta el mensaje, mientras que el receptor usará su clave
privada para poder acceder al texto.
El juez Andreu pidió a los Mossos que no compartiesen
con la policía sus pesquisas sobre el 17-AGonzalo AraluceEl
magistrado se lo comunicó a un representante del Cuerpo, según un correo
remitido a Josep Lluís Trapero. La Fiscalía pide 11 años de prisión para Trapero
por poner a los Mossos a disposición del secesionismo. Los Mossos atribuyeron la
deflagración de Alcanar al chispazo de un frigorífico y obviaron los explosivos.
recomendado por
"RSA es un sistema que se basa en la expresión de un número en sus
factores primos, básicamente lo que aprendemos en el colegio",
añade De León, que explica en qué se basa la robustez de su
seguridad: "Se buscan dos números primos muy grandes, se
multiplican, y el problema para los que quieran descifrar el mensaje
es que el producto es un número tan grande que resulta casi
imposible recuperar sus dos factores; esto se inventó en 1977 y fue
toda una revolución".
Según este experto, en el cifrado radica hoy por hoy la importancia
práctica de los números primos, "que son además los ladrillos con
los que se construyen todos los demás números", apunta.
El primo más alto
El pasado día 7 de enero, el doctor en matemáticas de la University
of Central Missouri Curtis Cooper anunciaba el hallazgo del mayor
número primo conocido hasta la fecha: 2 elevado a 74.207.281 -1, o
sea: dos multiplicado por sí mismo 74.207.281 millones de veces,
menos uno. Si lo escribiéramos, necesitaríamos espacio para meter
22.338.618 dígitos. Y ha sido bautizado como M74207281. El
anterior numero primo récord, descrito en 2013, constaba de más de
17 millones de dígitos.
El hallazgo, además, tiene una peculiaridad: se trata de un número
primo de Mersenne, una rareza matemática llamado así en honor al
monje francés del siglo XVII Marin Mersenne, que ya en su época
conjeturó algunas de sus propiedades. Se definen por la
fórmula 2 elevado a p-1, de modo que los primeros números primos
de Mersenne son 3, 7, 31 y 127, siendo p= 2, 3, 5 y 7,
respectivamente. Hasta la fecha sólo se conocen 49 de estos
números.
Curiosamente, la gran mayoría de los números primos más
altos descubiertos son primos de Mersenne. De hecho, explica
Manuel de León, uno de los mecanismos para construir números
primos es usar propiedades como la que descubrió Mersenne: "Uno
toma un número primo p y aplica la fórmula 2 elevado a p y luego se
resta 1; algunas veces éste resulta un primo".
"Existe un algoritmo muy rápido y eficiente, llamado test de Lucas
Lehemer, que funciona bien para decidir si un número de
Mersenne es primo", apunta Maria Emilia Alonso, profesora del
Departamento de Álgebra en la UCM. "Así pues, a pesar de tratar
siempre con números grandes, es mucho más sencillo averiguar que
un número de Mersenne es primo que demostrar que otro de tamaño
similar y que es primo lo es de verdad".
Por ello, parece que ésta es la vía más rápida para hallar nuevos
números primos altos. Y precisamente los últimos anuncios
provienen de una red de voluntarios que, mediante computación
distribuida, dedican potentes ordenadores a la búsqueda de estos
peculiares números.
Cooper explica a EL ESPAÑOL que "uno beneficios directos de la
búsqueda de números primos de Mersenne es el descubrimiento y la
experimentación de nuevos algoritmos para la determinación de
números primos de Mersenne y primos en general", afirma. Otro
beneficio es que la recogida de datos de las pruebas de los números
primos de Mersenne que pueden ayudar a varios teóricos de
comprender mejor la distribución de estos números.
Cómo se calcula
Curtis Cooper y la University of Central Missouri son los principales
contribuyentes en tiempo al proyecto GIMPS (Great Internet
Mersenne Prime Search, o Gran Búsqueda en Internet de los Primos
Mersenne), un ejemplo de cooperación en red que se apoya en
cientos de voluntarios que ceden potencia de sus ordenadores para
calcular sin descanso números primos. Para ello, los participantes
utilizan un programa libre, Prime95.
No es la primera vez que Cooper encuentra grandes números primos
de Mersenne: desde 2005, ha calculado en cuatro ocasiones el
número primo más alto, aunque estos descubrimientos nunca se
hubieran dado sin los voluntarios de GIMPS, que filtran cantidades
ingentes de números en busca de los candidatos que resultan ser no
primos.
Si bien un número tan alto difícilmente podría usarse hoy en día en
cifrado -actualmente el que usa el banco o el correo electrónico
utiliza números primos de unos cientos de cifras, 22 millones es algo
excesivo-, la búsqueda en sí tiene otro beneficio práctico: poner a
prueba el hardware y la arquitectura de las máquinas encargadas de
calcular, tal y como comenta a este diario el propio Cooper.
Tradicionalmente, algunos programas para la búsqueda de números
primos se han utilizado como test para procesadores. De hecho, las
rutinas de softwaredel proyecto GIMPS eran ya utilizadas por Intel
para probar sus legendarios chips Pentium II y Pentium Pro. Incluso
ahora, durante el proceso de búsqueda de este último número primo
de Mersenne, se detectó un fallo en los últimos procesadores Intel
Core i7 -antes llamados Skylake-, usados para tal fin.
"Otro beneficio indirecto de GIMPS es la prueba de que un gran
proyecto de computación distribuida puede funcionar realmente",
añade Cooper.
Chris Caldwell, profesor de matemáticas en la University of
Tennessee y uno de los principales impulsores del proyecto GIMPS
"en su tiempo libre", explicaba hace tiempo las razones por las que se
siguen calculando números primos. Grandes matemáticos los han
estudiado desde hace siglos, recuerda este científico, que además
apunta a que la investigación puede dar lugar a otros
descubrimientos provechosos. Otras razones que expone para seguir
escarbando en busca de estos escurridizos números son: por el mero
hecho de "coleccionar objetos raros y bellos", por un deseo de
competir ("¡Por la gloria!") e incluso por dinero: la fundación EFF
ofrece una jugosa recompensa de 150.000 dólares para el primero
que descubra un número primo de 100 millones de cifras.
"De todos modos", añade con humor la profesora Maria Emilia
Alonso, "es difícil de explicar al mundo exterior en qué nos
divertimos los matemáticos".
Mientras, la búsqueda continúa. "Hay infinitos números primos y
esto ya lo probó Euclides, es un razonamiento muy simple por
reducción al absurdo: si supongo que hay un número finito, llego a
una contradicción", comenta el matemático Manuel de León, que
añade: "Por lo tanto, nunca acabaremos de encontrar números
primos".
