There are more things in heaven and earth

267-1 = 193.707.721 x 761.838.257.287

Durante tres años de su vida, el matemático estadounidense Frank Nelson Cole dedicó las tardes de los domingos a examinar si era cierta la afirmación del matemático francés Mersenne acerca de un procedimiento para obtener números primos elevando el 2 a determinadas potencias (todas números primos) y restando uno.

No era cierto para 67 y, en una reunión de la sociedad matemática americana, simplemente se puso en pie, fue a la pizarra, escribió la descomposición con la que comienzo este comentario y se sentó, entre los aplausos de matemáticos desmadrados. Lo cuento para dejar constancia de lo difícil que es saber si determinado número es primo o no. Esta dificultad tiene que ver con la seguridad de nuestro dinero cuando circulan determinados datos por internet.

El problema fundamental de la criptografía ha sido la necesidad de que remitente y destinatario conocieran el código que se usa para encriptar los mensajes y ya se sabe, cuando el código circula, siempre hay una femme fatale que puede hacerse con él.

Por eso resulta tan extraordinaria la idea que se les ocurrió a Whitt Diffie y Martin Hellman, dos matemáticos de la Universidad de Stanford, la llamada criptografía de clave pública, que se basa en un sistema de encriptado que no hay que mantener oculto, porque una vez utilizado, sólo el que conoce una fórmula secreta puede desencriptar el dato que queremos transmitir. El problema era encontrar ese procedimiento.

Lo lograron un informático y dos matemáticos del MIT. El informático es Ron Rivest y los matemáticos son Leonar Adleman y Adi Shamir. Aunque, para explicarlo, nos tenemos que remontar unos siglos atrás.

Fermat, ya saben, es conocido sobre todo por el famoso teorema ese que dicen que demostró Mr. Wiles —la verdad es que más que una demostración es una enciclopedia, con sus trescientos folios de curvas elípticas; yo tengo una demostración mucho más elegante, pero no me cabe en este pequeño blog—. Pues bien, existe también un pequeño teorema de Fermat. Una versión moderna de ese teorema usa las llamadas calculadoras de reloj de Gauss.

Piensen en un reloj de 24 horas. ¿Cuál es la hora 25? Pues la una, como sabemos todos desde niños. Por tanto, 315 en una calculadora así es 3 (es el resto de dividir 315 entre 24).

El pequeño teorema de Fermat dice que xp = x (módulo p), siempre que p sea un número primo y nuestra calculadora de reloj tenga p horas. Para entenderlo mejor vean un ejemplo: una calculadora con p=7 y buscamos un número cualquiera, véase 2. Ahora elevamos 2 a la séptima potencia y le aplicamos nuestra calculadora. Si el teorema es cierto, el resultado debe ser 2 de nuevo. El resultado es 128 y tras dividir 128 entre 7, el resto será 2.

Leonard Euler, que era tela listo, extendió el teorema y demostró que en un reloj con N horas, siendo N el resultado de la multiplicación de dos números primos, p y q, el reloj comenzaba de nuevo tras (p-1) (q-1) + 1 pasos.

Ya tenemos todos los mimbres.

Ahora, imaginen que están comprando Les fleurs du mal por internet y quieren pagar con su tarjeta. Usted pone el número de su tarjeta y el ordenador utiliza un número N como módulo de la calculadora de reloj. Es un número público y se usa el mismo durante meses. Cuando el cliente incluye su número de tarjeta, recibe otro código al que llamaremos C. La página hace un cálculo sencillito, eleva el número de la tarjeta, al que llamaremos T, a la potencia C, pero lo hace usando la calculadora de reloj N. El resultado es TC = (módulo N).

Ya tenemos ese número y lo mandamos por internet. Los malignos hackers lo descubren, pero no saben qué hacer con él porque, claro, hay que encontrar un número que multiplicado C veces por sí mismo, usando una calculadora de reloj, sea igual al que han descubierto. Tengan en cuenta que el N que hoy se utiliza es un número de unas 250 cifras. Imaginen al pobre hacker probando cualquier posible hora en la calculadora de reloj.

La pregunta es ¿de qué le sirve ese número a VISA, por ejemplo?

Ahí está la gracia del asunto. No le serviría para nada si no fuera porque N (el módulo de la calculadora) es un número resultado de multiplicar dos números primos, p y q, que sí conocen.

Ahora se produce el truco de magia. Como los de VISA conocen esos números p y q, que son primos, son capaces de calcular las veces que tienen que multiplicar el número que reciban por internet (aplicando la calculadora de reloj N) para que reaparezca el número de la tarjeta de crédito.

En resumen, el problemilla es simple, hallar los primos con los que se obtiene N. Cosa de nada.

Fermat y Euler estarían encantados.

Como he dicho antes, en la actualidad se usan números N de unas doscientas cincuenta cifras y subiendo (en algún servicio secreto se llega a las seiscientas ) NOTA.

Para demostrarlo Rivest, Shamir y Adleman retaron a la comunidad matemática. Publicaron un número de 129 cifras y ofrecieron 100 dólares a aquél que descubriese los factores primos del número en cuestión. Al final sólo se necesitaron 17 años para descubrirlos.

Seguro que para entonces ya habrá leído nuestro comprador el maravilloso poema:

Souvent, pour s’amuser, les hommes d’équipage
Prennent des albatros, vastes oiseaux des mers,
Qui suivent, indolents compagnons de voyage.
Le navire glissant sur les gouffres amers.

A peine les ont-ils déposés sur les planches,
Que ces rois de l’azur, maladroits et honteux,
Laissent piteusement leurs grandes ailes blanches
Comme des avirons traîner à côté d’eux.

Ce voyageur ailé, comme il est gauche et veule!
Lui, naguère si beau, qu’il est comique et laid!
L’un agace son bec avec un brûle-gueule,
L’autre mime, en boitant, l’infirme qui volait!

Le poète est semblable au prince des nuées
Qui hante la tempête et se rit de l’archer;
Éxilé sur le sol au milieu des huées,
Ses ailes de géant l’empêchent de marcher.

 

NOTA: Así era el estado de la cuestión en 2007, cuando escribí esta entrada. Vean por dónde andan los números RSA.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s