267-1 = 193.707.721 x 761.838.257.287
Frank Nelson Cole, durante tres años de su vida, 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 puede conocer cualquiera, porque una vez utilizado, sólo el que conoce una fórmula secreta puede desencriptar el dato oculto. 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 Leonard Adleman y Adi Shamir. Y 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 300 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. Un ejemplo, una calculadora con p=7 y buscamos un número cualquiera, véase 2. Ahora elevamos 2 a la séptima potencia
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, si elevamos un número cualquiera a la potencia que resulta de (p - 1) x (q-1) + 1, el resultado, en el reloj con N horas, sería ese número cualquiera.
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.
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 y que tienen guardados bajo llave.
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. O lo que es lo mismo, el exponente C tiene un pariente, un exponente D (obtenido de los números primos p y q) que, aplicado al número resultante del cifrado, nos da el número de la tarjeta de crédito (Nota).
En resumen, el problemilla es simple, hallar los primos con los que se obtiene N. Cosa de nada.
Fermat y Euler estarían encantados.
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.
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.
(Escrito por Tsevanrabtan)
Nota:
Aquí tenemos un ejemplo de cifrado/descifrado con RSA.
| p=61 | 1º nº primo Privado |
| q=53 | 2º nº primo Privado |
| n=pq=3233 | producto p*q, Público |
| e=17 | exponente Público |
| d=2753 | exponente Privado. Satisface e*d=(p-1)*(q-1)*x+1. En el ejemplo 2753*17=60*52*15+1 |
La clave pública (e, n). La clave privada es d. La función de cifrado es:
-
- encrypt(m) = me(mod n) = m17(mod 3233)
Donde m es el texto sin cifrar. La función de descifrado es:
-
- decrypt(c) = cd(mod n) = c2753(mod 3233)
Donde c es el texto cifrado. Para cifrar el valor del texto sin cifrar 123, nosotros calculamos:
-
- encrypt(123) = 12317(mod 3233) = 855
Para descifrar el valor del texto cifrado, nosotros calculamos:
-
- decrypt(855) = 8552753(mod 3233) = 123
Para romper el código 'basta' con factorizar n (público). Es decir, determinar p y q. Como e es también público, se puede entonces (sólo entonces) determinar d.
Etiquetas: Tsevanrabtan
«El más antiguo ‹Más antiguo 201 – 289 de 289