Cifrado con números primos

hace 1 año 87
Ronald L. Rivest, Adi Shamir y  Leonard M. Adleman, creadores del algoritmo RSA, en el escenario de la Conferencia RSA sobre seguridad de la información.Ronald L. Rivest, Adi Shamir y Leonard M. Adleman, creadores del algoritmo RSA, en el escenario de la Conferencia RSA sobre seguridad de la información.Kim Kulish (Corbis via Getty Images)

En las dos semanas anteriores hemos hablado de los mensajes cifrados y de las primeras y más sencillas técnicas utilizadas para encriptarlos (el cifrado por sustitución y el cifrado por desplazamiento o cifrado César), así como del supuestamente indescifrable cifrado Vigenère, que introduce el concepto de clave: una palabra o frase que es necesario conocer para descifrar el mensaje.

Cambiemos ahora de tema por un momento (aunque solo aparentemente). ¿Qué números completan la secuencia siguiente?:

4, 6, 9, 10, 14, 15, 21…

Y, más difícil todavía, ¿qué números completan esta otra secuencia, prima hermana de la anterior?:

121, 143, 169, 187, 209, 221, 247…

Lo de “prima hermana” viene a cuento porque la cosa va de números primos. Y por eso decía que el cambio de tema solo era aparente, porque los números primos juegan un papel importante en la moderna criptografía.

Hasta hace unas décadas, la criptografía, aparte de su interés teórico (y también lúdico), solo era una cuestión práctica para los servicios de inteligencia; pero con la eclosión de la informática y la universalización de las operaciones en red, la posibilidad de mandar informaciones reservadas (números de cuenta, claves de acceso, etc.) de forma segura, pero a la vez fluida y fácil de manejar, se ha convertido en una prioridad. Y ahí intervienen los escurridizos números primos.

Sin entrar en detalles (de momento: ya lo haremos más adelante), digamos que hay sistemas de encriptado y desencriptado que se basan en manejar a la vez claves públicas y privadas, y que las primeras pueden basarse en el producto de dos números primos muy grandes. Veamos un ejemplo simplificado:

Recibo, de forma pública (o poco segura), el número 135143, que es el producto de dos primos, de los cuales conozco uno, que es el 149; dividiendo 135143 por 149 obtengo el otro factor primo, 907, que me permitirá, tras las operaciones pertinentes, decodificar un mensaje o acceder a una información reservada. ¿Demasiado fácil de descubrir? Si no supiera que 149 es uno de los factores, tendría que probar con una treintena de primos antes de encontrar la factorización. Si sigue pareciéndote fácil, intenta descomponer en sus factores los siguientes números, que son el producto de dos primos:

2117

4087

7387

9167

Todos terminan en 7, pero, obviamente, no tiene por qué ser así. ¿De cuántas maneras distintas puede terminar el producto de dos números primos de varias cifras?

RSA

Pero lo que para los cerebros humanos resulta largo y laborioso, para los electrónicos es una tarea casi instantánea, y por eso en la actualidad se utilizan números primos enormes, de cientos de cifras, inatacables incluso para los ordenadores más potentes.

El algoritmo basado en el producto de grandes primos más conocido es el RSA (por las iniciales de sus creadores: Rivest, Shamir y Adleman), desarrollado en 1979 y ampliamente utilizado desde entonces. Algunos opinan que los ordenadores cuánticos resolverán con facilidad el problema de la factorización; pero otros opinan que ni siquiera esas potentísimas máquinas lograrán -cuando dispongamos de ellas- descifrar mensajes cifrados con el algoritmo RSA y similares. ¿Se ha alcanzado por fin el objetivo de un cifrado indescifrable?

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aquí para recibir nuestra newsletter semanal.

Ver artículo completo