Criptografía y números RSA

Y las matemáticas para que sirven? Buena pregunta que uno se hace cuando estudia…La respuesta es sencilla, las matemáticas  sirven para todo!! Y sino te lo crees, te invito a que leas el siguiente post sobre criptografía.

A grandes rasgos podemos definir la criptografía como la disciplina que se ocupa de las técnicas utilizadas para alterar la representación lingüística de un mensaje mediante técnicas de cifrado, de manera que la información no esté disponible para todo el mundo, es decir, que sea una información confidencial.

Desde que vi la película “una mente maravillosa” con Russell Crow como actor principal, empecé a interesarme por este tipo de problemas. Posteriormente leí algunos libros y encontré el tema de los números RSA (nombre que toma de sus desarrolladores: Rivest, Shamir y Adleman). Sí sí, estos tres señores de la foto:

Este algoritmo creado en 1977 es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente en la actualidad.

Imaginemos que el emisor (E) desea enviar una mensaje (M) cifrado al receptor (R). Para ello, E y R deberían disponer de una clave solo conocida por ellos, para lo cual deberían reunirse y establecerla, o lo que es peor, si fueran varios R, se deberían realizar muchos más encuentros.

Debido a que la clave debe ser confidencial en todo momento, y que este proceso no hace otra cosa que incrementar las posibilidades de que esta sea descubierta, no parece que este sea el mejor método para transmitir un mensaje cifrado.

Pues bien, qué os parece un método mediante el que E emita un mensaje a una clave pública de R y que este dispusiera de una clave privada que solo él conoce para descifrarlo? Sería la solución perfecta, no?

Veamos cómo se podría hacer lo anterior a través de un ejemplo. Este no contiene nada relativo a los fundamentos teóricos sobre los que este algoritmo se sustenta, para eso, ya existen una gran cantidad de completísimas referencias que podéis consultar en internet. Particularmente, me pareció interesante la siguiente:

RSA encryption (criptografía)

Y si queréis ver un video, como siempre nuestros amigos de numberphile están dispuestos a que aprendamos de todo de una forma divertida:

Ejemplo:

El emisor E quiere transmitir un mensaje M a un receptor R. Este receptor tiene dos claves públicas, como podrían ser su teléfono y dirección, (n,e). Esta es por tanto la información que todo el mundo podría consultar.

La clave n es el resultado de multiplicar dos números primos p=11 y q=23 que solo él conoce y que previamente (como se verá más adelante, es importante que sean números largos) ha elegido resultando que n=p.q=253.

Por otra parte, e puede ser cualquier valor que R elija, en nuestro ejemplo tomaremos e=3, esto es, clave pública=(253,3).

Además, tiene una clave secreta que este debe obtener mediante la siguiente expresión que requiere trabajar con congruencias:

De aquí obtenemos que d=147. Para quien haya olvidado cómo trabajar con congruencias, simplemente recordar que es como trabajar con una nueva base. Según palabras de wikipedia:

Congruencia es un término usado en la teoría de números, para designar que dos números enteros y tienen el mismo resto al dividirlos por un número natural , llamado el módulo; esto se expresa utilizando la notación.

Por ejemplo:

7=  -1 mod 8 porque 8| (7-(-1))

27=  2 mod 5 porque 5| (27-2)

Por lo que volviendo a nuestro ejercicio tenemos que 147.3=441 y 441-220.2=1

Una vez determinados todos los parámetros de R, E emite el mensaje (M) “4”, mensaje que debe ser encriptado para que solamente R tenga acceso a este. Esto puede hacerse utilizando la siguiente expresión:

Luego “64” es el mensaje que E transmite en lugar del  “4” inicial. Ahora solo hace falta que R, descifre el mensaje, lo cual puede hacer de una manera relativamente sencilla partiendo de la siguiente expresión:

Este cálculo que en principio parece inabordable puede realizarse a partir de los cuadrados del número en cuestión. Una vez calculados y teniendo en cuenta que todo número entero positivo puede escribirse como suma de potencias de dos podemos resolver la ecuación anterior:

Luego M=4, es decir, el mensaje inicial que E quería transmitir a R.

La clave de todo reside en lo siguiente: si alguien te pidiera que multiplicaras 111,111,111 x 111,111,111, seguro que no tardarías demasiado en pulsar tres teclas de tu calculadora para obtener que dicho producto resulta ser el número capicúa 12345678987654321 (una multiplicación curiosa, verdad?).

Sin embargo, si te piden que factorices 12345678987654321 en dos números primos la cosa se complica un poco…o más bien bastante. Pues bien, los números RSA pueden ser de 50, 100, 200 o 300 cifras…echad un vistazo a la factorización del RSA-100 (tomado de wikipedia):

El emisor puede descifrar el mensaje fácilmente ya que conoce p y q, pero para que alguien que no fuera R pudiera descifrarlo, debería ser capaz de factorizarlo, lo que no es nada fácil debido a la capacidad computacional que se necesita (aunque tal vez esto cambia cuando tengamos ordenadores cuánticos).

Por cierto, si sois capaces de factorizar el RSA-2048 (un número con 617 cifras decimales) seréis recompensado con 200.000 $. A pesar de ser un premio tan suculento, creo que no es buena idea dedicar mucho tiempo en ello…

¿Quieres ver un video muy entretenido sobre criptografía y números RSA? Sin duda alguna os encantará el siguiente vídeo del divertido divulgador Eduardo Sáenz de Cabezón:

Algún documento tal vez para investigar algo más:

The RSA algorithm

Factorization of a 768-bit RSA modulus

Espero que con esto os gusten un poco más las matemáticas!!

Related posts:

Problemas de matemáticas (II). Teoría de números Matemáticas, física y ecuaciones diferenciales 5 Libros de matemáticas que no te puedes perder Libros de matemáticas e ingeniería