Lo que se esconde en Internet: sistema RSA de criptografía de clave pública

Fuente de la imagen: http://taringa.net

Nosotros, seres humanos, siempre hemos tenido necesidad de ocultar muchas cosas y de enviar mensajes secretos, de ahí que hace más de 2500 años ya los espartanos idearan un método para esconder información a los ojos no “dignos” para ello, conocido como el método de la scitala (Da-beat ha escrito unos cuantos e interesantes artículos sobre distintos métodos criptográficos que recomiendo que leas si aún no lo has hecho). Sin embargo, todos estos métodos, desde la scitala a la máquina Enigma, tenían un problema: la necesidad de que el emisor y el receptor se pusieran de acuerdo con respecto a la clave, a la forma de codificación, a usar; la misma para ambos. Esto puede ser muy engorroso si esas personas se encuentran muy lejos una de la otra: o bien hay que encontrarse para elegir la clave, o bien un intermediario lo tiene que hacer, con el peligro de que dicha clave se intercepte por el camino. Teniendo en cuenta que, además, es recomendable cambiar el código de vez en cuando, por si existen mentes astutas entre el enemigo, ya te puedes imaginar…

 

Desde luego, actualmente, con un método criptográfico de este tipo, sería impensable realizar compras por Internet o escribir correos electrónicos sin un mínimo de intimidad. ¿Se imagina el lector, por ejemplo, recibiendo cartas con el código a usar para enviar su número de cuenta bancaria a una determinada empresa? Además, la clave para cada comprador o emisor tendría que ser diferente y habría un gran riesgo de intercepción. Ya ves la que se podría armar.

 

Entonces, ¿qué método potente se esconde detrás de Internet y de tal barullo de mensajes encriptados que circulan por sus venas? Igual te suena: la Criptografía de clave pública (un nombre muy acertado), cuyo sistema más conocido y uno de los más seguros es el RSA (sus siglas se deben a la inicial del apellido de las tres personas que lo descubrieron: Rivest, Shamir y Adleman), que conoció la luz en 1977. Pero, antes de hablar sobre él, desplacémonos unos años atrás.

 

En 1903, un matemático que respondía al nombre de Frank Nelson Cole, dio la conferencia más silenciosa y corta de la Historia: cogió una tiza y la pasó cariñosamente por el encerado, dejándole las siguientes marcas:

 

 

Después de esto tomó asiento y el público se levantó para aplaudirlo efusivamente, lo que puede dar a entender que los matemáticos están más locos de lo que parecía: se ponen así por una simple multiplicación. El caso es que los números multiplicados son primos y Cole había gastado 3 años de las tardes de los domingos para descomponer el  en esos factores… En la época en la que Cole hizo esta proeza no se podía intuir que la resolución de problemas de este tipo pudiera traer del brazo grandes implicaciones, pero, por los giros que da la Historia, la descomposición de números grandes (de unos 200 dígitos) en sus dos factores primos es la base del RSA. ¡Y Hardy que se enorgullecía de que su querida Teoría de Números no tenía aplicaciones en la vida cotidiana! ¡Si levantara la cabeza!

 

Volvamos otra vez a 1977…Tiene gracia (o igual no) que a Rivest se le ocurriera su brillante idea, en la que los tres habían estado trabajando, en medio de una noche de borrachera. Lo que intentaban hacer era encontrar un método que permitiera cerrar el “baúl de los secretos” con una llave y abrirla con otra diferente, y lo encontraron, como ya se ha dicho, de mano de los átomos de la matemática: los números primos. También tiene cierta gracia que el principal medio de difusión de la idea fuera un artículo de Martin Gardner en su sección del Scientific American.

 

Ingredientes

 

Después de tanto preámbulo me gustaría mostrarte un poco en qué consiste dicho método. Para ello necesitaremos los siguientes ingredientes y proposiciones:

 

[1] Dados dos números a y b, existen dos números enteros x e y tales que el máximo común divisor, D, de a y b se puede expresar como:

                                                                                                                                  

[2] Si p y q son dos números primos distintos y a es un entero positivo que no es divisible por ninguno de los dos, entonces , es decir, el resto de dividir  por pq es 1.

 

Preparación

 

Vale, veamos cómo mezclar todo esto para obtener algo consistente. Para simplificar llamemos A a la persona que va a recibir el mensaje encriptado y B al que lo encripta. A tiene dos números, con los que B va a hacer la encriptación, que son conocidos por todos (cualquiera puede enviarle un mensaje secreto a A). Llamemos a esos números m y n. m y n tienen que cumplir una serie de características:

 

• m es un número formado por sólo dos factores primos muy grandes, p y q, es decir, m = pq. La tarea de conocer en qué factores primos se descompone un número muy grande, siempre que los factores primos que lo forman también sean muy grandes, es una tarea que lleva miles, e incluso millones, de años a los ordenadores más rápidos. Sin embargo, es relativamente sencillo encontrar dos números primos grandes y multiplicarlos. De ahí que A tenga información privilegiada que nadie más conoce: sólo él sabe qué dos factores primos componen el número m (podría ocurrir que dos personas tuvieran el mismo número m al haber multiplicado los dos mismos números primos. En ese caso cada una de estas personas conocería los secretos de la otra. La probabilidad de que esto ocurra es muy baja, por lo que no debería ser motivo de preocupación).

 

• n es un número primo (éste no hace falta que sea muy grande) que no divide al número (p-1)(q-1)

Fuente de la imagen: http://malavida.com

 

¿Cómo envía B el mensaje a A? Primero tiene que tranformar el mensaje en números, por ejemplo asignándole un número a cada letra del alfabeto y a cada signo de puntuación. Claro, esta tabla de equivalencias es también conocida por todos. Ahora que B ya ha transformado el mensaje en un número, al que llamaremos M, sólo tiene que realizar las siguientes operaciones: Elevar M a n y dividir el resultado por m, lo que nos dará un resto, M*, que es el mensaje encriptado que le enviamos a A. De otra manera, en la igualdad con  y C número natural, r equivale a M*

 

Aquí es importante hacer notar las tierras movedizas que pisa la persona que quiera descifrar el mensaje. Para ello tendría que encontrar un número que al elevarlo a n y al dividirlo por m nos diera de resto M*, lo que es muy difícil, dada la magnitud de los números de los que hablamos (o bien hallar los números p y q, pero ya hemos visto también la dificultad que esto entraña).

 

Por lo tanto, ¿Cómo hace A para conseguir ser el único que puede desencriptar el mensaje que le ha enviado B? Para ello necesita otro número, el desencriptador, x, que cumple que:

 

 

¿Y por qué tendría que existir ese número? Teniendo en cuenta que m no divide a (p-1)(q-1), ya que lo escogimos expresamente para que fuera así, y aplicando [1] a este caso en concreto, en el que a es m, b es (p-1)(q-1) y el máximo común divisor es 1, es fácil darse cuenta del porqué. De todas formas una cosa es que exista y otra que sea fácil hallarlo, pero gracias al algoritmo de Euclides no tenemos ninguna dificultad para dar con él. Hago notar también que A es el único que puede hallar ese número, ya que es el único que conoce p y q, y por lo tanto (p-1) y (q-1)

 

Bien, pues ahora, con [1] y [2], y con unos bastante sencillos pasos que no vamos a explicar en este post por no hacerlo demasiado tedioso, llegamos a la conclusión de que M es igual al resto de dividir M* elevado a x por m, es decir,

 , donde C y C’ son números naturales.

En realidad la implicación es doble, ya que también se cumple que:

 , donde C y C’ son números naturales

Ésta es una propiedad importante que deshecha una desventaja que podría tener este sistema con respecto a los antiguos si no fuera así: permite firmar el mensaje enviado, es decir, permite tener la certeza de que el mensaje que recibimos es de la persona esperada y no de un bromista que decidió hacerse pasar por otro. ¿Por qué y cómo? La doble implicación nos permite afirmar que el método de encriptado es inverso al de desencriptado, de tal manera que si encriptamos el mensaje que queremos enviar y luego lo desencriptamos o lo hacemos al revés, “desencriptamos” el mensaje y luego lo “encriptamos”, el resultado siempre va a ser el mensaje de partida. Veamos entonces cómo firmar nuestro mensaje.

 

1. B decide enviar su mensaje a A firmado. Para ello primero trata el mensaje, M, con su propio algoritmo de desciframiento (sólo conocido por él), obteniendo M1
2. B encifra M1 a través del algoritmo de enciframiento (conocido por todos) para A y le manda el mensaje, M1*, a A
3.  A, a través de su algoritmo de desciframiento (sólo conocido por él), obtiene M1.
4.  Ahora A usa el algoritmo de enciframiento de B (conocido por todos) en M1 y obtiene M (obsérvese que M1 lo habíamos obtenido a partir de usar el algoritmo de desciframiento de B sobre M). A puede estar seguro de que el mensaje es de B, ya que él es el único que conoce el algoritmo de desciframiento de B y de otra manera habría salido un galimatías.

 

Los pasos 2 y 3 son los necesarios si no queremos enviar el mensaje firmado. El primero y el cuarto se añaden para el caso de que sí se quiera hacer.

 

Me habría gustado mostrar un script mediante el que practicar este tipo de algoritmo, pero da-beat, que hace ya tiempo que había quedado en hacerlo, no se ha decidido aún. A ver si algún día escribe su post sobre el RSA, que seguramente sea mucho más dinámico que éste (siento haber escrito sobre el tema, pero es que no me resistía, y como tú durabas mucho, no tuve paciencia…) 

Ahora cabe preguntarse: ¿hasta qué punto preferimos que no se descubra

Fuente de la imagen: http://jasoft.org

 una forma fácil de descomponer un número grande en sus factores primos? Si no se descubre, el sistema RSA está a salvo, pero si se descubre habremos colocado uno de los cimientos del edificio matemático. ¿Qué es preferible? De todas maneras el sistema RSA no es el único método criptográfico de clave pública válido. Uno que tiene también mucho auge se basa en las denominadas curvas elípticas, usado principalmente en móviles, agendas electrónicas y demás aparatos electrónicos con poca memoria y microprocesadores lentos. El método de las curvas elípticas requiere mucho menos tiempo de encriptamiento que el sistema RSA. Quién sabe lo que pasará dentro de unos años. Quién sabe cuántos son los años de vida que le quedan al RSA.

 

Por cierto, es mi intención, si no me lío mucho con latex, demostrar las proposiciones del principio y observar más profundamente las entrañas matemáticas del sistema RSA… Pero eso ya para otro día.

---

Bibliografía:

DE GUZMÁN, M. (2000): Aventuras matemáticas. Pirámide

DU SAUTOY, M. (2003): La música de los números primos. El acantilado