miércoles, 17 de febrero de 2010

Por qué el 1 dejó de ser un número primo.

A Vanbrugh

Supongamos que tenemos que enviar un mensaje en el interior de un pequeño baúl. Afortunadamente podemos comprar un candado inviolable marca ACME. Así que se lo ponemos a nuestro baúl y enviamos el mensaje a nuestro destinatario, quien naturalmente no puede abrir el baúl, a menos que le enviemos la llave. Pero claro, si le enviamos la llave, y ésta y el baúl son interceptados, el secreto dejaría de secreto. Parece que estamos en un buen lío. ¿Alguna idea?

Cinco minutos para pensar

Solución: Cuando el destinatario reciba el baúl, le pone otro candado inviolable marca ACME y nos devuelve la caja con los dos candados. Al recibirlo, le quitamos nuestro candado y se lo devolvemos. Cuando él lo vuelva a recibir, lo único que tiene que hacer es quitarle su candado y leer el mensaje. Si durante el proceso, el baúl es interceptado, el mensaje estará a salvo ya que el ladrón no ha tenido acceso a las llaves.

Como vemos la clave de todo este proceso es que los usuarios legítimos tengan un procedimiento sencillo para abrir o cerrar el baúl -la llave-, pero los ladrones lo tengan crudo.

Pues así es, más o menos, como se codifican y transmiten hoy en día los mensajes secretos. Para hacerlo, se utilizan unas funciones, que en matemáticas se las conoce con el nombre de funciones trampa, que no son más que funciones cuyo cálculo directo es sencillo (por ejemplo, la multiplicación), pero en la que el cálculo de la función inversa es muy complejo, es decir, involucra un número muy elevado de operaciones. (Por ejemplo, la descomposición en factores primos)

Ejemplo: Con lápiz y papel multiplicad 1756 x 5673. Tratad ahora de descomponer ahora en factores primos el número 357462.

Así pues los pasos a seguir son:
  1. El mensaje se convierte en un número (n). Este procedimiento puede ser público (i.e. conocido por todo el mundo). Por ejemplo, asignamos a la A el número 11, a la B el 12, y así sucesivamente.
  2. A continuación el emisor multiplica el número resultante (n) por un  número primo (p) gigantesco (y cuando hablo de gigantescos me refiero a números de más de 100 cifras) y envía el producto (np) al receptor.
  3. El receptor multiplica el número recibido (np) por su propio número primo, también gigantesco, (q) y devuelve el resultado (npq) al emisor.
  4. El emisor lo divide por su número primo (p) y devuelve el resultado (nq) al receptor
  5. El receptor solo tiene que dividir por su propio número primo (q) para obtener el número original (n).
  6. Como el procedimiento utilizado para convertir el mensaje en el número es público, el receptor no tiene ninguna dificultad en recuperar el mensaje.
Naturalmente la clave de todo este procedimiento se basa en ser capaces de obtener números primos gigantescos, lo que no es tarea fácil. También es evidente que el método será seguro mientras no seamos capaces de factorizar un número grande de forma rápida.

Y para estar seguros de que todo funciona, hay que dotar a todo el proceso del correspondiente armazón que nos asegure que no se va a ir todo al garete a la mínima de cambio. De ello se ocupa una rama de las matemáticas que se denomina teoría de números y los tipos (y tipas) que se han dedicado a este campo utilizan para generar y para probar si un número es o no primo una serie de funciones, como por ejemplo la función de Euler, que tienen la particularidad de que algunas de las propiedades que presentan al aplicarse a los números primos, no se cumplen con el número 1. Así que los matemáticos tuvieron las siguientes opciones:
  • Opción (a). Añadir la coletilla 'salvo para el número 1' a todas las propiedades que verificasen los números primeros, salvo el 1.
  • Opción (b). Declarar solemnemente que el número 1 ya no es un número primo.
Y como los matemáticos son unos fanáticos del principio de economía, pues su elección fue fácil.

Notas:
El método descrito es uno de los que se utiliza para codificar mensajes, no el único.
Si alguien se anima, puede aplicar el procedimientos descrito a una frase, utilizar está página para generar números primos y enviarme el resultado.

Para saber más:
John D. Barrow, ¿Por qué el mundo es matemático?, Barcelona, Grijalbo-Mondadori, 1997, 137 pp.  ISBN: 84-253-3123-4

26 comentarios:

Vanbrugh dijo...

Cuando escribí, en un comentario en el blog de Miroslav (http://desconciertos3.blogspot.com/2010/02/acertijo-logico.html?showComment=1266329404929#c7631633933938408263) que la convención de no considerar primo al 1 me parecía injustificada y arbitraria, me expresé mal. Es evidente que no podía ser injustificada -otra cosa es que no conociera yo la justificación- y era evidente también que, como tal convención, sería saludable y legítimamente arbitraria. El 1 tiene la mala costumbre de ir por libre y permitirse absurdas excepciones a reglas que todos sus congéneres cumplen dócilmente, y algo había que hacer con él.

Me ha encantado el post. Muchas gracias por la dedicatoria.

Guiss dijo...

Yo seguía pensando que el uno era primo, desde que se me atragantaron las derivadas y las integrales no he levantado cabeza y a estas alturas no creo que la levante. De hecho, cuando veo "Numbers", la serie, me da igual que expliquen algo, para mí es como si me dijesen que el matemático lo sabe porque tiene un pálpito. Así que tienes mucho mérito explicando, porque creo que he entendido el mecanismo que explicas en tu artículo. Eso sí, he cerrado deprisa lo de la función de Euler, todavía tengo la carne de gallina :P
Mira tú el uno, qué sorpresas...

Vanbrugh dijo...

8058031053
49763852764457
5316424110
10490381953
66859496667048700000
911874453262
7682754057
529957139305

Miroslav Panciutti dijo...

A mí también, como a Vanbrugh, me llamó la atención la cuestión de la "primalidad" del uno y la consulté brevemente sobre la marcha, así que ya sabía que el uno no era primo "por convenio" y que se debía a que no cumplía condiciones que sí cumplían los demás primos. Seguramente, yo habría optado por la opción 1 que planteas, o, si no, habría cambiado la definición de "primo", que, en todo caso, creo que es lo que los matemáticos deberían hacer.

De todas formas, me ha encantado tu explicación "criptográfica" y el ejemplo de los dos candados y el producto de los primos. Eso sí, no me atrevo de momento a "encriptarte" una frase.

Numeros dijo...

2417105067023420283256710015721146289625700318439432181179001768298196
8577114725941159938194581011652651925916065

Numeros dijo...

Que quede claro que el ejemplo del baúl no es de mi invención (snifff)

Guiss ¿Derivadas, integrales...? No prometo nada, pero haré lo que pueda.

Vanbrugh dijo...

Después de las excelentes explicaciones de Números quedó claro que la gracia de este sistema de encriptación estaba en la dificultad de factorizar rápidamente números grandes; y que para que esa dificultad juegue en favor del encriptador y en contra del desencriptante es fundamental usar números primos gigantescos ¿verdad?

Bueno, pues yo voy y en mi mensaje de un para de comentarios más arriba, separo la frase en palabras y las multiplico todas por el mismo primo, para colmo de seis cifras. Quedan ocho estupendos y cortitos números, todos con un factor común.

O sea, tirado de encontrar, pero con ocho oportunidades distintas, por si se resiste un poco.

Mi futuro entre los encriptadores está en servirles cafés y cogerles los recados telefónicos, sin duda.

Imagino que nuestro amable anfitrión aún está tratando de encontrar las palabras para poderme explicar todo esto sin llamarme abiertamente idiota.

A menos que sea precisamente esto, "idiota", lo que me dice en su mensaje encriptado de respuesta. No me he atrevido a hacer nada con él, por si acaso.

Numeros dijo...

:-D :-D :-D

La verdad es que supone que solo había un número, y el que te devolví era ese número multiplicado por mi primo.

Hay codificar toda la frase en un único número. Por ejemplo

"***********"

Con la clave A->11, B->12; ..., Z->37, espacio en blanco -> 40, quedaría

"nnnnnnnnnnnnnnnnnnnnnnnnnnnn"

Ahora multiplicamos el número por uno primo de más de 100 cifras, aunque nos conformaremos con uno algo más pequeño: 12 cifras. El resultado es:

54779738600653170917745894909220768441094

Que alguien factorice ese número a mano y que nos diga lo que tarda)

Ahora Vanbrugh debes multiplicar ese resultado por tu número primo.

Vamos a ver si hay más suerte.

Nota Cualquiera que tenga el Mathematica puede factorizar el número anterior en aproximadamente 0.01 s. Pero es que hacer el producto le lleva solo 10^(-7) s. Esto es la cienmilésimaparte de tiempo.

Milhaud dijo...

De hecho, este sistema de cifrado es el que se utiliza en la tecnología móvil UMTS (conocida más popularmente como 3G), sólo que el cifrado en esa tecnología exige números de gran tamaño y no un primo cualquiera, por cuestiones de robusted.

Gran artículo.

Anónimo dijo...

Al principio no entendía el ejemplo del Baúl, el truco está en que los candados se ponen 'en serie'

ToniAlumno dijo...

Para el que le interese, esta entrada habla sobre los algoritmos matemáticos de clave asimétrica o de par de claves privada-pública. Son la base para el cifrado de comunicaciones por internet proporcionando varios servicios de seguridad: confidencialidad, autenticación, no repudio, ... Un tema muy interesante que invito a todo el mundo a conocer. 1saludo

Anónimo dijo...

El procemiento de intercambio que has elegido como ejemplo tiene un error.

Si un fisgón captura np, npq y nq entonces puede hallar "n" como el máximo común divisor de estas cantidades.

Tan fácil como:

q = npq/np
n = nq/q

Kor dijo...

Creo recordar una definición de números primos que venía a ser algo así como que un número es primo cuando tiene únicamente 4 divisores enteros (el propio número, el 1, y sus opuestos).
Por lo que el 1 no sería número primo ya que sólo tiene dos divisores (1 y -1).

Julio dijo...

No entiendo por qué, en el algoritmo, p y q tienen que ser primos. ¿Por qué no funcionaría con números cualesquiera?

En cualquier caso lo que dice Manolo es cierto, si hay un fisgón enmedio, el algoritmo no sirve.

Anónimo dijo...

Realmente no has explicado la razón. Has dicho que algunas de las propiedades de la función de Euler no se cumplen, pero nada más.

vitalidad dijo...

Recuerdas fatal Kor, un número primo lo es cuando es divisible (da cero en la división) por él mismo, y por el 1. Por ello el 1 lo cumple.

Anónimo dijo...

Julio, tienen que ser primos para que no los puedas factorizar. En caso contrario se podría acelerar el proceso de desencriptado.

Anónimo dijo...

@Julio

p y q tienen que ser primos pq si fueran compuestos habría más factores en el producto resultante (y más pequeños) y eso haría que factorizarlo fuera más sencillo.

Julio dijo...

@Anónimos, ¿Y? ¿A dónde nos lleva factorizar los productos resultantes?

rvd! dijo...

Iba a postear algo similar a lo que ha dicho Manolo pero con un añadido dedicado a Numeros:

Numero primo de "Numeros": 29996224275833
(el cual es por cierto el 1000000000000avo numero primo).

Es decir, que si A le manda a B np y B le contesta npq, A puede saber cual es el numero primo usado por B. Si ademas A le contesta con nq, entonces B sabe cual es el primo usado por A.

Mi duda ahora es saber si el numero primo usado por A y B cambia para mensaje.

En caso de que no, bastaria con mandar un email "codificado" a la victima y esperar a que nos responda para tener su numero primo. Luego con interceptar los mensajes "np" de A, nos bastaria con dividir por el primo que le hemos sacado y descifrar los mensajes.

Salu2!

rvd! dijo...
Este comentario ha sido eliminado por el autor.
rvd! dijo...

UPDATE:
"Numeros", este era tu mensaje: HOLASOYVANBUGH (1826221130263633112412321718). Te faltaron los espacios y la R!

El metodo seguido ha sido saber cual era tu primo y aplicarlo al "mensaje interceptado". Para obtener tu primo se podia haber hecho de dos formas:

1) Usando un mensaje previo (de tu anterior comentario yo ya tenia NP y NPQ)

2) Factorizando tu mensaje:
2 2819 6043 51349 7765489 134423407 29996224275833

Por otro lado me gustaria comentar que el ejemplo del baul aunque es muy facil de entender, no es 100% valido ya que con los mensajes cifrados siguiendo este metodo SE ENVIA LA LLAVE mientras que con los baules tan solo se envian los candados.

PD: Para los que quieran descargar una calculadora cientifica de hasta 10000 digitos: http://gc3.net84.net/bcalc.htm

Salu2!

sherpa dijo...

se me ocurre una pregunta

en el mundo de los candados, si nuestro amigo nos enviase un candado abierto, quedándose él la llave, nosotros cerraríamos el cofre con su candado y se lo enviamos tranquilamente

supongo que la analogía al mundo de los números sería que ambos extremos tuviesen un algoritmo de encriptación basado en ese número, pero hay alguna herramienta que nos permitiese hacer esto con desconocidos?

Anónimo dijo...

4

Anónimo dijo...

Tio, felicidades por el post. Muy bueno :D

Saludos, Newlog

RauBn dijo...

Ahora supongamos que recibo en mensaje con los dos candados, el mío y del par; m=npq. Con n el mensaje original, p mi clave y q la suya.

Entonces para adivinar la clave q del par sólo tendría que hacer q=m/(np).

Si las claves fueran estáticas sólo tendría que enviar un mensaje para conseguir la clave del par....