En criptografía, RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1977, que utiliza factorización de números enteros. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente.
La seguridad de este algoritmo radica en el problema de la factorización de números enteros. Los mensajes enviados se representan mediante números, y el funcionamiento se basa en el producto, conocido, de dos números primos grandes elegidos al azar y mantenidos en secreto. Actualmente estos primos son del orden de , y se prevé que su tamaño siempre crezca con el aumento de la capacidad de cálculo de los ordenadores.
Como en todo sistema de clave pública, cada usuario posee dos claves de cifrado: una pública y otra privada. Cuando se quiere enviar un mensaje confidencial, el emisor busca la clave pública del receptor, cifra su mensaje con esa clave, y una vez que el mensaje cifrado llega al receptor, este se ocupa de descifrarlo usando su clave privada.
En el caso de querer firmar (propiedades de autenticidad, integridad y no repudio), el emisor obtiene un hash del mensaje a firmar y lo procesa con su clave privada obteniendo así la firma; se envía el mensaje y la firma; el receptor recalcula el hash y descifra el hash original con la clave pública del emisor, validando así (o no) la firma del mensaje.
Se cree que RSA será seguro mientras no se conozcan formas rápidas de descomponer un número grande en producto de primos. Aunque se cree que la computación cuántica podría proveer de una solución al problema de factorización, existen investigadores que dudan que dichos avances vayan a volver obsoletos estos algoritmos.
Historia thumb|175px|Adi Shamir, uno de los tres inventores de RSA (los otros dos son Ron Rivest y Leonard Adleman). El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Leonard Adleman, del Instituto Tecnológico de Massachusetts (MIT); las letras RSA son las iniciales de sus apellidos. Clifford Cocks, un matemático británico que trabajaba para la agencia de inteligencia británica GCHQ, había descrito un sistema equivalente en un documento interno en 1973. Debido al elevado coste de las computadoras necesarias para implementarlo en la época su idea no trascendió. Su descubrimiento, sin embargo, no fue revelado hasta 1997 ya que era confidencial, por lo que Rivest, Shamir y Adleman desarrollaron RSA de forma independiente.
El algoritmo fue patentado por el MIT en 1983 en Estados Unidos con el número 4.405.829. Esta patente expiró el 21 de septiembre de 2000. Como el algoritmo fue publicado antes de patentar la aplicación, esto impidió que se pudiera patentar en otros lugares del mundo. Dado que Cocks trabajó en un organismo gubernamental, una patente en Estados Unidos tampoco hubiera sido posible.
Es un algoritmo puramente asimétrico, junto con DSA. Este algoritmo como su nombre lo indica, sirve para firmar (autenticar) y para cifrar información. Una desventaja del algoritmo DSA es que requiere mucho más tiempo de cómputo que RSA.
Cifrado RSA Este consta de tres pasos: generación de claves, cifrado y descifrado
Idea del cifrado Supongamos que Bob quiere enviar a Alicia un mensaje secreto que solo ella pueda leer.
Alicia envía a Bob una caja con un candado abierto, del que solo Alicia tiene la llave. Bob recibe la caja, escribe el mensaje, lo pone en la caja y la cierra con su candado (ahora Bob no puede leer el mensaje). Bob envía la caja a Alicia y ella la abre con su llave. En este ejemplo, la caja con el candado (abierto) es la «clave pública» de Alicia, y la llave del candado es su «clave privada».
Técnicamente, Bob envía a Alicia un «mensaje llano» en forma de un número menor que otro número , mediante un protocolo reversible conocido como padding scheme («patrón de relleno»). A continuación genera el «mensaje cifrado» mediante la siguiente operación:
,
donde es la clave pública de Alicia.
Ahora Alicia descifra el mensaje en clave mediante la operación inversa dada por
,
donde es la clave privada que solo Alicia conoce.
Generación de claves Se eligen dos números primos distintos y . Por motivos de seguridad, estos números deben escogerse de forma aleatoria y deben tener una longitud en bits parecida. Se pueden hallar primos fácilmente mediante test de primalidad. Se calcula . se usa como el módulo para ambas claves, pública y privada. Con es la función φ de Euler calcula aprovechando las dos propiedades de la función de Euler siguientes: si es primo. Si a y b son primos entre sí, entonces . Se escoge un entero positivo menor que , que sea coprimo con . se da a conocer como el exponente de la clave pública. Si se escoge un con una suma encadenada corta, el cifrado será más efectivo. Un exponente muy pequeño (p. ej. ) podría suponer un riesgo para la seguridad. Se determina un (mediante aritmética modular) que satisfaga la congruencia , es decir, que sea el multiplicador modular inverso de Expresado de otra manera, es dividido exactamente por . Esto suele calcularse mediante el algoritmo de Euclides extendido. se guarda como el exponente de la clave privada.
La clave pública es , esto es, el módulo y el exponente de cifrado. La clave privada es , esto es, el módulo y el exponente de descifrado, que debe mantenerse en secreto.
Usando las propiedades de la función de Euler, el Teorema de Euler y el Teorema del resto chino se puede demostrar que Una introducción a la criptografía de clave pública. Segunda Edición. Wolfgag Willems et al. Ediciones Uninorte 2010RSA Proof of Correctness
Notas PKCS#1 v2.0 y PKCS#1 v2.1 se especifican mediante la función de Carmichael en vez de la función de Euler, donde indica el mínimo común múltiplo. Para una mayor eficiencia los siguientes valores se calculan de antemano y se almacenan como parte de la clave privada: y : los primos para la generación de las claves, y , .
Cifrado Alicia comunica su clave pública a Bob y Alicia mantiene su propia clave privada en secreto. Ahora Bob desea enviar un mensaje a Alicia.
Primero, Bob convierte en un número entero menor que . Luego calcula el texto cifrado mediante la operación
.
Esto puede hacerse rápido mediante el método de exponenciación binaria. Ahora Bob transmite a Alicia.
Descifrado
Alicia puede recuperar a partir de usando su exponente de la clave privada mediante el siguiente cálculo:
.
Ahora que tiene en su poder, puede recuperar el mensaje original invirtiendo el padding scheme.
El procedimiento anterior funciona porque
.
Esto es así porque, como hemos elegido y de forma que , se cumple
.
La última congruencia se sigue directamente del teorema de Euler cuando es coprimo con . Puede demostrarse que las ecuaciones se cumplen para todo usando congruencias y el teorema chino del resto.
Esto muestra que se obtiene el mensaje original:
.
Ejemplo
Aquí tenemos un ejemplo de cifrado/descifrado con RSA. Los parámetros usados aquí son pequeños y orientativos con respecto a los que maneja el algoritmo, pero podemos usar también OpenSSL para generar y examinar un par de claves reales.
p = 61 n.º primo privado q = 53 2.º n.º primo privado n = p·q = 3233 producto p×q e = 17 exponente público d = 2753 exponente privado
La clave pública es (e, n). La clave privada es (d, n). La función de cifrado es:
Donde m es el texto sin cifrar. La función de descifrado es:
Donde c es el texto cifrado. Para cifrar el valor del texto sin cifrar 123, nosotros calculamos:
Para descifrar el valor del texto cifrado, nosotros calculamos:
Los cálculos de potencias grandes y del módulo pueden ser eficientemente realizados por el algoritmo de multiplicación cuadrática para exponenciación modular.
Esquemas
RSA debe ser combinado con algún esquema de relleno, ya que si no el valor de M puede llevar a textos cifrados inseguros. El valor m=0, m=1 o m=n-1 siempre produce textos cifrados iguales para 0, 1 o n-1 respectivamente, debido a propiedades de los exponentes. Cuando ciframos con exponentes pequeños (e=3) y valores pequeños de m, el resultado de m podría ser estrictamente menor que el módulo de n. En este caso, el texto cifrado podría ser fácilmente descifrado, tomando la raíz e-ésima del texto cifrado sin tener en cuenta el módulo.
Dado que el cifrado RSA es un algoritmo determinista (no tiene componentes aleatorios) un atacante puede lanzar con éxito un ataque de texto elegido contra el criptosistema, construyendo un diccionario de textos probables con la llave pública, y almacenando el resultado cifrado. Observando los textos cifrados en un canal de comunicación, el atacante puede usar este diccionario para descifrar el contenido del mensaje.
En la práctica, el primero de los dos problemas podría presentarse cuando enviamos pequeños mensajes ASCII donde m es la concatenación de uno o más carácter/es ASCII codificado/s. Un mensaje consiste en un solo carácter ASCII NUL (cuyo valor es 0) se codificaría como m=0, produciendo un texto cifrado de 0 sin importar qué valores de e y N son usados. Probablemente, un solo ASCII SOH (cuyo valor es 1) produciría siempre un texto cifrado de 1. Para sistemas convencionales al usar valores pequeños de e, como 3, un solo carácter ASCII mensaje codificado usando este esquema sería inseguro, ya que el máximo valor de m sería 255, y 255³ es menor que cualquier módulo razonable. De esta manera los textos sin cifrar podrían ser recuperados simplemente tomando la raíz cúbica del texto cifrado. Para evitar estos problemas, la implementación práctica del RSA se ayuda de algunas estructuras, uso del rellenado aleatorio dentro del valor de m antes del cifrado. Esta técnica asegura que m no caerá en el rango de textos sin cifrar inseguros, y que dado un mensaje, una vez que este rellenado, cifrará uno de los números grandes de los posibles textos cifrados. La última característica es la incrementación del diccionario haciendo este intratable a la hora de realizar un ataque.
El esquema de relleno de RSA (en inglés RSA-padding scheme) debe ser cuidadosamente diseñado para prevenir ataques sofisticados los cuales podrían ser facilitados por la predictibilidad de la estructura del mensaje. Ejemplos de esquema de relleno usados con RSA: RSA-OAEP (Optimal Asymetric Encryption Padding) o su versión moficada RSA-OAEP+. Este tipo de relleno es usado por ejemplo en PKCS#1 y en la red de anonimato TOR RSA-SAEP+ (Simplified Asymmetric Encryption Padding) RSA-REACT RSA-PSS (Probabilistic Signature Scheme). Usado por ejemplo en PKCS#1 Algunos de estos esquemas de relleno, por ejemplo RSA-OAEP y RSA-PSS, encuentran su 'justificación' teórica en el polémico modelo de oráculo aleatorio.
Autenticación de mensajes RSA puede también ser usado para autenticar un mensaje. Supongamos que Alicia desea enviar un mensaje autentificado a Bob. Ella produce un valor hash del mensaje, lo eleva a la potencia de d≡ mod n (como ella hace cuando descifra mensajes), y lo adjunta al mensaje como una “firma”. Cuando Bob recibe el mensaje autentificado, utiliza el mismo algoritmo hash en conjunción con la clave pública de Alice. Eleva la firma recibida a la potencia de e≡ mod n (como hace cuando cifra mensajes), y compara el resultado hash obtenido con el valor hash del mensaje. Si ambos coinciden, él sabe que el autor del mensaje estaba en posesión de la clave secreta de Alicia, y que el mensaje no ha sido tratado de forzar (no ha sufrido ataques).
Se debe observar que la seguridad de los padding-schemes como RSA-PSS son esenciales tanto para la seguridad de la firma como para el cifrado de mensajes, y que nunca se debería usar la misma clave para propósitos de cifrado y de autentificación.
Seguridad