Cuando una persona busca mandar un mensaje a otra persona pero no quiere que alguien más conozca el mensaje, pueden optar por encriptar el mensaje. Una de las maneras más comunes de hacer esto hoy en día es mediante el sistema RSA.
¿Qué es el sistema RSA?
Es un sistema criptográfico que emplea claves para encriptar y desencriptar mensajes y basa su éxito en la complicada tarea para una computadora clásica de encontrar la factorización en números primos de un número entero muy grande.
El algoritmo fue presentado por Ron Rivest, Adi Shamir y Leonard Adleman del Instituto Tecnológico de Massachusetts (MIT) en 1977. El nombre RSA se debe a las iniciales de sus apellidos.
Como mencionamos anteriormente el sistema emplea claves. Estas consisten en dos claves de cifrado: una clave pública y una clave privada. El emisor del mensaje debe tomar la clave publica del receptor y con ella cifrar su mensaje, luego envía el mensaje cifrado al receptor y este lo descifra usando su clave privada. A continuación analizaremos a detalle el algoritmo RSA para cifrar mensajes.
El algoritmo RSA
Supongamos que tenemos dos personas, que llamaremos emisor y receptor. Digamos que emisor quiere enviar un mensaje a receptor. Para esto poseen un caja y un candado. Receptor tiene dos llaves, una de ellas sólo sirve para cerrar el candado, que llamamos la llave pública y la otra sólo funciona para abrir el candado, denominada llave privada. Cuando emisor quiere enviar el mensaje, mete el mensaje en la caja, luego receptor le da su llave pública y con ella cierra el candado. Ahora, sin la llave privada, emisor ni nadie más puede abrir la caja. Receptor entonces recibe la caja cerrada y usa su llave privada para abrir el candado y ver el mensaje que hay dentro. Lo que ac acabamos de decir es la idea detrás del funcionamiento del sistema RSA.
De manera más técnica, lo que esta pasando es que el emisor tiene un mensaje en forma de un número entero
. Las llaves son realmente un par ordenado de número enteros y el cifrado se hace transformando el número
en un número
mediante aritmética modular. Veamos todo esto en detalle:
Lo primero que debe hacer el receptor es generar sus claves pública y privada. Para esto se eligen dos número primos diferentes y
. Luego se calcula el número
(1)
Este número será la base para hacer la aritmética modular a continuación. Entonces consideramos la función de euler evaluada en el número
, que, aprovechando las propiedades de la función, se puede escribir como
Ahora se debe escoger un entero tal que
y que sea coprimo con
(esto quiere decir que el máximo común divisor de
y
sea 1, en símbolos,
). A este entero
lo llamaremos exponente de la clave pública.
Luego, se encuentra un número tal que satisface la relación
Otra manera de decir esto es que el entero es un múltiplo de
. Al entero
lo llamaremos el exponente de la clave privada.
De esta manera tenemos que la clave pública será el par y la clave privada será el par
.
Ahora, ya que tenemos las claves pública y privada, el emisor usa la clave pública para cifrar el mensaje de la siguiente manera: Transforma el mensaje en un número entero
que sea menor que
, entonces el mensaje cifrado
estará dado por
Posteriormente, el emisor envía el mensaje cifrado al receptor, quien procede a descifrarlo usando la clave privada de la siguiente manera:
La seguridad de este sistema recae en la dificultad de obtener la clave privada a partir de la clave pública, bueno lo que se necesita es pues
aparece en la clave pública, sin embargo para obtener
necesitamos conocer
y para ello necesitamos ser capaces de descomponer
en sus factores primos
y
. Esto último representa una tarea computacionalmente costosa cuando se trata de números muy grandes. No existen algoritmos capaces de resolver esto en tiempo polinómico.
Bueno, esto de que no hay algoritmo capaz de resolver el problema de factorizar un número grande en sus factores primos es mitad verdad, pues si bien es cierto que no existe un algoritmo capaz de resolverlo en tiempo polinómico que pueda ser ejecutado en un computador clásico, si existe un algoritmo capaz de factorizar en primos pero en una computadora cuántica. Este algoritmo se conoce como el algoritmo de Shor.
Referencias
R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120–126. 1978.
Moret, V. Principios fundamentales de computación cuántica. (2013) Universidad de la Coruña, Departamento de Computación. Facultad de Informática