Biografías

Temas

Curiosidades

Apuntes

Problemas

Software

Libros

Artículos

Enlaces

Grupos

Escribime

Libro de visitas

La teoría de números, tenida en tiempos por disciplina esotérica que se ocupaba de las curiosas propiedades de los números primos, se encuentra hoy en las entrañas mismas de la criptografía moderna. El algoritmo criptográfico RSA (sigla de sus inventores, Rivest, Shamir y Adleman), utilizado en la mayoría de las transacciones de comercio electrónico, se funda en la dificultad (no demostrada matemática, pero sí empíricamente) de descomponer en factores un número compuesto por el producto de dos números primos.
La multiplicación de dos números primos grandes constituye un ejemplo de las llamadas "funciones de una sola dirección": la multiplicación requiere escasos microsegundos, siendo tal tiempo proporcional a la longitud de las representaciones binarias de los números; por el contrario, el descubrimiento de los factores dado solamente el producto es un proceso lento, que exige varias horas para un producto de 512 bits, y que a partir de ahí continúa con un crecimiento exponencial lento en función de la longitud binaria del producto. Para números de 2048 bits la descomposición factorial se considera prácticamente inviable, al menos que se sepa. Los algoritmos de factorización rápida, de existir, tendrían un sinfín de aplicaciones en el espionaje industrial e incluso en el militar.
Lo cual nos lleva a un problema propuesto por John McCarthy (inventor del lenguaje Lisp y teórico de la inteligencia artificial) y que resolvió Michael Rabin (inventor de tantos e importantes algoritmos informáticos) allá por los años cincuenta. El problema reza como sigue: Disponemos de un puñado de espías dispuestos para entrar en territorio enemigo. Deseamos evitar que sean atacados cuando traten de regresar a territorio propio, y también, lógicamente, la infiltración de espías enemigos. Así pues, cada espía ha de presentar una contraseña a los guardias fronterizos, que éstos comprobarán. Aunque tenemos confianza en nuestros espías y en la lealtad de los guardias, existe el temor de que éstos se vayan de la lengua por las noches en algún bar. ¿Qué información habrían de recibir los guardias, y de qué modo han de presentar los espías sus contraseñas, de manera que sólo los agentes propios puedan pasar, y nadie más? Puede dar por supuesto que lo dicho sobre números primos es una pista.


SOLUCION AVENTURAS PROBLEMATICAS DICIEMBRE 2002:

Se necesita una función de una sola dirección cuya verificación les resulte sencilla a los guardias, pero tal que le sea muy difícil al adversario hallar la función inversa.
Una estrategia basada en números primos funcionaría como sigue: antes de salir del suelo patrio, el espía selecciona al azar dos números primos grandes (p y q) y le facilita a los guardias fronterizos su producto (p x q). Los guardias no necesitan saber quién les proporcionó ese valor; basta que sepan que el número recibido viene de fuente autorizada.
Cuando un guardia quiere cerciorarse de que regresa un espía propio, el espía le da sus dos factores primos; el guardia los multiplica y comprueba que el producto corresponde a uno de los números de su lista. Evidentemente, estos números no pueden volver a ser utilizados por este espía ni por ningún otro. Incluso aunque un guardia se vaya de la lengua y revele en público alguno de los números no utilizados, resulta imposible hallar sus factores primos, lo que impide la infiltración de un espía enemigo.
He aquí la solución ideada por Rabin mucho antes de la invención de la criptografía de clave pública, valiéndose de una función de una dirección ideada por John von Neumann (con el propósito de generar números pseudoaleatorios): se empieza con un número cualquiera (que será el primer número de la serie) y se eleva al cuadrado; se toman entonces los dígitos centrales del cuadrado, que forman otro número (el segundo número de la serie), que se eleva al cuadrado. Prosiguiendo de igual manera se genera una sucesión de números pseudoaleatorios.
El método de Rabin funcionaba como sigue. Haga que cada espía memorice un número grande N tomado al azar, de 50 cifras, pongamos por caso. Al ser identificado, el espía dará el número N. El guardia calcula M = N x N y toma a continuación los 50 dígitos centrales de M, comprobando seguidamente que están en su lista y que no han sido tachados ya. De ser así, deja pasar al espía, tacha ese número de su lista, e informa a los demás puestos fronterizos. La próxima vez que el espía haya de partir en misión, genera otro número al azar, y los 50 dígitos centrales les son enviados a los puestos de guardia de la frontera.
Aun cuando el guardia difunda la lista completa, el adversario ha de efectuar el equivalente a hallar N dados los 50 dígitos centrales de M. Es una tarea extraordinariamente difícil, pero los lectores de inclinación matemática podrán percatarse de que son varios los números N que pueden servir.