Cifrado con n¨²meros primos

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.