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/n^s, con n de 1 a infinito:

¿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/1^s + 1/2^s + 1/3^s + 1/4^s + 1/5^s + ...

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 m^e mod n (donde mod se refiere al resto de la división, es decir, calculo el resto de m^e/n), obtengo un número, al que llamaremos c, que cumple lo siguiente: m= c^d 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.