RSA (criptosistema)

Compartir Imprimir Citar

Algoritmo para la criptografía de clave pública

RSA (Rivest–Shamir–Adleman) es un criptosistema de clave pública ampliamente utilizado para la transmisión segura de datos. También es uno de los más antiguos. El acrónimo "RSA" proviene de los apellidos de Ron Rivest, Adi Shamir y Leonard Adleman, quienes describieron públicamente el algoritmo en 1977. Un sistema equivalente fue desarrollado en secreto en 1973 en la Sede de Comunicaciones del Gobierno (GCHQ) (la agencia británica de inteligencia de señales) por el matemático inglés Clifford Cocks. Ese sistema fue desclasificado en 1997.

En un criptosistema de clave pública, la clave de cifrado es pública y distinta de la clave de descifrado, que se mantiene en secreto (privada). Un usuario de RSA crea y publica una clave pública basada en dos grandes números primos, junto con un valor auxiliar. Los números primos se mantienen en secreto. Los mensajes pueden ser encriptados por cualquier persona, a través de la clave pública, pero solo pueden ser decodificados por alguien que conozca los números primos.

La seguridad de RSA se basa en la dificultad práctica de factorizar el producto de dos números primos grandes, el "problema de factorización". Romper el cifrado RSA se conoce como el problema RSA. Si es tan difícil como el problema de la factorización es una pregunta abierta. No hay métodos publicados para derrotar al sistema si se usa una clave lo suficientemente grande.

RSA es un algoritmo relativamente lento. Debido a esto, no se usa comúnmente para cifrar directamente los datos del usuario. Más a menudo, RSA se usa para transmitir claves compartidas para la criptografía de clave simétrica, que luego se usan para el cifrado y descifrado masivo.

Historia

Adi Shamir, co-inventor de RSA (los otros son Ron Rivest y Leonard Adleman)

La idea de un criptosistema de clave pública-privada asimétrica se atribuye a Whitfield Diffie y Martin Hellman, quienes publicaron este concepto en 1976. También introdujeron las firmas digitales e intentaron aplicar la teoría de números. Su formulación utilizó una clave secreta compartida creada a partir de la exponenciación de algún número, módulo un número primo. Sin embargo, dejaron abierto el problema de realizar una función unidireccional, posiblemente porque la dificultad de la factorización no estaba bien estudiada en ese momento.

Ron Rivest, Adi Shamir y Leonard Adleman del Instituto Tecnológico de Massachusetts hicieron varios intentos a lo largo de un año para crear una función unidireccional que fuera difícil de invertir. Rivest y Shamir, como informáticos, propusieron muchas funciones potenciales, mientras que Adleman, como matemático, se encargó de encontrar sus debilidades. Probaron muchos enfoques, incluido el "basado en una mochila" y "polinomios de permutación". Durante un tiempo, pensaron que lo que querían lograr era imposible debido a requisitos contradictorios. En abril de 1977, pasaron la Pascua en la casa de un estudiante y bebieron mucho vino Manischewitz antes de regresar a sus casas alrededor de la medianoche. Rivest, incapaz de dormir, se acostó en el sofá con un libro de texto de matemáticas y comenzó a pensar en su función unidireccional. Pasó el resto de la noche formalizando su idea, y al amanecer tenía gran parte del papel listo. El algoritmo ahora se conoce como RSA: las iniciales de sus apellidos en el mismo orden que su artículo.

Clifford Cocks, un matemático inglés que trabajaba para el Cuartel General de Comunicaciones del Gobierno de la agencia de inteligencia británica (GCHQ), describió un sistema equivalente en un documento interno en 1973. Sin embargo, dadas las computadoras relativamente costosas necesarias para implementarlo en ese momento, era se considera principalmente una curiosidad y, hasta donde se sabe públicamente, nunca se implementó. Su descubrimiento, sin embargo, no fue revelado hasta 1997 debido a su clasificación de alto secreto.

Kid-RSA (KRSA) es un cifrado de clave pública inseguro y simplificado publicado en 1997, diseñado con fines educativos. Algunas personas sienten que aprender Kid-RSA da una idea de RSA y otros cifrados de clave pública, de forma análoga al DES simplificado.

Patente

El 20 de septiembre de 1983 se otorgó al MIT una patente que describe el algoritmo RSA: U.S. Patente 4.405.829 "Sistema y método de comunicaciones criptográficas". Del resumen de la patente de DWPI:

El sistema incluye un canal de comunicaciones junto a al menos una terminal con un dispositivo de codificación y al menos una terminal con un dispositivo de decodificación. Un mensaje-a-se-transferido se incide en cripttexto en el terminal de codificación, codificando el mensaje como número M en un conjunto predeterminado. Ese número se eleva a un primer poder predeterminado (asociado con el receptor previsto) y finalmente computado. El resto o residuos, C, es... computado cuando el número exponente se divide por el producto de dos números primos predeterminados (asociados con el receptor previsto).

En agosto de 1977 se publicó una descripción detallada del algoritmo en la columna Mathematical Games de Scientific American. Esto precedió a la fecha de presentación de la patente de diciembre de 1977. En consecuencia, la patente no tenía validez legal fuera de los Estados Unidos. Si el trabajo de Cocks hubiera sido conocido públicamente, una patente en Estados Unidos tampoco hubiera sido legal.

Cuando se emitió la patente, los términos de la patente eran de 17 años. La patente estaba a punto de expirar el 21 de septiembre de 2000, pero RSA Security lanzó el algoritmo al dominio público el 6 de septiembre de 2000.

Operación

El algoritmo RSA consta de cuatro pasos: generación de claves, distribución de claves, cifrado y descifrado.

Un principio básico detrás de RSA es la observación de que es práctico encontrar tres enteros positivos muy grandes $e$ , $d$ , y $n$ , tales que con exponenciación modular para todos los enteros $m$ (con $0 \leq m n$ ):

{displaystyle (m^{e})^{d}equiv m{pmod {n}}}

y que sabiendo $e$ y $n$ , o incluso $m$ , puede ser extremadamente difícil encontrar $d$ . La barra triple (≡) aquí denota congruencia modular (es decir, cuando divides $(m e) d$ por $n$ y $m$ por $n$ , ambos tienen el mismo resto).

Además, para algunas operaciones es conveniente que se pueda cambiar el orden de las dos exponenciaciones y que esta relación también implica

{displaystyle (m^{d})^{e}equiv m{pmod {n}}.}

RSA implica una clave pública y una clave privada. La clave pública puede ser conocida por todos y se utiliza para cifrar mensajes. La intención es que los mensajes cifrados con la clave pública solo se puedan descifrar en un período de tiempo razonable utilizando la clave privada. La clave pública está representada por los números enteros $n$ y $e$ , y la clave privada por el entero $d$ (aunque $n$ también se usa durante el proceso de descifrado, por lo que también podría considerarse parte de la clave privada). $m$ representa el mensaje (previamente preparado con una determinada técnica que se explica a continuación).

Generación de claves

Las claves para el algoritmo RSA se generan de la siguiente manera:

Elige dos grandes números primos p y q.
- Para hacer más difícil el factor, $p$ y $q$ debe ser elegido al azar, ser similar en magnitud, pero difieren en longitud. Los primeros enteros se pueden encontrar eficientemente usando una prueba de primalidad.
- $p$ y $q$ Debería mantenerse en secreto.
Computación n = pq.
- $n$ se utiliza como el módulo para las llaves públicas y privadas. Su longitud, generalmente expresada en pedazos, es la longitud clave.
- $n$ es liberado como parte de la llave pública.
Computación λ()n), donde λ Es la función totiente de Carmichael. Desde n = pq, λ()n) = lcm(λ()p),λ()q), y desde p y q son primos, λ()p) φ()p) p − 1, y también λ()q) q − 1. Por lo tanto λ()n) = lcm(p, 1, q −1).
- El $lcm$ puede ser calculado a través del algoritmo Euclideano, ya $lcm(a, b) Silencio ab Silencio / gcd(a, b)$ .
- $λ () n)$ se mantiene en secreto.
Elija un entero e tales que 1 e. λ()n) y gcd(e, λ()n) = 1; es decir, e y λ()n) son coprime.
- $e$ tener un poco de longitud y pequeño peso Hamming resulta en una encriptación más eficiente – el valor más comúnmente elegido para $e$ es $216 + 1 = 65537$ . El valor más pequeño (y más rápido) posible para $e$ es 3, pero un valor tan pequeño para $e$ ha demostrado ser menos seguro en algunos ajustes.
- $e$ es liberado como parte de la llave pública.
Determine d como d ↑ e⁻¹ (modelo) λ()n); es decir, d es el inverso multiplicativo modular de e modulo λ()n).
- Esto significa: resolver para $d$ la ecuación $de (modelo) λ () n)$ ; $d$ puede ser calculado eficientemente utilizando el algoritmo de Euclidean extendido, ya que, gracias a $e$ y $λ () n)$ ser coprime, dicha ecuación es una forma de identidad de Bézout, donde $d$ es uno de los coeficientes.
- $d$ se mantiene en secreto como exponente de clave privada.

La clave pública consta del módulo $n$ y el exponente público (o cifrado) $e$ . La clave privada consta del exponente privado (o descifrado) $d$ , que debe mantenerse en secreto. $p$ , $q$ , y $λ (n)$ también deben mantenerse en secreto porque pueden usarse para calcular $d$ . De hecho, se pueden descartar todos después de calcular $d$ .

En el artículo original de RSA, la función totient de Euler $φ (n) = (p - 1)(q - 1)$ se usa en lugar de $λ (n)$ para calcular el exponente privado $d$ . Dado que $φ (n)$ siempre es divisible por $λ (n)$ , el algoritmo también funciona. La posibilidad de utilizar la función totient de Euler resulta también del teorema de Lagrange aplicado al grupo multiplicativo de los enteros módulo pq. Por lo tanto, cualquier $d$ que satisfaga a $d \cdot e \equiv 1 (mod φ (n))$ también satisface $d \cdot e \equiv 1 (mod λ (n))$ . Sin embargo, calcular $d$ modulo $φ (n)$ a veces producirá un resultado mayor de lo necesario (es decir, $d > λ (n)$ ). La mayoría de las implementaciones de RSA aceptarán exponentes generados usando cualquier método (si usan el exponente privado $d$ en absoluto, en lugar de usar el método de descifrado optimizado basado en el teorema del resto chino que se describe a continuación), pero algunos estándares como FIPS 186-4 pueden requerir que $d < λ (n)$ . Cualquier "sobredimensionado" los exponentes privados que no cumplan con este criterio siempre se pueden reducir módulo $λ (n)$ para obtener un exponente equivalente más pequeño.

Dado que cualquier factor común de $(p - 1)$ y $(q - 1)$ están presentes en la factorización de $n - 1 = pq - 1 = (p - 1)(q - 1) + (p - 1) + (q - 1), se recomienda que (p - 1) y (q - 1) solo tienen factores comunes muy pequeños, si cualquiera, además de los necesarios 2.$

Nota: los autores del artículo original de RSA llevan a cabo la generación de claves eligiendo $d$ y luego calculando $e$ como el inverso multiplicativo modular de $d$ módulo $φ (n)$ , mientras que la mayoría de las implementaciones actuales de RSA, como las que siguen a PKCS#1, hacen lo contrario (elija $e$ y calcule $d). Dado que la clave elegida puede ser pequeña, mientras que la clave calculada normalmente no lo es, el algoritmo del documento RSA optimiza el descifrado en comparación con el cifrado, mientras que el algoritmo moderno optimiza el cifrado.$

Distribución de claves

Supongamos que Bob quiere enviar información a Alice. Si deciden usar RSA, Bob debe conocer la clave pública de Alice para cifrar el mensaje y Alice debe usar su clave privada para descifrar el mensaje.

Para permitir que Bob envíe sus mensajes cifrados, Alice transmite su clave pública $(n, e)$ a Bob a través de una ruta confiable, pero no necesariamente secreta. La clave privada de Alice $(d)$ nunca se distribuye.

Cifrado

Después de que Bob obtenga la clave pública de Alice, puede enviar un mensaje $M$ a Alice.

Para hacerlo, primero convierte $M$ (estrictamente hablando, el texto plano sin relleno) en un número entero $m$ (estrictamente hablando, el texto sin formato acolchado), tal que $0 \leq m < n$ mediante el uso de un protocolo reversible acordado conocido como esquema de relleno. Luego calcula el texto cifrado $c$ , utilizando la clave pública de Alice $e$ , correspondiente a

{displaystyle cequiv m^{e}{pmod {n}}.}

Esto se puede hacer razonablemente rápido, incluso para números muy grandes, usando exponenciación modular. Bob luego transmite $c$ a Alice. Tenga en cuenta que al menos nueve valores de $m$ producirán un texto cifrado $c$ igual a $m$ , pero es muy poco probable que esto ocurra en la práctica.

Descifrado

Alice puede recuperar $m$ de $c$ utilizando su exponente de clave privada $d$ calculando

{displaystyle c^{d}equiv (m^{e})^{d}equiv m{pmod {n}}.}

Con $m$ , puede recuperar el mensaje original $M$ invirtiendo el esquema de relleno.

Ejemplo

Este es un ejemplo de cifrado y descifrado RSA. Los parámetros utilizados aquí son artificialmente pequeños, pero también se puede utilizar OpenSSL para generar y examinar un par de claves real.

Elija dos números principales distintos, como
$p=61$ y $q=53$ .
Computación $n = pq$ dar
${displaystyle n=61times 53=3233.}$
Computar la función totiente del producto del Carmichael como $λ () n) = lcm(p, 1, q -1)$ dar
${displaystyle lambda (3233)=operatorname {lcm} (60,52)=780.}$
Elija cualquier número $1 e c) 780$ que es coprime a 780. Elegir un número primo para $e$ nos deja sólo para comprobar que $e$ no es un divisor de 780.
Vamos $e=17$ .
Computación $d$ , el inverso multiplicativo modular de $e (modelo) λ () n)$ , rendimiento
${displaystyle d=413,}$ como ${displaystyle 1=(17times 413){bmod {7}}80.}$

La clave pública es $(n = 3233, e = 17)$ . Para un mensaje de texto sin formato rellenado $m$ , la función de cifrado es

{displaystyle {begin{aligned}c(m)&=m^{e}{bmod {n}}\&=m^{17}{bmod {3}}233.end{aligned}}}

La clave privada es $(n = 3233, d = 413)$ . Para un texto cifrado cifrado $c$ , la función de descifrado es

{displaystyle {begin{aligned}m(c)&=c^{d}{bmod {n}}\&=c^{413}{bmod {3}}233.end{aligned}}}

Por ejemplo, para cifrar $m = 65$ , se calcula

{displaystyle c=65^{17}{bmod {3}}233=2790.}

Para descifrar $c = 2790$ , se calcula

{displaystyle m=2790^{413}{bmod {3}}233=65.}

Ambos cálculos se pueden realizar de manera eficiente mediante el algoritmo de multiplicar y elevar al cuadrado para la exponenciación modular. En situaciones de la vida real, los números primos seleccionados serían mucho más grandes; en nuestro ejemplo, sería trivial factorizar $n = 3233$ (obtenido de la clave pública disponible gratuitamente) de vuelta a los primos $p$ y $q$ . $e$ , también de la clave pública, se invierte para obtener $d$ , adquiriendo así la clave privada.

Las implementaciones prácticas usan el teorema del resto chino para acelerar el cálculo usando el módulo de factores (mod pq usando mod p y mod q).

Los valores $d p$ , $d q$ y $q inv$ , que son parte de la clave privada se calculan de la siguiente manera:

{displaystyle {begin{aligned}d_{p}&=d{bmod {(}}p-1)=413{bmod {(}}61-1)=53,\d_{q}&=d{bmod {(}}q-1)=413{bmod {(}}53-1)=49,\q_{text{inv}}&=q^{-1}{bmod {p}}=53^{-1}{bmod {6}}1=38\&Rightarrow (q_{text{inv}}times q){bmod {p}}=38times 53{bmod {6}}1=1.end{aligned}}}

Así es como $d p$ , d_q y $q inv$ se utilizan para un descifrado eficiente (el cifrado es eficiente si se elige un $d$ y $e$ ):

{displaystyle {begin{aligned}m_{1}&=c^{d_{p}}{bmod {p}}=2790^{53}{bmod {6}}1=4,\m_{2}&=c^{d_{q}}{bmod {q}}=2790^{49}{bmod {5}}3=12,\h&=(q_{text{inv}}times (m_{1}-m_{2})){bmod {p}}=(38times -8){bmod {6}}1=1,\m&=m_{2}+htimes q=12+1times 53=65.end{aligned}}}

Firma de mensajes

Supongamos que Alice usa la clave pública de Bob para enviarle un mensaje cifrado. En el mensaje, ella puede decir que es Alice, pero Bob no tiene forma de verificar que el mensaje sea de Alice, ya que cualquiera puede usar la clave pública de Bob para enviarle mensajes encriptados. Para verificar el origen de un mensaje, RSA también se puede usar para firmar un mensaje.

Supongamos que Alice desea enviar un mensaje firmado a Bob. Puede usar su propia clave privada para hacerlo. Produce un valor hash del mensaje, lo eleva a la potencia de $d$ (módulo $n$ ) (como lo hace cuando descifra un mensaje) y lo adjunta como una "firma" al mensaje Cuando Bob recibe el mensaje firmado, usa el mismo algoritmo hash junto con la clave pública de Alice. Eleva la firma a la potencia de $e$ (módulo $n$ ) (como lo hace cuando encripta un mensaje) y compara el valor hash resultante con el valor hash del mensaje. Si los dos están de acuerdo, sabrá que el autor del mensaje estaba en posesión de la clave privada de Alice y que el mensaje no ha sido manipulado desde que se envió.

Esto funciona debido a las reglas de exponenciación:

{displaystyle h=operatorname {hash} (m),}

{displaystyle (h^{e})^{d}=h^{ed}=h^{de}=(h^{d})^{e}equiv h{pmod {n}}.}

Por lo tanto, las claves pueden intercambiarse sin pérdida de generalidad, es decir, una clave privada de un par de claves puede usarse para:

Descifrar un mensaje únicamente destinado al destinatario, que puede ser encriptado por cualquiera que tenga la clave pública (transporte encriptado asimétrico).
Encriptar un mensaje que puede ser descifrado por cualquiera, pero que sólo puede ser cifrado por una persona; esto proporciona una firma digital.

Pruebas de corrección

Demostración usando el pequeño teorema de Fermat

La prueba de la corrección de RSA se basa en el pequeño teorema de Fermat, que establece que $a p - 1 \equiv 1 (mod p)$ para cualquier número entero $a$ y prime $p$ , sin dividir $a.$

Queremos mostrar que

{displaystyle (m^{e})^{d}equiv m{pmod {pq}}}

m

p

q

e

d

ed (modelo) λ () pq)

Ya que $λ (pq) = lcm(p - 1, q - 1)$ es, por construcción, divisible por $p - 1$ y $q - 1$ , podemos escribir

{displaystyle ed-1=h(p-1)=k(q-1)}

h

k

Para comprobar si dos números, como $m ed$ y $m$ , son congruentes $mod pq$ , basta (y de hecho es equivalente) comprobar que son congruentes $mod p$ y $mod q$ por separado.

Para mostrar $m ed \equiv m (mod p)$ , consideramos dos casos:

Si $m (modelo) p)$ , $m$ es un múltiple de $p$ . Así m^ed es un múltiple de $p$ . Así que... $m ed ANTERIOR m (modelo) p)$ .
Si $not equiv$ ,
${displaystyle m^{ed}=m^{ed-1}m=m^{h(p-1)}m=(m^{p-1})^{h}mequiv 1^{h}mequiv m{pmod {p}},}$
donde usamos el pequeño teorema de Fermat para reemplazar $m p -1 mod p$ con 1.

La verificación de que $m ed \equiv m (mod q)$ procede de manera completamente análoga:

Si $m (modelo) q)$ , m^ed es un múltiple de $q$ . Así que... $m ed ANTERIOR m (modelo) q)$ .
Si $not equiv$ ,
${displaystyle m^{ed}=m^{ed-1}m=m^{k(q-1)}m=(m^{q-1})^{k}mequiv 1^{k}mequiv m{pmod {q}}.}$

Esto completa la prueba de que, para cualquier número entero $m$ , y los números enteros $e$ , $d$ tal que $ed \equiv 1 (mod λ (pq))$ ,

{displaystyle (m^{e})^{d}equiv m{pmod {pq}}.}

Notas

^ No podemos romper RSA trivialmente aplicando el teorema (mod pqPorque... $pq$ no es primo.
^ In particular, the statement above holds for any $e$ y $d$ que satisfacen $ed (modelo) p - 1) q - 1))$ , desde $() p - 1) q -1)$ es divisible por $λ () pq)$ , y por lo tanto trivialmente también $p - 1$ y $q - 1$ . However, in modern implementations of RSA, it is common to use a reduced private exponent $d$ que sólo satisface al débil, pero suficiente condición $ed (modelo) λ () pq)$ .
^ Esto es parte del teorema restante chino, aunque no es la parte significativa de ese teorema.

Prueba usando el teorema de Euler

Aunque el artículo original de Rivest, Shamir y Adleman usó el pequeño teorema de Fermat para explicar por qué funciona RSA, es común encontrar pruebas que se basen en el teorema de Euler.

Queremos mostrar que $m ed \equiv m (mod n)$ , donde $n = pq$ es un producto de dos números primos diferentes, y $e$ y $d$ son enteros positivos que satisfacen $ed \equiv 1 (mod φ (n))$ . Desde $e$ y $d$ son positivos, podemos escribir $ed = 1 + hφ (n)$ para algunos no -entero negativo $h$ . Suponiendo que $m$ es relativamente principal para $n$ , tenemos

{displaystyle m^{ed}=m^{1+hvarphi (n)}=m(m^{varphi (n)})^{h}equiv m(1)^{h}equiv m{pmod {n}},}

donde la penúltima congruencia se deriva del teorema de Euler.

Más generalmente, para cualquier $e$ y $d$ satisface $ed \equiv 1 (mod λ (n))$ , la misma conclusión se sigue de la generalización de Carmichael del teorema de Euler, que establece que $m λ (n) \equiv 1 (mod n)$ para todos los $m$ relativamente primo a $n$ .

Cuando $m$ no es relativamente primo a $n$ , el argumento recién proporcionado no es válido. Esto es altamente improbable (solo una proporción de $1/ p + 1/ q - 1/(pq)$ los números tienen esta propiedad), pero incluso en este caso, la congruencia deseada sigue siendo cierta. O $m \equiv 0 (mod p)$ o $m \equiv 0 (mod q)$ , y estos casos se pueden tratar con la prueba anterior.

Relleno

Ataques contra RSA simple

Hay una serie de ataques contra RSA simple, como se describe a continuación.

Al encriptar con exponentes de baja encriptación (por ejemplo, $e = 3$ ) y pequeños valores de los $m$ (es decir, $m . n 1/ e$ ), el resultado de $m e$ es estrictamente menos que el módulo $n$ . En este caso, los cifertextos se pueden descifrar fácilmente tomando el $e$ la raíz del cifertexto sobre los enteros.
Si el mismo mensaje de texto claro es enviado a $e$ o más receptores de forma encriptada, y los receptores comparten el mismo exponente $e$ , pero diferente $p$ , $q$ , y por consiguiente $n$ , entonces es fácil descifrar el mensaje original de texto claro a través del teorema restante chino. Johan Håstad notó que este ataque es posible incluso si los textos claros no son iguales, pero el atacante conoce una relación lineal entre ellos. Este ataque fue mejorado posteriormente por Don Coppersmith (ver el ataque de Coppersmith).
Debido a que la encriptación RSA es un algoritmo de encriptación determinista (es decir, no tiene componente aleatorio) un atacante puede lanzar exitosamente un ataque de texto simple elegido contra el criptosistema, encriptando probables texto bajo la clave pública y probar si son iguales al criptotexto. Un criptosistema se llama semánticamente seguro si un atacante no puede distinguir dos encriptaciones entre sí, incluso si el atacante sabe (o ha elegido) los correspondientes texto. RSA sin relleno no es semánticamente seguro.
RSA tiene la propiedad de que el producto de dos cifertextos es igual al cifrado del producto de los respectivos textos. Eso es, $m 1 e m 2 e ↑ m 1 m 2) e (modelo) n)$ . Debido a esta propiedad multiplicativa, es posible un ataque de principio elegido. Por ejemplo, un atacante que quiere saber la descifración de un cifertexto $c ↑ m e (modelo) n)$ puede preguntar al titular de la llave privada $d$ para descifrar un cifertexto de aspecto insospechado $c ̈ cr e (modelo) n)$ para algún valor $r$ elegido por el atacante. Debido a la propiedad multiplicadora, $c$ ' es el cifrado de $mr (modelo) n)$ . Por lo tanto, si el atacante tiene éxito con el ataque, aprenderán $mr (modelo) n),$ del cual pueden derivar el mensaje $m$ multiplicando $mr$ con el inverso modular de $r$ modulo $n$ .
Dado el exponente privado $d$ , uno puede factor eficientemente el módulo $n = pq$ . Y dada la factorización del módulo $n = pq$ , se puede obtener cualquier llave privada ( $d$ ', $n$ ) generado contra una llave pública ( $e$ ', $n$ ).

Esquemas de relleno

Para evitar estos problemas, las implementaciones prácticas de RSA suelen incorporar algún tipo de relleno aleatorio estructurado en el valor $m$ antes de cifrarlo. Este relleno garantiza que $m$ no caiga en el rango de textos sin formato inseguros, y que un mensaje determinado, una vez rellenado, se cifrará para uno de un gran número de diferentes posibles textos cifrados.

Estándares como PKCS#1 se diseñaron cuidadosamente para proteger los mensajes antes del cifrado RSA. Debido a que estos esquemas rellenan el texto sin formato $m$ con una cierta cantidad de bits adicionales, el tamaño del mensaje sin relleno $M$ debe ser algo más pequeña. Los esquemas de relleno RSA deben diseñarse cuidadosamente para evitar ataques sofisticados que pueden ser facilitados por una estructura de mensaje predecible. Las primeras versiones del estándar PKCS#1 (hasta la versión 1.5) usaban una construcción que parece hacer que RSA sea semánticamente seguro. Sin embargo, en Crypto 1998, Bleichenbacher demostró que esta versión es vulnerable a un ataque práctico de texto cifrado elegido adaptativo. Además, en Eurocrypt 2000, Coron et al. mostró que para algunos tipos de mensajes, este relleno no proporciona un nivel de seguridad lo suficientemente alto. Las versiones posteriores del estándar incluyen relleno de cifrado asimétrico óptimo (OAEP), que evita estos ataques. Como tal, OAEP debe usarse en cualquier aplicación nueva y el relleno PKCS#1 v1.5 debe reemplazarse siempre que sea posible. El estándar PKCS#1 también incorpora esquemas de procesamiento diseñados para brindar seguridad adicional para las firmas RSA, p. el Esquema de Firma Probabilística para RSA (RSA-PSS).

Los esquemas de relleno seguro como RSA-PSS son tan esenciales para la seguridad de la firma de mensajes como lo son para el cifrado de mensajes. Se concedieron dos patentes de EE. UU. sobre PSS (Patente de EE. UU. 6.266.771 y Patente de EE. UU. 7.036.014); sin embargo, estas patentes expiraron el 24 de julio de 2009 y el 25 de abril de 2010, respectivamente. El uso de PSS ya no parece estar gravado por patentes. Tenga en cuenta que el uso de diferentes pares de claves RSA para el cifrado y la firma es potencialmente más seguro.

Consideraciones prácticas y de seguridad

Usando el algoritmo del resto chino

Para mayor eficiencia, muchas bibliotecas criptográficas populares (como OpenSSL, Java y.NET) utilizan para descifrar y firmar la siguiente optimización basada en el teorema del resto chino. Los siguientes valores se calculan previamente y se almacenan como parte de la clave privada:

$p$ y $q$ – los primeros de la generación clave,
${displaystyle d_{P}=d{pmod {p-1}},}$
${displaystyle d_{Q}=d{pmod {q-1}},}$
${displaystyle q_{text{inv}}=q^{-1}{pmod {p}}.}$

Estos valores permiten al receptor calcular la exponencia $m = c d (modelo) pq)$ más eficientemente como sigue:
${displaystyle m_{1}=c^{d_{P}}{pmod {p}}}$ ,
${displaystyle m_{2}=c^{d_{Q}}{pmod {q}}}$ ,
${displaystyle h=q_{text{inv}}(m_{1}-m_{2}){pmod {p}}}$ ,
${displaystyle m=m_{2}+hq{pmod {pq}}}$ .

Esto es más eficiente que calcular la exponenciación elevando al cuadrado, aunque se deben calcular dos exponenciaciones modulares. La razón es que estas dos exponenciaciones modulares usan un exponente más pequeño y un módulo más pequeño.

Factorización de enteros y problema RSA

La seguridad del criptosistema RSA se basa en dos problemas matemáticos: el problema de factorizar números grandes y el problema RSA. Se cree que el descifrado completo de un texto cifrado RSA no es factible si se supone que ambos problemas son difíciles, es decir, no existe un algoritmo eficiente para resolverlos. Proporcionar seguridad contra el descifrado parcial puede requerir la adición de un esquema de relleno seguro.

El problema RSA se define como la tarea de tomar $e$ ésima raíz módulo un compuesto $n$ : recuperar un valor $m$ tal que $c \equiv m e (modificación n)$ , donde $(n, e)$ es una clave pública RSA y el estilo $c$ es un texto cifrado RSA. Actualmente, el enfoque más prometedor para resolver el problema de RSA es factorizar el módulo $n$ . Con la capacidad de recuperar factores primos, un atacante puede calcular el exponente secreto $d$ a partir de una clave pública $(n, e)$ , luego descifrar $c$ usando el procedimiento estándar. Para lograr esto, un atacante factoriza $n$ en $p$ y $q$ , y calcula $lcm(p - 1, q - 1)$ que permite determinar $d$ a partir de $e$ . Todavía no se ha encontrado ningún método de tiempo polinomial para factorizar enteros grandes en una computadora clásica, pero no se ha demostrado que exista ninguno; ver factorización de enteros para una discusión de este problema.

Se puede usar la criba cuadrática de polinomios múltiples (MPQS) para factorizar el módulo público $n$ .

La primera factorización de RSA-512 en 1999 usó cientos de computadoras y requirió el equivalente a 8400 MIPS años, durante un tiempo transcurrido de aproximadamente siete meses. En 2009, Benjamin Moody pudo factorizar una clave RSA de 512 bits en 73 días usando solo software público (GGNFS) y su computadora de escritorio (una Athlon64 de doble núcleo con una CPU de 1900 MHz). Se necesitaron poco menos de 5 gigabytes de almacenamiento en disco y unos 2,5 gigabytes de RAM para el proceso de tamizado.

Rivest, Shamir y Adleman señalaron que Miller ha demostrado que, asumiendo la verdad de la hipótesis de Riemann extendida, encontrar $d$ de $n$ y $e$ es tan difícil como factorizar $n$ en $p$ y $q$ (hasta una diferencia de tiempo polinomial). Sin embargo, Rivest, Shamir y Adleman señalaron, en la sección IX/D de su artículo, que no habían encontrado una prueba de que invertir RSA fuera tan difícil como factorizar.

A partir del 2020, el mayor número RSA factorizado conocido públicamente tenía 829 bits (250 dígitos decimales, RSA-250). Su factorización, mediante una implementación distribuida de última generación, tomó aproximadamente 2700 años de CPU. En la práctica, las claves RSA suelen tener una longitud de 1024 a 4096 bits. En 2003, RSA Security estimó que era probable que las claves de 1024 bits se pudieran descifrar para 2010. A partir de 2020, no se sabe si tales claves se pueden descifrar, pero las recomendaciones mínimas se han movido a al menos 2048 bits. En general, se supone que RSA es seguro si $n$ es lo suficientemente grande, fuera de la computación cuántica.

Si $n$ es de 300 bits o menos, se puede factorizar en unas pocas horas en una computadora personal, utilizando software ya disponible de forma gratuita. Se demostró que las claves de 512 bits eran prácticamente rompibles en 1999, cuando se factorizó RSA-155 usando varios cientos de computadoras, y ahora se factorizan en unas pocas semanas usando hardware común. En 2011 se informaron exploits que usaban certificados de firma de código de 512 bits que pueden haber sido factorizados. Un dispositivo de hardware teórico llamado TWIRL, descrito por Shamir y Tromer en 2003, cuestionó la seguridad de las claves de 1024 bits.

En 1994, Peter Shor demostró que una computadora cuántica, si alguna vez se pudiera crear una para ese propósito, sería capaz de tener en cuenta el tiempo polinomial, rompiendo RSA; ver Algoritmo de Shor.

Generación de clave defectuosa

Encontrar los números primos grandes $p$ y $q$ generalmente se realiza probando números aleatorios del tamaño correcto con pruebas de primalidad probabilística que eliminan rápidamente prácticamente todos los no primos.

Los números $p$ y $q$ no debe estar "demasiado cerca", para que la factorización de Fermat para $n$ sea exitosa. Si $p - q$ es menor que $2 n 1/4$ ( $n = p \cdot q$ , que incluso para valores "pequeños" de 1024 bits de $n$ es 3×10⁷⁷), resolviendo $p$ y $q$ es trivial. Además, si $p - 1$ o $q - 1$ tiene solo pequeños factores primos, $n$ pueden ser factorizados rápidamente por el algoritmo p − 1 de Pollard, y por lo tanto tales valores de $p$ o $q$ deben descartarse.

Es importante que el exponente privado $d$ sea lo suficientemente grande. Michael J. Wiener demostró que si $p$ está entre $q$ y $2 q$ (que es bastante típico) y $d < n 1/4 /3$ , luego $d$ se puede calcular de manera eficiente desde $n$ y $e$ .

No se conoce ningún ataque contra pequeños exponentes públicos como $e = 3$ , siempre que se utilice el relleno adecuado. El ataque de Coppersmith tiene muchas aplicaciones para atacar RSA específicamente si el exponente público $e$ es pequeño y si el mensaje cifrado es corto y no acolchado. 65537 es un valor de uso común para $e$ ; este valor se puede considerar como un compromiso entre evitar posibles ataques de pequeño exponente y aún permitir cifrados eficientes (o verificación de firma). La publicación especial del NIST sobre seguridad informática (SP 800-78 Rev. 1 de agosto de 2007) no permite exponentes públicos $e$ menores que 65537, pero no indica el motivo de esta restricción.

En octubre de 2017, un equipo de investigadores de la Universidad de Masaryk anunció la vulnerabilidad ROCA, que afecta a las claves RSA generadas por un algoritmo integrado en una biblioteca de Infineon conocida como RSALib. Se demostró que una gran cantidad de tarjetas inteligentes y módulos de plataforma confiable (TPM) se vieron afectados. Las claves RSA vulnerables se identifican fácilmente mediante un programa de prueba que lanzó el equipo.

Importancia de una fuerte generación de números aleatorios

Para generar los números primos $p$ se debe usar un generador de números aleatorios criptográficamente fuerte, que se haya sembrado correctamente con la entropía adecuada. y $q$ . A principios de 2012, Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung y Christophe Wachter llevaron a cabo un análisis que comparó millones de claves públicas recopiladas de Internet. Pudieron factorizar el 0,2 % de las claves usando solo el algoritmo de Euclides.

Aprovecharon una debilidad exclusiva de los criptosistemas basados en la factorización de enteros. Si $n = pq$ es una clave pública, y $n' = p' q'$ es otro, entonces si por casualidad $p = p'$ (pero $q$ no es igual a $q$ '), luego un simple cálculo de $gcd(n, n') = p$ factores tanto $n$ como $n$ ', comprometiendo totalmente ambas claves. Lenstra et al. tenga en cuenta que este problema se puede minimizar mediante el uso de una semilla aleatoria fuerte de una longitud de bits del doble del nivel de seguridad previsto, o mediante el empleo de una función determinista para elegir $q$ dado $p$ , en lugar de elegir $p$ y $q$ de forma independiente.

Nadia Heninger era parte de un grupo que hizo un experimento similar. Usaron una idea de Daniel J. Bernstein para calcular el GCD de cada clave RSA $n$ contra el producto de todas las demás claves n' habían encontrado (un número de 729 millones de dígitos), en lugar de calcular cada $mcd(n, n')$ por separado, logrando así una aceleración muy significativa, ya que después de una gran división, el problema de MCD es de tamaño normal.

Heninger dice en su blog que las claves incorrectas ocurrieron casi en su totalidad en aplicaciones integradas, incluidos "cortafuegos, enrutadores, dispositivos VPN, dispositivos de administración de servidores remotos, impresoras, proyectores y teléfonos VOIP" de más de 30 fabricantes. Heninger explica que el problema de un primo compartido descubierto por los dos grupos resulta de situaciones en las que el generador de números pseudoaleatorios tiene una semilla inicial deficiente y luego se vuelve a sembrar entre la generación del primer y el segundo primo. El uso de semillas de entropía suficientemente alta obtenidas a partir de tiempos de pulsación de tecla o ruido de diodo electrónico o ruido atmosférico de un receptor de radio sintonizado entre estaciones debería resolver el problema.

La generación de números aleatorios sólidos es importante en todas las fases de la criptografía de clave pública. Por ejemplo, si se usa un generador débil para las claves simétricas que distribuye RSA, un intruso podría omitir RSA y adivinar las claves simétricas directamente.

Ataques de tiempo

Kocher describió un nuevo ataque a RSA en 1995: si Eve conoce el hardware de Alice con suficiente detalle y puede medir los tiempos de descifrado de varios textos cifrados conocidos, Eve puede deducir la clave de descifrado $d$ rápidamente. Este ataque también se puede aplicar contra el esquema de firma RSA. En 2003, Boneh y Brumley demostraron un ataque más práctico capaz de recuperar factorizaciones RSA a través de una conexión de red (por ejemplo, desde un servidor web habilitado para Secure Sockets Layer (SSL)). Este ataque aprovecha la información filtrada por la optimización del teorema del resto chino utilizada por muchas implementaciones de RSA.

Una forma de frustrar estos ataques es asegurarse de que la operación de descifrado lleve una cantidad de tiempo constante para cada texto cifrado. Sin embargo, este enfoque puede reducir significativamente el rendimiento. En cambio, la mayoría de las implementaciones de RSA utilizan una técnica alternativa conocida como cegamiento criptográfico. El cegamiento de RSA hace uso de la propiedad multiplicativa de RSA. En lugar de calcular $c d (mod n)$ , Alice primero elige un valor aleatorio secreto $r$ y calcula $(r e c) d (modificación n)$ . El resultado de este cálculo, después de aplicar el teorema de Euler, es $rc d (mod n)$ , por lo que el efecto de $r$ se puede eliminar multiplicando por su inversa. Se elige un nuevo valor de $r$ para cada texto cifrado. Con el cegamiento aplicado, el tiempo de descifrado ya no está correlacionado con el valor del texto cifrado de entrada, por lo que el ataque de tiempo falla.

Ataques adaptables de texto cifrado elegido

En 1998, Daniel Bleichenbacher describió el primer ataque práctico adaptativo de texto cifrado elegido contra mensajes cifrados con RSA utilizando el esquema de relleno PKCS #1 v1 (un esquema de relleno aleatoriza y agrega estructura a un mensaje cifrado con RSA, por lo que es posible determinar si un mensaje descifrado es válido). Debido a fallas en el esquema PKCS #1, Bleichenbacher pudo montar un ataque práctico contra las implementaciones RSA del protocolo Secure Sockets Layer y recuperar claves de sesión. Como resultado de este trabajo, los criptógrafos ahora recomiendan el uso de esquemas de relleno probados y seguros, como el relleno de cifrado asimétrico óptimo, y RSA Laboratories ha lanzado nuevas versiones de PKCS #1 que no son vulnerables a estos ataques.

Una variante de este ataque, denominada "BERserk", volvió en 2014. Afectó a Mozilla NSS Crypto Library, que fue utilizada principalmente por Firefox y Chrome.

Ataques de análisis de canal lateral

Se ha descrito un ataque de canal lateral mediante análisis de predicción de ramificaciones (BPA). Muchos procesadores usan un predictor de bifurcación para determinar si es probable que se tome o no una bifurcación condicional en el flujo de instrucciones de un programa. A menudo, estos procesadores también implementan subprocesos múltiples simultáneos (SMT). Los ataques de análisis de predicción de bifurcación utilizan un proceso de espionaje para descubrir (estadísticamente) la clave privada cuando se procesa con estos procesadores.

El análisis de predicción de bifurcación simple (SBPA) afirma mejorar el BPA de una manera no estadística. En su artículo, 'Sobre el poder del análisis de predicción de rama simple', los autores de SBPA (Onur Aciicmez y Cetin Kaya Koc) afirman haber descubierto 508 de los 512 bits de una clave RSA en 10 iteraciones.

En 2010 se describió un ataque de falla de energía en las implementaciones de RSA. El autor recuperó la clave variando el voltaje de energía de la CPU fuera de los límites; esto causó múltiples fallas de energía en el servidor.

Implementación complicada

Hay muchos detalles a tener en cuenta para implementar RSA de forma segura (PRNG sólido, exponente público aceptable...). Esto hace que la implementación sea un desafío, hasta el punto de que el libro Practical Cryptography With Go sugiere evitar RSA si es posible.

Implementaciones

Algunas bibliotecas de criptografía que brindan soporte para RSA incluyen:

Botan
Bouncy Castle
cryptlib
Crypto+
Libgcrypt
Nettle
OpenSSL
lobo Crypt
GnuTLS
Mbed TLS
LibreSSL

Te puede interesar
Computadora de color TRS-80
(leer más)
Te puede interesar
Inicialización perezosa
(leer más)
Te puede interesar
Descifrado de software
(leer más)
Más resultados...