Así funciona el algoritmo RSA

Por Arturo Quirantes, el 22 enero, 2018. Categoría(s): Criptografia ✎ 11
RSA
RSA, el algoritmo de clave pública

Hace unos días la Fundación BBVA otorgó su premio Fronteras del Conocimiento a cuatro de los principales impulsores de la criptografía de clave pública, entre ellos dos de los creadores del algoritmo RSA. En este post voy a explicaros en qué consiste ese algoritmo y por qué es tan importante. Seré breve y os remitiré a mi libro Cuando la criptografía falla para ampliar información.

Durante centenares de años la criptografía ha tenido un talón de Aquiles. La idea es tomar datos, procesarlos mediante un algoritmo y enviarlos al destinatario. En teoría, si el algoritmo es robusto los datos estarán seguros. Pero hay un problema, y es el de las contraseñas. Los algoritmos o sistemas de cifrado necesitan una clave, contraseña o similar. Y el problema siempre ha sido: ¿cómo enviar la clave a los interlocutores? Se puede buscar un sistema físicamente seguro (digamos un envío en maletín cerrado dentro de un furgón blindado con guardias armados), pero en ese caso la seguridad no se basará en sistemas matemáticos sino físicos; además, si tienes un sistema seguro para transportar la clave ¿por qué no usarlo para enviar el mensaje?

En los años setenta lo imposible comenzó a hacerse realidad. Los investigadores norteamericanos Whitfield Diffie, Martin Hellman y Ralph Merkle descubrieron el concepto básico a finales de los años 70, algo conocido como criptografía de clave pública (PKC por sus siglas en inglés).

Hasta entonces, la criptografía era de clave simétrica, es decir, la misma clave que se usa para cifrar sirve también para descifrar. La PKC se basa en dos claves, una pública y una privada. La pública, usada para cifrar, era conocida por todos; pero solamente el poseedor de la clave privada podría descifrar el mensaje. Sería análogo a un buzón de correos, donde d todo el mundo puede meter información dentro, pero solamente el dueño puede abrirlo con su llave. De esa forma desaparece la necesidad de enviar la clave de forma segura, porque no tienes más que publicarla en Internet y cualquiera podrá usarla.

En teoría se puede obtener la clave privada a partir de la clave pública, pero en la práctica el proceso es muy difícil y exigente en términos computacionales; es decir, la PKC basa su fortaleza en problemas difíciles. Durante los años setenta y ochenta se pusieron a prueba muchos problemas matemáticos difíciles.  Uno de ellos finalmente dio origen a un sistema de clave pública conocido con el nombre de RSA, por las iniciales de sus creadores: Rivest, Shamir, Adleman. Fue uno de los más importantes hitos que permitieron crear una Internet segura, con páginas web protegidas mediante criptografía.

El problema matemático en que se basa RSA es la factorización de números primos. Si les doy el número 15, no tardarán mucho en descubrir que es compuesto; pero si el número es muy grande, obtener su factorización es una tarea ardua y larga. Vamos, pues, a escoger un número n que sea producto de dos números primos p y q.

Pero espere, señor explicador, ¿cómo sabemos que p y q son primos? El algoritmo que nos explican es que debemos intentar dividir p por todos los números enteros inferiores a él, a ver si alguno da un resto cero. Podemos refinarlo usando solamente los números primos inferiores a la raíz cuadarada de p, pero aún así la tarea es computacionalmente ardua para números grandes.

Lo que se hace es tomar otro algoritmo de primalidad (es decir, que determina si un número es primo o no) que sea más sencillo de usar. Uno de ellos, denominado Test de Primalidad de Fermat (TPF) está basado en el Pequeño Teorema de Fermat, que dice: “Si p es un número primo, y a es un número cualquiera entre 1 y p, entonces se cumple que la división a^(p-1) / p tiene resto igual a uno

Hay algunos problemas con este test, pero pueden resolverse. No voy a mostrar la resolución aquí por no extenderme demasiado, pero la tienen en mi libro, así que vamos con el algoritmo RSA. La idea es usar la llamada aritmética modular. Habitualmente, cuando hacemos la división c=a/b lo que suele interesarnos es el cociente. Si a, b son dos números reales, el cociente es c, y el resto es cero. Si, como en el caso que nos ocupa, se trata de números enteros, entonces el cociente no tiene por qué ser exacto. Bien, pues en la aritmética modular no nos interesa el cociente, sino el resto.

Para esta nueva operación, utilizaremos la notación “mod.” Cuando escribimos b mod n (“b módulo n”) nos estamos refiriendo a “el resto que obtenemos al dividir b por n” Cuando queramos indicar que al dividir a entre n obtenemos resto b, lo escribiremos así:

a = b mod n

También podemos entenderlo diciendo que (a-b) es múltiplo entero de n, o que hay un entero k para el que se cumple que a=k*n+b.

Para construir nuestro sistema de PKC partiremos de dos números primos grandes (p, q) y su producto n=p*q. Calculemos también el número F=(p-1)(q-1). El número n es público, pero p y q no lo son. A continuación crearemos la clave pública y la clave privada.

La clave pública e será un número tal que F y e sean primos relativos. Con “primos relativos” queremos decir que no tengan divisores comunes, es decir, que su máximo común divisor sea uno. No tienen por qué ser primos ellos mismos. Por ejemplo, los números 15 y 14, a pesar de ser números compuestos, son primos relativos.

La clave privada d es un número que cumpla que e*d mod F = 1; se dice en este caso que d es el inverso (multiplicativo) de e módulo F. No siempre existe el inverso multiplicativo, y la condición necesaria para que exista inverso es que los números e y F sean primos relativos. Por eso le hemos exigido esa condición específica al número e.

Ya estamos preparados para cifrar el mensaje M, que vamos a representar mediante un número entero. Para obtener el mensaje cifrado C, realizaremos la siguiente operación:

C = (M^e) mod n

Fíjense que tenemos un número M enorme, elevado a una potencia e, pero no importa porque, como ya hemos visto, la aritmética modular me permite operar con facilidad. El proceso opuesto, el descifrado, lo realizamos calculando el siguiente número:

M=(C^d) mod n

¿Lo ve claro? Seguro que no. El proceso de demostración es algo elaborado (de nuevo, aquí está mi libro para una explicación completa), pero el resultado final es ese. Lo importante es que el proceso de cifrado y descifrado es sencillo usado aritmética modular, y en ambas ocasiones seguimos los mismos pasos:

– Para cifrar, tomamos e y hacemos C = (M^e) mod n

– Para descifrar, tomamos d y hacemos M = (C^d) mod n

En todo ese proceso, recordemos, e es la clave pública, en tanto que d es la clave privada. El producto n=p*q también es público, de modo que para reventar el problema no hay más que factorizar n, obtener el número F y a partir de ahí recuperar d; en la práctica, como n es muy grande, la factorización no puede realizarse en un tiempo razonable ni con equipos informáticos de tamaño razonables.

Posteriormente se han desarrollado otros sistemas de PKI, pero RSA fue el pionero y resultó crucial para levantar una Internet segura, y eso ha sido reconocido recientemente con el premio Fronteras del Conocimiento BBVA. Pero hay algo que no entiendo: ¿Por qué premiaron a Rivest y Shamir pero no a Adleman? No lo sé, pero se lo merece igual que los demás. En cualquier caso enhorabuena a todos, y gracias por haber hecho de Internet un lugar más seguro.

NOTA HISTÓRICA. En rigor hay que reconocer que los primeros descubridores de la criptografía de clave pública no fueron Diffie, Hellman y Merkle. Los británicos James Ellis, Clifford Cocks y Malcolm Williamson habían descubierto los principios de la PKC pocos años antes. Para su desgracia, trabajaban para la agencia criptoanalítica británica GCHQ, y su trabajo se mantuvo en secreto durante muchos años. Solamente a finales de los años 90 se les permitió hablar de su papel en la PKC. Los norteamericanos se llevaron todo el mérito.



11 Comentarios

  1. Cuanto me pica la curiosidad el tema y cuantas preguntas me surgen, pero no entiendo absolutamente nada de matematicas.
    Una de esas dudas es, en todo ese sistema de encriptar y desencriptar, ¿Como se ha resuelto el tema de enviar la clave privada que no sea de forma física?

      1. Más bien la criptografía de clave pública no se utiliza para cifrar información, sino para el intercambio de claves y para obtener confidencialidad no se cifra con la clave privada se cifra con la clave pública. Cuando se cifra con al clave privada se logra autenticar al emisor de un mensaje, es decir se obtiene lo que se conoce como firma digital. Para el cifrado de información se utiliza criptografía de clave privada.

    1. Pues la clave privada se envía usando estos algoritmos de PKC, a través de estos algoritmos los sistemas se ponen de acuerdo con la clave privada a utilizar, y después s comunican con un algoritmo de encriptación simétrico. Podría comunicarse enteramente usando PKC, pero son más costosos computacionalmente que un algoritmo simétrico.

    2. Supongo que te haces un lio porque piensas que eres tu quien envia la clave que se va a usar en los mensajes.

      Lo que haces es dar tu clave publica para que la persona con la que quieres hablar te envie la clave de verdad cifrada con la clave publica. Como tu eres el unico que tiene la clave privada nadie mas puede descifrar este mensaje con la clave de verdad y asi no tienes que enviarlo de estrangis lo puede ver todo el mundo que da igual es indescifrable.

      Luego ya usais el cifrado de toda la vida usando esa clave de verdad.

  2. Seguramente estoy en un error, pero hay algo que no entiendo …
    si para ecriptar se utiliza la clave publica (e,n), así : C = (M^e) mod n
    yo podria desencriptar solo usando esa clave publica asi: M = (C/(mod n))^1/e ?
    por que lo anterior no se puede y hace necesario utilizar la clave privada, la verdad soy nuevo en estos temas y me gustaria saber mas. gracias, ojala alguien pueda responderme.

    1. Lamentablemente no es tan fácil.
      mod n no es un número que está multiplicando.
      Es como si tuvieras sen(x)=0.5 y despejaras poniendo x=0.5 / sen
      De paso, elevar a la 1/e sería elevar a d. Pero el problema es que, al no saber F, no podés calcular d.

Deja un comentario

Por Arturo Quirantes, publicado el 22 enero, 2018
Categoría(s): Criptografia
Etiqueta(s): , ,