Búsqueda

jueves, marzo 23, 2006

Numb3rs: una de cal y otra de arena

Hace unas semanas se estrenó Numb3rs, en Antena 3, una serie bastante original en la que un joven genio de las matemáticas ayuda a su hermano del FBI a resolver sus casos. En uno de los episodios de la semana pasada, se tocaba un tema interesante: la posibilidad de reventar las transacciones seguras en Internet.

En el episodio en cuestión, la hija de un matemático es secuestrada. El matemático en cuestión estaba trabajando en uno de los llamados problemas del milenio, la Hipótesis de Riemann, y creía haberla demostrado. Los secuestradores quieren precisamente esa demostración, reducida a un algoritmo. El protagonista explica que posiblemente quieran utilizarla para reventar los códigos que se utilizan en Internet, ya que éstos se basan en números primos, y la Hipótesis de Riemann puede proporcionar una manera rápida de factorizar números grandes. Más adelante descubren que el padre de la niña se había equivocado en sus conclusiones, y no tenía una demostración válida de la hipótesis en cuestión. Así que se inventan un algoritmo que da el pego, y montan una trampa para los secuestradores, de forma que cuando alguien intente conectarse a un determinado servidor (con información confidencial sobre los tipos de interés, me parece) utilizando esa clave falsa, se localiza el punto de la conexión mientras se proporcionan datos falsos para que los secuestradores no sospechen.

Bueno, empecemos por los aciertos. Efectivamente, la Hipótesis de Riemann existe y es uno de los 7 problemas del milenio que el CMI ha seleccionado, y que premia con un millón de dólares a quien los resuelva (un millón para cada problema). ¿De qué va eso de la Hipótesis de Riemann? Bueno, es algo difícil de explicar sin entrar de lleno en el mundo de las matemáticas, pero intentaré dar una explicación de andar por casa. Existe una función llamada función zeta de Riemann (zeta griega, no latina, es decir, ζ), que se representa como ζ(s), y que se define definió inicialmente para todo número complejo (excepto el 1) con parte real mayor que uno, como el sumatorio de 1/ns, con n de 1 a infinito:

Fórmula de la función zeta de Riemann

¿Lo cualo? Veamos, recordemos un momento eso de los números complejos. Un número complejo es un número de la forma a + b i, donde i es la raiz cuadrada de -1 (la unidad imaginaria), a es la llamada parte real, y b la parte imaginaria. El Σ ese (la letra griega sigma mayúscula) es el símbolo matemático para representar un sumatorio. ¿Un qué? Un sumatorio, es decir, una serie de sumas. En este caso, se define como todos los enteros desde 1 a infinito, es decir, que la función dichosa sería algo así como

1/1s + 1/2s + 1/3s + 1/4s + 1/5s + ...

hasta el infinito. Posteriormente se extendió para todo el plano complejo, salvo el 1, de forma que su fórmula ya no se parece al sumatorio.

La Hipótesis de Riemann nos dice que los ceros no triviales de dicha función son números cuya parte real es 1/2. Para entendernos, aquellos valores de s para los que la función se hace cero, son necesariamente de la forma 1/2 + b i. Hay que señalar que esto es una hipótesis conjetura, es decir, se cree que es cierta (y se tiene bastante seguridad de que lo sea), pero matemáticamente no está demostrada. Dicho de otra forma, no se ha encontrado ningún cero que no cumpla esa condición, pero no se ha conseguido demostrar que eso ocurra para todos los ceros.

¿Y qué utilidad tiene todo esto? Pues veréis, el teorema de los números primos nos dice que el número de números primos menores o iguales que un número x, es aproximadamente igual al cociente entre x y el logaritmo neperiano de x, es decir, x/ln(x) cuando x es muy grande. Este teorema nos ayuda para saber si determinado número, demasiado grande para poder ser factorizado en un tiempo razonable, es primo o no, ya que nos dice cuántos números primos hay por debajo del número en cuestión. Si la Hipótesis de Riemann es cierta, la fórmula anterior puede ser mejorada, reduciendo el número de primos posibles.

Resumiendo para los que se hayan podido perder, si la Hipótesis de Riemann es cierta, tenemos una muy buena herramienta para saber si un número (muy grande) determinado es primo o no.

Vale, pero ¿qué tiene que ver esto con Internet? Bueno, olvidémonos un momento de todo lo anterior y adentrémonos en el fascinante mundo de la criptografía. Todo el mundo tiene más o menos una idea de lo que es la criptografía. La idea es cifrar un mensaje de alguna manera, de forma que sea ilegible para el que no sepa descifrarlo. Para ello necesitamos dos elementos básicos: un algoritmo de cifrado, y una clave. Pongamos un ejemplo muy sencillo (y clásico, ya que tengo entendido que se utilizaba en la Roma antigua). Imaginemos que nuestro algoritmo de cifrado consiste simplemente en transformar una letra en otra, desplazando el alfabeto n posiciones. Es decir, si n es 2, tenemos:

A B C D E ... X Y Z
C D E F G ... Z A B

Es decir, la A pasaría a ser una C, la B una D, y así sucesivamente. El texto mensaje se convertiría en ñgouclg.El número de posiciones a desplazar sería la clave. En este ejemplo concreto hemos utilizado el 2 como clave, pero podríamos utilizar otro número. Para descifrar el texto, debemos aplicar un algoritmo inverso, con la misma clave. En este ejemplo, el algoritmo inverso sería desplazar las letras en el otro sentido:

A B C D E ... X Y Z
Y Z A B C ... V W X

Y así, ñgouclg se convertiría en mensaje. Esto es lo que se conoce como cifrado simétrico, ya que se utiliza la misma clave para cifrar y descifrar. El principal inconveniente de este tipo de cifrados es el distribuir la clave por un canal seguro, de forma que sólo su legítimo destinatario la reciba. Si alguien intercepta la clave, podrá descifrar todos los mensajes.

Existe otro tipo de cifrado, llamado asimétrico, en el que se utilizan dos claves relacionadas, de forma que si se cifra con una, se debe descifrar con la otra, y viceversa. Si mantenemos una de ellas secreta, y sólo entregamos la otra, cualquiera puede cifrar mensajes que sólo yo puedo descifrar. Y al revés, si yo cifro un mensaje, cualquiera puede descifrarlo, pero sabe que sólo yo he podido cifrarlo (no ha sido un impostor). Esto es lo que se conoce como sistemas de clave pública: de la pareja de claves, una se distribuye libremente (clave pública), y la otra se mantiene secreta (clave privada). Estos sistemas son ampliamente utilizados en informática, tanto para cifrar mensajes como para firmarlos digitalmente. En efecto, si yo cifro un mensaje con mi clave privada, existe la certeza de que sólo yo he podido cifrar ese mensaje, por lo que es el equivalente a una firma.

¿Cómo se consigue esto? Aquí debemos abandonar los ejemplos sencillos. La criptografía asimétrica se basa en algoritmos no reversibles, es decir, no tienen un algoritmo inverso. Además, tienen la peculiaridad de que una pareja de claves se relaciona de la forma mencionada antes. Si cifro con una, al aplicar el mismo algoritmo sobre el texto cifrado, con la otra clave, en realidad lo estoy descifrando (aunque existen sistemas en los que los algoritmos de cifrado y descifrado son diferentes, como en ElGamal). Un punto fundamental es que la relación entre las claves no es evidente, es decir, no se puede deducir la clave privada a partir de la clave pública.

La base de todo este tinglado son los números primos. Voy a explicar de forma sencilla uno de los algoritmos de cifrado asimétrico más utilizados: RSA. La generación de la pareja de claves en RSA se hace de la siguiente manera:

  1. Buscamos dos números primos distintos (y bastante grandes), a los que llamaremos p y q.
  2. Obtenemos el producto de dichos números (p · q), al que llamaremos n.
  3. Obtenemos el producto de los dos números primos menos uno, es decir (p-1)(q-1), al que llamaremos z. Ésta es la llamada función φ de Euler, y nos indica el número de todos los números primos con n, menores o iguales que n. Dos números primos entre sí, son dos números cuyo máximo común divisor es 1, y no quiere decir que sean necesariamente primos. Por ejemplo, 25 y 12 no son primos, pero son primos entre sí.
  4. Buscamos un número primo, menor que z, y primo con z, es decir, que no sea factor de z, o dicho de otra manera, que z no sea múltiplo de ese número. A este número lo llamaremos e.
  5. Buscamos un número, al que llamaremos d, tal que su producto con e, se pueda dividir entre z, danto como resto 1 (recordáis lo que es el resto de una división ¿no?). O dicho de otra manera, d·e - 1 es divisible entre z.

Una vez hecho esto, resulta que estos números tienen unas propiedades muy interesantes. Si yo cojo un número cualquiera m, y realizo la operación me mod n (donde mod se refiere al resto de la división, es decir, calculo el resto de me/n), obtengo un número, al que llamaremos c, que cumple lo siguiente: m= cd mod n. Es decir, si utilizo e, como exponente, obtengo un número, al que si le aplico el mismo algoritmo, pero con d como exponente, me da el número original. Así que ya tenemos nuestra pareja de claves. El par (e, n) sería la clave pública, y el par (d, n) sería la clave privada.

Fijáos que hemos calculado e y d a partir de z, pero este último número no lo necesitamos para nada una vez calculadas las claves, y por tanto lo podemos borrar para siempre (al igual que los números p y q). Si conocieramos z, podríamos deducir una clave a partir de la otra. Y para obtener z, necesitamos factorizar n (es decir, obtener los números primos que lo componen, p y q). Y aquí está todo el meollo de la cuestión. Con nuestro conocimiento actual de matemáticas, tenemos herramientas para saber si un número es primo o no, sin necesidad de factorizarlo. Factorizar un número suficientemente grande, puede llevar siglos aunque utilicemos los ordenadores más rápidos del mundo, mientras que averiguar si un número del mismo tamaño es primo o no, se puede hacer en segundos (o minutos). Esto quiere decir que si encontramos una forma de factorizar números grandes en poco tiempo, habremos reventado el algoritmo RSA.

¿Cómo de grandes son los números de los que estamos hablando? Pues de cientos de dígitos. Actualmente se utilizan en la mayoría de los casos, números de 1.024 bits, que tienen algo más de 300 dígitos. Pero últimamente se ha puesto en tela de juicio si ese tamaño es suficiente, por lo que ahora se recomiendan números de 2.048 bits, lo que nos daría números de más de 600 dígitos. ¿Podéis imaginarlo?

Una vez entendido todo esto (o eso espero), volvamos al episodio de Numb3rs. El prota nos explica que la demostración de la Hipótesis de Riemann puede utilizarse para ayudar en la factorización de números grandes, limitando múcho el número de primos con los que probar. Pero lo cierto es que lo que nos ayuda con los números primos es la hipótesis en sí. Es decir, yo me creo que es cierta, y utilizo ese conocimiento. De hecho, existen métodos para comprobar si un número grande es primo o no, basados precisamente en la suposición de que la Hipótesis de Riemann es correcta. Es decir, la demostración en sí no nos ayudaría en nada. Tal vez, y sólo tal vez, exista la posibilidad de que en el desarrollo de la demostración, aparezcan nuevas fórmulas que nos permitan reducir el tiempo de cómputo en la factorización de un número grande. Pero eso es sólo una hipótesis.

Luego existe otro problema. Supongamos que la demostración de la Hipótesis de Riemann nos ayuda a factorizar un número grande, y por tanto, a obtener una clave privada a partir de su pareja pública. En el episodio, los matemáticos no lo consiguen, y les dan a los secuestradores un algoritmo que da el pego. Pero dar el pego no es suficiente. ¿Qué es lo primero que harían los secuestradores con el algoritmo? Obtener lo que creen que es una clave privada, a partir de una pública. ¿Y lo segundo? Pues comprobar que esa clave privada corresponde a la pública. Es decir, cifrar un texto cualquiera con una de ellas, y descifrarlo con la otra. Y si no funciona, pues en seguida se darían cuenta.

Lo cuel nos lleva a otro problema. En el episodio, una vez montan la trampa, empiezan a hablar de la clave falsa y la cerradura falsa. Pero no hay una única clave falsa. ¿Cómo acceder de forma ilegítima a un servidor, suponiendo que tengas un método para obtener claves privadas a través de las públicas? Pues obteniendo la clave pública de un usuario legítimo (a través de su certificado digital, que básicamente es la clave pública junto con otros datos personales, firmados digitalmente por una entidad de certificación de confianza), y calculando la clave privada correspondiente. De esta forma, el secuestrador podría hacerse pasar por el usuario legítimo del certificado (uno de los pasos para la autenticación en este tipo de escenarios, consiste en firmar digitalmente un código aleatorio generado por el servidor entre el cliente y el servidor, es decir, cifrando con la clave privada). Esto quiere decir que la cerradura falsa debería poder identificar todas las posibles claves privadas falsas de todos los usuarios legítimos del sistema (o mejor dicho, identificar el cifrado con una de esas claves). O sea, que no estamos hablando de una única clave, sino de muchas.

Y todo este tinglado lo tienen que montar unos informáticos en unas pocas horas, lo que nos lleva a uno de los topicazos más habituales en estos temas. En el mundo real, sería algo inviable. Hay que modificar el sistema de autenticación para que detecte las claves falsas, montar un sistema parecido al real pero con datos falsos, y hacer que todo funcione sin ningún error. Ahora mismo, en mi trabajo, me dedico a mantener y ampliar una aplicación en Internet (varias relacionadas entre sí, en realidad) en la que los usuarios se identifican y a los que se les cobra por un servicio (no, no es ese tipo de servicio). Si me dicen que tengo que modificar todo para dirigir a unos usuarios a datos falsos o reales, en función de determinadas claves, en menos de un día, me parto de risa (o me pego un tiro).

Nota: Corregido el 27 de Marzo de 2006.

Nota: Corregido el 5 de Abril de 2006.

47 comentarios:

  1. Reconozco que me he perdido, casi al final, pero me he perdido. Y eso que te explicas puta madre :( pero soy consciente de mis limitaciones. No obstante me ha quedado claro el porqué de la pifia del episodio.

    ResponderEliminar
  2. Me cuesta seguirte en temas tan tecnicos espero conseguirlo poco a poco. Aunque me ha llamado la atención la serie, seguro que me gustara ¿alguna pista sobre el día y la hora de emisión? Gracias anticipadas.

    ResponderEliminar
  3. La verdad es que es una pena que, aún estando bien informados, los guionistas hallan renunciado a dejar la trama bien cerradita.

    Por cierto, el fallo de guión viene a corroborar que las demostraciones matemáticas no son necesarios en el mundo real ;-)

    ResponderEliminar
  4. Wow..
    La verdad que pagaría para escucharte hablar toda una tarde.
    Me asombra la variedad de conocimientos que tenés.
    Espero que esto no suene gay, hay muchos que confunden.. por las dudas..
    Saludos!

    ResponderEliminar
  5. Genial, como siempre.

    No he visto ese capítulo en concreto, pero creo que, en comparación con las "locuras" que plantean otras series, esta no está tan mal. Eso sí, es una serie de "acción", no un espacio educativo...

    Las demostraciones matemáticas son lo que mueve el mundo. La hipótesis de Riemmann tiene toda la pinta de ser cierta, pero basta que un día aparezca un caso que no la cumpla y todo se viene abajo.

    Lo mismo para la criptografía en general... las fórmulas que cita Alf: [ m^e mod n = c ] y [ m = c^d mod n ] no habrían sido posibles sin la enorme "ristra" de demostraciones anteriores (al menos las de Teoría de Números), incluso creo que concretamente éstas surgieron directamente de otras demostraciones. (Dificilmente te levantas una mañana y dices: Pues hoy voy a intentar demostrar que m^e mod n... bla bla bla)

    Repito: Genial :D

    ResponderEliminar
  6. Pasu madre.. en serio que enmancaré este post. No creo haber leido algo claro para iniciarse en criptologia.

    Saludos.

    ResponderEliminar
  7. Madre mía... esto si que es currarse un artículo... En temas más profanos decirte que como has podido comprobar Antena3 no confía mucho en Numb3rs, ya emite sólo un episodio y en late-night... no creo que veamos una 2ª temporada (si acaban de emitir la primera)

    ResponderEliminar
  8. Como siempre genial

    ResponderEliminar
  9. Brutal!!!! Te superas, Alf!!!

    Por cierto, que la clave de sustitución de letras se le atribuye a César (creo que para enviar mensajes en la guerra de las Galias, pero eso ya no lo tengo seguro).

    ResponderEliminar
  10. Auch me perdí en algún momentno, pero las mates no son mi fuerte realmente.

    Eso no lo le quita lo verdaderamente entretenido que es la lectura de Malaciencia. Lo que daría por que se estrenara uno en particular sobre Malafísica, o Malapata ;)

    ResponderEliminar
  11. Me has hecho recordar los apuntos del año pasado ><, por momentos quería dejar de leer ;).

    Por cierto, que a mi la serie no me parece disparatada, es más, incluso entretenida, y me hace gracia como la mayoría de la gente se pierde con las explicaciones del colega. Eso sí, en el último capítulo dijeron algo de la sucesión de "Finobacci", imagino que habrá sido un error de traducción, pero me hizo gracia.

    Saludos y sigue así que enganchas con los post lo que no está escrito.

    ResponderEliminar
  12. Creo que el tema de modificar la aplicación para que trague las claves falsas no es tan difícil:

    Solución chapuza: Redirigir los errorres de password a la aplicación falsa

    Un poco mas currado. Cuando la clave nos de error, replicar el proceso de generación de clave privada a partir de la pública con el algoritmo "trucho", y comprobar si se ha empleado esa clave privada para generar la respuesta. En caso afirmatívo, redirigir a la aplicación falsa.

    La aplicación falsa podría ser el entorno de testing de los desarrolladores. Tendría que saber el tipo de aplicación, pero creo que esto ya se sale del artículo.

    ResponderEliminar
  13. Alf, habla con los hermanos Scott, a ver si hay una vacante de guionista. Imprescindible inglés.

    ResponderEliminar
  14. Este comentario ha sido eliminado por un administrador del blog.

    ResponderEliminar
  15. Vi los dos primeros capítulos de la serie y no me convencieron nada. De hecho hice una entrada crítica en mi blog, sin meterme al fundamento matemático con el que juega la serie.

    Os invito a leerla y a dejar comentarios si quereis (es la segunda entrada)...

    http://paradigma.wordpress.com/

    ResponderEliminar
  16. Martin Silennus24 marzo, 2006 11:57

    Excelente post, sobre todo la parte en la que explicas la diferencia entre cifrados simétricos y asimétricos. Por fin veo una explicación clara y concisa sobre este tema.

    ResponderEliminar
  17. Hola Alf,

    descubrí MalaCiencia hace poco y, en cuanto tengo un rato libre, voy leyendo todas las entradas (desde el principio,eh!). Me parece que haces un trabajo realmente bueno y que a más de un periodista o "entendido" le vendría bien leerte de vez en cuando.

    A lo que voy. En este artículo dices (o eso me ha parecido entender) que en el cifrado asimétrico se utilizan dos claves distintas para encriptar y desencriptar, pero un sólo algoritmo. Eso es así en sistemas de cifrado como RSA, pero no así en otros como El Gamal (ver Wikipedia en inglés, en español aún no hay entrada). En él, se utiliza un algoritmo para la encriptación del mensaje (plain text)
    y otro diferente para desencriptarlo.
    Puede que esté metiendo la pata,pero creo que es así. Otra cosa es que hacen uso de la mismas operaciones (exponenciación "modulo n", producto...).

    Espero que haya sido útil. Y si estoy equivocado, por favor, sacadme de mi error.

    Saludos,

    Álvaro

    ResponderEliminar
  18. Impresionante. La primera vez que entiendo como funciona el cifrado RSA.

    Tengo una duda con otro tipo de cifrado, el que usan los ZIP. ¿la única forma de forzarlos es el método de fuerza bruta? tengo un zip antiguo del que he olvidado la clave, y no hay forma de recuperarlo.

    ResponderEliminar
  19. OLÉ !!!

    LLevo varios meses leyéndote, y nunca me había animado a comentar, pero lo de hoy me ha dejado de piedra. Fantástico, genial, extraordinario.. (y no, no soy tu madre)

    Enhorabuena y gracias por el blog, campeón !!!

    ResponderEliminar
  20. Vaya, no conocía el algoritmo ElGamal, pero sí, son dos algoritmos diferentes. En cuanto pueda, corregiré un poco el texto.

    Num3rs es una serie atípica, no sólo por la temática, sino porque los guinostas se han molestado en buscar asesores. Según parece, varios matemáticos del California Institute of Technology trabajan como asesores de la serie. Por eso, a pesar de los inevitables gazapos (supongo que por exigencias de ritmo, narrativa o interés de la historia) hay también aciertos.

    Espero que A3 no la maltrate con los horarios, o la arroje al olvido, como suele hacer con todas sus series.

    Creo que Rodrigo se llevaría una decepción si tuviera que oírme hablar toda una tarde :-) La gran ventaja de escribir sobre hablar es que tienes tiempo para ordenar tus ideas, corregir la redacción, documentarse... hasta que el texto quede como uno cree que es mejor.

    Sobre el problema de Fernando... pues habría que averiguar qué tipo de encriptación se usa. Cuando hablas de ZIP, ¿te refieres a un fichero comprimido (.zip), o a un disco Zip extraíble (zip drive)? En cualquier caso, me temo que a menos que se haya utilizado algún algoritmo "reventado", habrá que usar furza bruta.

    ResponderEliminar
  21. Una explicación muy, pero muy clara de como funciona el algoritmo de cifrado asimétrico. Me perido en algunos puntos, pero es responsabilidad mía por dejar tanto tiempo oxidada la mate.

    No he visto la serie todavía, pero promete ser bastante friki.

    Me parece que te citaré como fuente para un post que estoy escribiendo.


    saludos

    ResponderEliminar
  22. Excelente la explicación del cifrado.

    ResponderEliminar
  23. Jaja, pues te doy tiempo para que prepares una charla :)
    Saludos!

    ResponderEliminar
  24. ¡¡Enhorabuena por el artículo!!

    Lo encuentro tan elaborado que no me resisto a hacer algunas observaciones que normalmente obviaría por ser nimiedades, pero que en vista del nivel y la calidad de tu artículo no me resisto a comentártelas:

    - Cuando dices "Hay que señalar que esto es una hipótesis, es decir, se cree que es cierta (y se tiene bastante seguridad de que lo sea), pero matemáticamente no está demostrada." Sería más preciso hablar de "conjetura" que de "hipótesis".

    - Cuando hablas de los números "primos entre sí", podría ayudarte a simplificar la redacción de alguna frase si introdujeses el término de números "coprimos".

    - En esta expresión "(uno de los pasos para la autenticación en este tipo de escenarios, consiste en firmar digitalmente un código aleatorio generado por el servidor, es decir, cifrando con la clave privada)", se introduce una variación respecto al funcionamiento real de los protocolos TLS/SSL. Sería más preciso hablar de "firmar digitalmente un código aleatorio generado entre el cliente y el servidor", ya que de lo contrarío el protocolo SSL tendría un agujero de seguridad que hemos comentado hace unos días por aquí.

    ResponderEliminar
  25. Aquel que hizo el comentario de que "Por cierto, el fallo de guión viene a corroborar que las demostraciones matemáticas no son necesarios en el mundo real", no quisiera menospreciar a nadie pero seguramente es informático o ingeniero, porque no entiende que la criptografía es una aplicación al mundo real de muchísimos resultados de la teoría de números que no serían usados si las demostraciones no se hubieran hecho, así como la teoría de complejidad. En resumen, sin las demostraciones, o sea, sin los teoremas, cualquier algoritmo que use resultados de matemáticas sería un algoritmo ineficaz pues no estaría asegurado que siempre regresara resultados correctos, pues pudiera ser que se toma un resultado intuitivo sin demostración y en un de esas de pura suerte encuentras el contraejemplo de tu resultado y adiós algoritmo, no sirve, porque existe un caso en el que el resultado está mal, y supón que excluyes ese caso, pero no sabes si hay más casos así, ahora sigue indefinidamente. Así que moraleja importante, la computación, la verdadera computación va de la mano de las matemáticas, seguramente Alf estará de acuerdo.

    ResponderEliminar
  26. El artículo un 10. Y le subo a un 10+1 si añades los pequeños comentarios que te han hecho.
    Antena3 ni llega al 3. Para empezar ya se ha saltado el capítulo 4. Me temo que alguna nos liarán. Siempre nos quedarán las VO+Subs

    ResponderEliminar
  27. El otro día en el capítulo "vectores", el matemático hablaba del "teorema de gráficos", cuando se refería al "teorema de grafos", inventado por Euler para resolver el problema de los puentes de Königsberg.
    Parece un fallo de traducción.

    Pese a estas cosillas, la serie está bien
    ;)

    ResponderEliminar
  28. En el comentario del otro día, se me olvidó añadir una cosa: tanto en el algoritmo de El Gamal (para desencriptar), como en RSA (para calcular la clave privada d), las operaciones se realizan TODAS en "módulo". Es decir, donde veamos un (x)^{-1} no quiere decir que tengamos que calcular (1/x), sino, como dice Alf en el artículo, el número que multiplicado por 'x' y dividido entre 'z' dé resto igual a 1.

    Lo mismo ocurre con la exponenciación: se opera (g^y)mod(z). Es decir, nos quedamos siempre con el resto

    Álvaro

    ResponderEliminar
  29. InCreiBle!!!!! Hay que quitarse el sombrero.
    Joer tio, por ke no te dedicas a dar clase en la facultad, por ke mas de un profe de algebra o de fisica no tiene ni pajolera idea de explicar.
    ALF FOR PRESIDENT!!!!!

    ResponderEliminar
  30. Gracias por las correcciones, he actualizado el artículo con ellas. Aunque no he utilizado el término "coprimos", ya que no parece estar en el diccionario de la RAE. Es más, en la versión española de la Wikipedia no utilizan esa palabra mientras que en la inglesa sí (bueno, coprimos no, sino coprimes).

    Y por supuesto que estoy de acuerdo con los comentarios sobre la necesidad de las demostraciones y tanta matemática teórica. Un ingeniero puede no necesitar conocer las demostraciones, pero sin ellas, la base de su trabajo podría estar equivocada. Por cierto, que esto del cifrado asimétrico es un muy buen ejemplo de que el tópico de hacker hollywoodense es erróneo. Para reventar el algoritmo RSA, no hay que ser un genio informático, o un experto en seguridad. Hay que ser un genio en matemáticas (y en una rama muy concreta).

    ResponderEliminar
  31. Excelente artículo, lo he leído hasta el final y me parece impresionante la claridad de la exposición. En otras ocasiones cada vez que leo la palabra 'encriptar' dejo de leer inmediatamente porque no me inspiran confianza. No ha sido este el caso. Un gran trabajo didáctico.

    ResponderEliminar
  32. Pues hoy hay una noticia en Slashdot.com que habla de la hipótesis de Riemann precisamente, parece que está de moda

    http://science.slashdot.org/article.pl?sid=06/03/27/1315212&from=rss


    http://www.seedmagazine.com/news/2006/03/prime_numbers_get_hitched.php?utm_source=seedmag-main=rss

    ResponderEliminar
  33. Alf, me refería a los ficheros .zip. El cifrado que tienen se puede romper si tiene una version desencriptada de al menos uno los archivos que contiene. Que no es el caso, por lo que la unica opcion es fuerza bruta.

    ResponderEliminar
  34. En otras ocasiones cada vez que leo la palabra 'encriptar' dejo de leer inmediatamente

    Je, ya me dieron un tirón de orejas en su día por utilizar "encriptar" y desencriptar", que no están admitidas por la RAE. Intento no repetir errores :-)

    ResponderEliminar
  35. Muy bueno el post y el blog en general, os habéis ganado un enlace ;-)
    Sólo voy a permitirme una puntualización pedante, para destacar entre tanto halago: la función zeta no se define según ese sumatorio para todos los complejos distintos de 1, sino tan sólo para los que tienen parte real estrictamente mayor que 1. Esa función luego se extiende al resto del plano complejo (salvo el polo en s=1) por extensión analítica, pero su fórmula no se parece ni de lejos al sumatorio (que es divergente en todo ese semiplano). La distinción es irrelevante para el lector general, pero si tienes alguno interesado en resolver la hipótesis de Riemann, le vendría bien saber que la fórmula con la que tiene que lidiar es otra ;-)
    La serie esa parece interesante, pero por guirilandia no la retransmite, intentare hacerme con un par de capítulos, a ver qué tal está.

    ResponderEliminar
  36. Gracias por la matización. Debería haberme fijado mejor, ya que la entrada de la Wikipedia lo explica así.

    En cuanto pueda, lo corregiré.

    ResponderEliminar
  37. Hola:

    Hay un error de concepto bastante gordo en esta entrada. Que la veracidad de la hipótesis de Riemann permita mejorar la aproximación asintótica del número de primos NO implica que podamos saber con mayor facilidad (ni siquiera con mayor probabilidad) si un determinado número es primo o no, por muy grande que sea.

    Supongo que este error se extiende también al capítulo de Numb3rs (que no he visto).

    Un saludo. Jose Brox

    ResponderEliminar
  38. Hombre, según la Wikipedia, el test de Miller-Rabin, se basa en que la Hipótesis de Riemann sea cierta para determinar si un número es primo o no.

    ResponderEliminar
  39. El test de Miller-Rabin no determina la primalidad de un número, sino su posible primalidad. La diferencia es sustancial y debe ser tenida en cuenta. A efectos prácticos pueden servir los PRPs y SPRPs como si fueran primos, pero a nivel teórico no.

    Es cierto que si la RH es cierta, entonces se puede mejorar la probabilidad en el algoritmo, en el sentido de que se puede obtener el mismo grado de certeza con un número menor de pasos.

    Un saludo. Jose Brox

    ResponderEliminar
  40. Hola, ayer creo que fue la primera vez que leí este blog y debo decir que me ha encantado. De segro tienes otro lector fijo XD. Bieno, ya de paso, donde dices
    Buscamos un número primo, menor que z, y primo con z, es decir, que no sea factor de z, o dicho de otra manera, que z no sea múltiplo de ese número. A este número lo llamaremos e.
    Es una redundancia, ya que cualquier número primo es primo entre sí con todos los demás.

    ResponderEliminar
  41. Un número primo sólo es primo con los números menores que él, pero puede ser (y de hecho es), factor de números mayores.

    Por ejemplo, 7 es un número primo, pero 7 y 14 no son primos entre sí, pues 14=7*2. A eso me refería.

    ResponderEliminar
  42. Ni diea quien eres, llegue a este blog por un amigo

    Felicitaciones, muy bien explicado todo

    AdeW!

    ResponderEliminar
  43. Cuendo me aburro me pongo a leer entradas anteriores de tu blog siguiendo enlaces de unos a otros y la barra de "envios anteriores"...Es la tercera vez que creo haber leido todo y aparecen envios que desconocia. Mejor, asi no me quedo sin leer.

    ResponderEliminar
  44. NO SABIENDO DONDE PONER ESTO OS PONGO EN COMENTARIO DE SU ULTIMO ARTICULO, PROCURANDO QUE OS SEA DE INTERES PUBLICO...

    Logran controlar el spin de un electrón simple.
    Longinos, 20/08/2006 (10:37).

    El control del spin permitiría su aplicación como bit cuántico, elemento básico para el desarrollo de los ordenadores del futuro.

    Investigadores del Instituto Kavli de Nanociencia de la Universidad Tecnológica de Delft y la Fundación para la Investigación Básica de la Materia (FOM), en Holanda, han logrado por primera vez en la historia controlar el spin de un electrón simple en una nanoestructura, siendo capaces de hacerlo rotar en cualquier dirección y medirlo adecuadamente.

    Este logro abre la vía para la aplicación del spin de un electrón como ?bit cuántico?, la base para un futuro (todavía teórico) ordenador cuántico.

    La revista Nature recoge en su número del 17 de agosto el artículo que sobre este gran avance científico han elaborado los investigadores responsables del mismo.

    El resto del artículo en Astroseti.org:




    ENLACES RELACIONADOS

    Artículo en Astroseti.org.

    ResponderEliminar
  45. De hecho los hindúes Agrawal, Kayal y Saxena en el 2002 encontraron un algoritmo determinístico para demostrar la primalidad de un número y que es polinomial. Aunque todavía no ha podido implementarse de modo que sea práctico, creo que debió mencionarse tal hecho.

    ResponderEliminar
  46. Genial!
    Tenía que hacer un trabajo sobre la relación entre los números primos y los gigantes y me has ayudado muchísimo. Me alegra ver que hay gente que es capaz de expresarse claramente para que los no iniciados entendamos las Matemáticas XDD
    Muchas gracias!!!

    ResponderEliminar