RSA: la seguridad de tu dinero depende de él.

Los ciéntificos Ron Rivest, Adi Shamir y Leonard Adleman, crearon el algoritmo de cifrado RSA en 1978 en el MIT. El RSA es un tipo de algoritmo de cifrado llamado de clave pública, porque no necesitas guardar en secreto la clave para cifrar el mensaje. A esta clave la llaman pública porque la puedes distribuir sin peligro. Esto es debido a que la clave para descifrar, llamada clave privada, es distinta e imposible de calcular para un ordenador actual. En la frase anterior, podemos cambiar descifrar por cifrar y viceversa, es decir, podemos usar la clave pública para descifrar y la privada para cifrar. En este punto, tengo que matizar que en realidad no es que sea imposible para el ordenador hacer el cálculo de la clave privada, sí puede hacerlo, lo que ocurre es que si la clave es muy larga, puede necesitar miles de años para encontrar la solución. Conforme los ordenadores van aumentando de rendimiento, parece que es más fácil romper el cifrado RSA, ya que disminuye el tiempo para encontrar la solución, pero simplemente aumentando un bit más el tamaño de la clave, el algoritmo vuelve a ser seguro, dado que el tiempo necesario para alcanzar la solución crece exponencialmente.

Hace 20 años un pequeño grupo de criptógrafos organizaron la primera edición de una conferencia llamada RSA. Hoy día se ha convertido en la conferencia anual de seguridad informática más importante del mundo y durante esta semana se está celebrando en San Francisco. En la conferencia RSA de este año, el tema principal se titula "Las aventuras de Alice y Bob". En la jerga criptográfica, siempre que se va a explicar un protocolo de cifrado, se usan los nombres ficticios Alice y Bob, para representar a la persona que está en el ordenador A y a la persona que está en el ordenador B, respectivamente. Esta nomenclatura inicialmente fue utilizada por Rivest para exponer el RSA, a la que más tarde, Bruce Schneier (autor del libro "Criptografía aplicada"), agregó otros personajes más: Caroline (la persona en el ordenador C), Mallory (el malvado atacante), Eve el espía, Walter el guardián y Sara (un servidor).

El algoritmo de clave pública RSA funciona de la siguiente manera. Supongamos que Alice quiere enviarle un mensaje cifrado a Bob:

1. Alice le dice a Bob que quiere enviarle un mensaje cifrado.
2. Bob envía su clave pública a Alice.
3. Alice cifra con la clave pública el mensaje para Bob.
4. Bob descifra el mensaje de Alice con su clave privada.

En el caso de ejemplo puedes imaginar que eres Alice conectándote al servidor de tu banco (Bob), la clave pública viene en el certificado que tienes que aceptar en tu navegador. Después el navegador se encarga de cifrar el mensaje. La conexión por https en realidad es un poco más complicada, ya que el mensaje que envía Alice en el paso 3, en realidad es una clave de un algoritmo de cifrado de clave privada. De esta manera, en los siguiente envios, la información se cifra usando el algoritmo de clave privada ya que es menos costoso computacionalmente que el de clave pública.

La firma digital es igual de sencilla. Supongamos que Alice quiere enviar un mensaje firmado a Bob:

1. Alice envía el mensaje a Bob.
2. Bob se lo guarda a la espera de que llegue la firma que le verifique que es de Alice.
3. Alice envía su clave pública a Bob.
4. Alice crea su firma cifrando el mensaje con su clave privada y lo envía a Bob.
5. Bob descifra el mensaje con la clave pública de Alice.
6. Si el mensaje que obtiene Bob en el paso anterior coincide con el que le llegó en el paso 1, entonces Bob puede estar totalmente seguro que ese documento es de Alice y que no ha sido modificado por el camino, ya que Alice es la única que puede cifrar un mensaje que pueda ser descifrado con su clave pública.

¿Y si Alice quiere enviar un mensaje cifrado y firmado a Bob? Entonces se haría de la siguiente forma:

1. Bob envía su clave pública a Alice.
2. Alice envía el mensaje cifrado con la clave pública de Bob.
3. Bob descifra el mensaje con su clave privada y se lo guarda a la espera de que llegue la firma que le verifique que es de Alice.
4. Alice envía su clave pública a Bob.
5. Alice crea su firma cifrando el mensaje con su clave privada que seguidamente cifra con la clave publica de Bob y se lo envía.
6. Bob descifra la firma con su clave privada y seguidamente la vuelve a descifrar con la clave pública de Alice.
7. Si el mensaje que obtiene Bob en el paso anterior coincide con el que le llegó en el paso 3, entoncés Bob puede estar totalmente seguro que ese documento es de Alice, que no ha sido modificado y además no lo ha podido ver nadie.

No quiero entrar en explicaciones de fórmulas que requieren tener alguna idea de matemáticas discretas, pero para que entendáis un poco mejor la esencia el algoritmo, al menos, quiero explicaros que la seguridad de éste se basa en la dificultad de factorizar números que son producto de dos números primos muy grandes. Por ejemplo, si queremos factorizar en números primos el número 6, podemos calcular de cabeza fácilmente que 6=2*3, pero si queremos factorizar el número 66698810729, tendremos que intentar dividirlo primero por 2, luego por 3, por 5, 7, 11, 13, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,... así hasta llegar al 192667, con lo que obtenemos que la factorización de 66698810729 es 346187*192667. Es decir que para hacer ese cálculo, primero necesitamos averiguar todos los número primos anteriores al 192667. Un ser humano puede tardar varias horas en hacer esto y un ordenador unos segundos, pero los números que se usan para el algoritmo RSA son mucho mayores, de hasta 1024 bits, lo que supone un número de unas 300 cifras en decimal y miles de años de cómputo para el ordenador. Este es el truco de los algoritmos de clave pública, es decir, crear un problema relativamente fácil de plantear pero muy costoso de resolver.

No se puede hablar del RSA sin mencionar también a Whitfield Diffie y Martin Hellman que dos años antes de la invención del RSA, idearon el primer algoritmo de criptografía de clave pública llamado intercambio de clave Diffie-Hellman, que se vale de la criptografía de clave privada para conseguir la pública. La criptografía de clave privada se basa en el secreto de la clave, ya que la misma clave se usa para cifrar y descifrar (cuando no es la misma, se puede calcular fácilmente a partir de la de cifrado). Lo que hicieron estos señores fue inventar una forma de compartir claves de algoritmos de criptografía de clave privada de forma segura. Aunque en la práctica no se usa tal cual, ha sido la base para muchos de los protocolos que se usan en la actualidad. La idea que tuvieron fue la siguiente:

1. Alice cifra con su clave el mensaje y lo envía a Bob.
2. Bob cifra el mensaje recibido con su clave y lo envía a Alice.
3. Alice descifra el mensaje recibido con su clave y se lo envía a Bob.
4. Bob descifra el mensaje recibido con su clave y obtiene el mensaje original.

Para terminar un video reciente de Rivest, Shamir y Adleman haciendo una breve explicación de su algoritmo:

Ver en Youtube