RSA (criptosistema)

RSA ( Rivest–Shamir–Adleman ) es un criptosistema de clave pública , uno de los más antiguos y ampliamente utilizados para la transmisión segura de datos. Las siglas «RSA» provienen 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 de inteligencia de señales británica , por el matemático inglés Clifford Cocks . Ese sistema fue desclasificado en 1997. ^[2]

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 RSA crea y publica una clave pública basada en dos números primos grandes , junto con un valor auxiliar. Los números primos se mantienen en secreto. Cualquiera puede cifrar los mensajes mediante la clave pública, pero solo pueden descifrarlos quienes conozcan la clave privada. ^[1]

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 factorización es una pregunta abierta. ^[3] No hay métodos publicados para vencer al sistema si se utiliza una clave lo suficientemente grande.

RSA es un algoritmo relativamente lento, por lo que no se suele utilizar para cifrar directamente los datos de los usuarios. Con mayor frecuencia, se utiliza RSA para transmitir claves compartidas para criptografía de clave simétrica , que luego se utilizan para el cifrado y descifrado masivo.

La idea de un criptosistema de clave pública-privada asimétrico se atribuye a Whitfield Diffie y Martin Hellman , quienes publicaron este concepto en 1976. También introdujeron 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. ^[4] Además, al igual que Diffie-Hellman , RSA se basa en la exponenciación modular .

Ron Rivest , Adi Shamir y Leonard Adleman , del Instituto Tecnológico de Massachusetts , intentaron varias veces a lo largo de un año crear una función que fuera difícil de invertir. Rivest y Shamir, como científicos informáticos, propusieron muchas funciones potenciales, mientras que Adleman, como matemático, fue responsable de encontrar sus debilidades. Probaron muchos enfoques, incluidos los " polinomios de permutación" y los "polinomios de mochila ". Durante un tiempo, pensaron que lo que querían lograr era imposible debido a requisitos contradictorios. ^[5] En abril de 1977, pasaron la Pascua en la casa de un estudiante y bebieron mucho vino antes de regresar a sus hogares alrededor de la medianoche. ^[6] Rivest, incapaz de dormir, se tumbó 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 tenía gran parte del artículo listo al amanecer. El algoritmo ahora se conoce como RSA: las iniciales de sus apellidos en el mismo orden que su artículo. ^[7]

Clifford Cocks , un matemático inglés que trabajaba para la agencia de inteligencia británica Government Communications Headquarters (GCHQ), describió un sistema similar en un documento interno en 1973. ^[8] Sin embargo, dadas las computadoras relativamente caras necesarias para implementarlo en ese momento, se consideró principalmente una curiosidad y, hasta donde se sabe públicamente, nunca se implementó. Sus ideas y conceptos no fueron revelados hasta 1997 debido a su clasificación de alto secreto.

Kid-RSA (KRSA) es un sistema de cifrado de clave pública simplificado e inseguro publicado en 1997, diseñado para fines educativos. Algunas personas creen que aprender Kid-RSA brinda conocimientos sobre RSA y otros sistemas de cifrado de clave pública, análogos al DES simplificado . ^{[9] [10] [11] [12] [13]}

El 20 de septiembre de 1983 se concedió al MIT una patente que describe el algoritmo RSA: patente estadounidense 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 acoplado a al menos un terminal que tiene un dispositivo de codificación y a al menos un terminal que tiene un dispositivo de decodificación. Un mensaje que se va a transferir se cifra en texto cifrado en el terminal de codificación codificando el mensaje como un número M en un conjunto predeterminado. A continuación, ese número se eleva a una primera potencia predeterminada (asociada con el receptor previsto) y, finalmente, se calcula. El resto o residuo, C, se calcula cuando el número exponencial se divide por el producto de dos números primos predeterminados (asociados con el receptor previsto).

En agosto de 1977, en la columna Mathematical Games de la revista Scientific American , se publicó una descripción detallada del algoritmo . ^[7] Esto precedió a la fecha de presentación de la patente, en 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 los Estados Unidos tampoco habría sido legal.

Cuando se concedió la patente, su duración era de 17 años. La patente estaba a punto de expirar el 21 de septiembre de 2000, pero RSA Security hizo público el algoritmo el 6 de septiembre de 2000. ^[14]

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

Un principio básico detrás de RSA es la observación de que es práctico encontrar tres números enteros positivos muy grandes e , d y n , tales que para todos los números enteros m ( 0 ≤ m < n ), ambos y tienen el mismo resto cuando se dividen por (son congruentes módulo ): Sin embargo, cuando solo se dan e y n , es extremadamente difícil encontrar d .${\displaystyle (m^{e})^{d}}$${\estilo de visualización m}$${\estilo de visualización n}$ ${\estilo de visualización n}$$${\displaystyle (m^{e})^{d}\equiv m{\pmod {n}}.}$$

Los números enteros n y e constituyen la clave pública, d representa la clave privada y m representa el mensaje. La exponenciación modular de e y d corresponde al cifrado y al descifrado, respectivamente.

Además, como los dos exponentes se pueden intercambiar , la clave privada y pública también se pueden intercambiar, lo que permite la firma y verificación de mensajes utilizando el mismo algoritmo.

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

1. Elija dos números primos grandes p y q .
   • Para dificultar la factorización, p y q deben elegirse al azar, ser ambos grandes y tener una gran diferencia. ^[1] Para elegirlos, el método estándar es elegir números enteros aleatorios y utilizar una prueba de primalidad hasta encontrar dos primos.
   • p y q deben mantenerse en secreto.
2. Calcular n = pq .
   • n se utiliza como módulo tanto para las claves públicas como para las privadas. Su longitud, expresada habitualmente en bits, es la longitud de la clave .
   • n se libera como parte de la clave pública.
3. Calcular λ ( n ) , donde λ es la función totiente de Carmichael . Puesto que n = pq , λ ( n ) = mcm ( λ ( p ),  λ ( q )) , y puesto que p y q son primos, λ ( p ) = φ ( p ) = p − 1 , y asimismo λ ( q ) = q − 1 . Por lo tanto λ ( n ) = mcm( p − 1, q − 1) .
   • El mcm se puede calcular a través del algoritmo euclidiano , ya que mcm( a ,  b ) = ⁠| de |/mcd( a ,  b )⁠ .
   • λ ( n ) se mantiene en secreto.
4. Elija un entero e tal que 1 < e < λ ( n ) y mcd ( e , λ ( n )) = 1 ; es decir, e y λ ( n ) son coprimos .
   • e tiene una longitud de bits corta y un peso Hamming pequeño , lo que da como resultado un cifrado más eficiente: el valor más comúnmente elegido para e es 2 ¹⁶ + 1 =65 537 . El valor más pequeño (y más rápido) posible para e es 3, pero se ha demostrado queun valor tan pequeño para e es menos seguro en algunos entornos. ^[15]
   • e se publica como parte de la clave pública.
5. Determinar d como d ≡ e ⁻¹ (mod λ ( n )) ; es decir, d es el inverso multiplicativo modular de e módulo λ ( n ) .
   • Esto significa: resolver para d la ecuación de ≡ 1 (mod λ ( n )) ; d puede calcularse eficientemente utilizando el algoritmo euclidiano extendido , ya que, gracias a que e y λ ( n ) son coprimos, dicha ecuación es una forma de la identidad de Bézout , donde d es uno de los coeficientes.
   • d se mantiene en secreto como el exponente de clave privada .

La clave pública consiste en el módulo n y el exponente público (o de cifrado) e . La clave privada consiste en el exponente privado (o de descifrado) d , que debe mantenerse en secreto. p , q y λ ( n ) también deben mantenerse en secreto porque se pueden usar para calcular d . De hecho, todos ellos pueden descartarse después de que se haya calculado d . ^[16]

En el artículo original de RSA, ^[1] se utiliza la función totient de Euler φ ( n ) = ( p − 1)( q − 1) en lugar de λ ( n ) para calcular el exponente privado d . Dado que φ ( n ) siempre es divisible por λ ( n ) , el algoritmo funciona igual de bien. La posibilidad de utilizar la función totient de Euler resulta también del teorema de Lagrange aplicado al grupo multiplicativo de números enteros módulo pq . Por tanto, cualquier d que satisfaga d ⋅ e ≡ 1 (mod φ ( n )) también satisface d ⋅ e ≡ 1 (mod λ ( n )) . Sin embargo, calcular d módulo φ ( n ) a veces producirá un resultado mayor que el necesario (es decir, d > λ ( n ) ). La mayoría de las implementaciones de RSA aceptarán exponentes generados utilizando cualquiera de los dos métodos (si utilizan el exponente privado d , en lugar de utilizar 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 (Sección B.3.1) pueden requerir que d < λ ( n ) . Cualquier exponente privado "de gran tamaño" que no cumpla con este criterio siempre se puede 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á presente en la factorización de n − 1 = pq − 1 = ( p − 1)( q − 1) + ( p − 1) + ( q − 1) , ^{[17] [ ¿ fuente autopublicada? ]} se recomienda que ( p − 1) y ( q − 1) tengan solo factores comunes muy pequeños, si los hay, además del 2 necesario. ^{[1] [18] [19] [ verificación fallida ] [20] [ verificación fallida ]}

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 inverso (eligen e y calculan d ). Dado que la clave elegida puede ser pequeña, mientras que la clave calculada normalmente no lo es, el algoritmo del artículo de RSA optimiza el descifrado en comparación con el cifrado, mientras que el algoritmo moderno optimiza el cifrado en su lugar. ^{[1] [21]}

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

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.

Después de que Bob obtiene la clave pública de Alice, puede enviarle un mensaje M.

Para ello, primero convierte M (estrictamente hablando, el texto sin formato sin relleno) en un entero m (estrictamente hablando, el texto sin formato con relleno ), de modo que 0 ≤ 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 c\equiv m^{e}{\pmod {n}}.}$$

Esto se puede hacer con bastante rapidez, incluso para números muy grandes, utilizando la 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 , ^[a] pero es muy poco probable que esto ocurra en la práctica.

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

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

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

A continuación se muestra un ejemplo de cifrado y descifrado RSA: ^[b]

1. Elija dos números primos distintos, como por ejemplo

   ${\displaystyle p=61}$y .${\displaystyle q=53}$

2. Calcular n = pq dando

   ${\displaystyle n=61\times 53=3233.}$

3. Calcule la función totiente de Carmichael del producto como λ ( n ) = mcm ( p − 1, q − 1) dando

   ${\displaystyle \lambda (3233)=\operatorname {mcm} (60,52)=780.}$

4. Elija cualquier número 2 < e < 780 que sea coprimo de 780. Elegir un número primo para e nos deja solo para comprobar que e no es divisor de 780.

   Dejar .${\displaystyle e=17}$

5. Calcule d , el inverso multiplicativo modular de e (mod λ ( n )) , obteniendo como
   $${\displaystyle d=413,}$$${\displaystyle 1=(17\times 413){\bmod {7}}80.}$

La clave pública es ( n = 3233, e = 17) . Para un mensaje de texto simple 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 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 utilizando el algoritmo de elevar al cuadrado y multiplicar para la exponenciación modular . En situaciones de la vida real, los primos seleccionados serían mucho mayores; en nuestro ejemplo, sería trivial factorizar n = 3233 (obtenido de la clave pública disponible libremente) para obtener los primos p y q . Luego, se invierte e , también de la clave pública, para obtener d , adquiriendo así la clave privada.

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

Los valores d _p , d _q y q _inv , que forman 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}}=38\times 53{\bmod {6}}1=1.\end{aligned}}}$$

A continuación se muestra cómo se utilizan d _p , d _q y q _inv para un descifrado eficiente (el cifrado es eficiente mediante la elección de un par d y e adecuado ):$${\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}}=(38\times -8){\bmod {6}}1=1,\\m&=m_{2}+h \times q=12+1\times 53=65.\end{aligned}}}$$

Supongamos que Alice utiliza la clave pública de Bob para enviarle un mensaje cifrado. En el mensaje, ella puede afirmar ser Alice, pero Bob no tiene forma de verificar que el mensaje proviene de Alice, ya que cualquiera puede utilizar la clave pública de Bob para enviarle mensajes cifrados. Para verificar el origen de un mensaje, también se puede utilizar RSA para firmar un mensaje.

Supongamos que Alice desea enviar un mensaje firmado a Bob. Para ello, puede utilizar su propia clave privada. Produce un valor hash del mensaje, lo eleva a la potencia d (módulo n ) (como hace cuando descifra un mensaje) y lo adjunta como una "firma" al mensaje. Cuando Bob recibe el mensaje firmado, utiliza el mismo algoritmo hash junto con la clave pública de Alice. Eleva la firma a la potencia e (módulo n ) (como hace cuando cifra un mensaje) y compara el valor hash resultante con el valor hash del mensaje. Si ambos coinciden, sabe que el autor del mensaje estaba en posesión de la clave privada de Alice y que el mensaje no ha sido alterado desde que se envió.

Esto funciona gracias a las reglas de exponenciación :$${\displaystyle h=\nombreoperador {hash} (m),}$$$${\displaystyle (h^{e})^{d}=h^{ed}=h^{de}=(h^{d})^{e}\equiv h{\pmod {n}}.}$$

De esta manera, las claves se pueden intercambiar sin pérdida de generalidad, es decir, una clave privada de un par de claves se puede utilizar para:

1. Descifrar un mensaje destinado únicamente al destinatario, que puede ser cifrado por cualquier persona que disponga de la clave pública (transporte cifrado asimétrico).
2. Cifrar un mensaje que puede ser descifrado por cualquier persona, pero que sólo puede ser cifrado por una persona; esto proporciona una firma digital.

La prueba de la corrección de RSA se basa en el pequeño teorema de Fermat , que establece que a ^{p − 1} ≡ 1 (mod p ) para cualquier entero a y primo p , sin dividir a . ^{[nota 1]}

Queremos demostrar que para cada entero m cuando p y q son números primos distintos y e y d son enteros positivos que satisfacen ed ≡ 1 (mod λ ( pq )) .$${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}}$$

Dado que λ ( pq ) = mcm ( p − 1, q − 1) es, por construcción, divisible tanto por p − 1 como por q − 1 , podemos escribir para algunos enteros no negativos h y k . ^{[nota 2]}$${\displaystyle ed-1=h(p-1)=k(q-1)}$$

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. ^{[nota 3]}

Para demostrar que m ^ed ≡ m (mod p ) , consideramos dos casos:

1. Si m ≡ 0 (mod p ) , m es un múltiplo de p . Por lo tanto, m ^ed es un múltiplo de p . Por lo tanto, m ^ed ≡ 0 ≡ m (mod p ) .
2. Si m 0 (mod p )${\displaystyle \no \equiv}$ ,

   ${\displaystyle m^{ed}=m^{ed-1}m=m^{h(p-1)}m=(m^{p-1})^{h}m\equiv 1^{h}m\equiv 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 ≡ m (mod q ) se realiza de forma completamente análoga:

1. Si m ≡ 0 (mod q ) , m ^ed es un múltiplo de q . Por lo tanto, m ^ed ≡ 0 ≡ m (mod q ) .
2. Si m 0 (mod q )${\displaystyle \no \equiv}$ ,

   ${\displaystyle m^{ed}=m^{ed-1}m=m^{k(q-1)}m=(m^{q-1})^{k}m\equiv 1^{k}m\equiv m{\pmod {q}}.}$

Esto completa la prueba de que, para cualquier entero m y enteros e , d tales que ed ≡ 1 (mod λ ( pq )) ,$${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}.}$$

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

Queremos demostrar que m ^ed ≡ m (mod n ) , donde n = pq es un producto de dos números primos diferentes, y e y d son números enteros positivos que satisfacen ed ≡ 1 (mod φ ( n )) . Como e y d son positivos, podemos escribir ed = 1 + hφ ( n ) para algún número entero no negativo h . Suponiendo que m es primo relativo a n , tenemos$${\displaystyle m^{ed}=m^{1+h\varphi (n)}=m(m^{\varphi (n)})^{h}\equiv m(1)^{h}\equiv m{\pmod {n}},}$$

donde la segunda última congruencia se sigue del teorema de Euler .

De manera más general, para cualquier e y d que satisfaga ed ≡ 1 (mod λ ( n )) , la misma conclusión se desprende de la generalización de Carmichael del teorema de Euler , que establece que m ^{λ (n)} ≡ 1 (mod n ) para todos los m relativamente primos a n .

Cuando m no es primo relativo con respecto a n , el argumento que acabamos de dar no es válido. Esto es altamente improbable (solo una proporción de números 1/ p + 1/ q − 1/( pq ) tienen esta propiedad), pero incluso en este caso, la congruencia deseada sigue siendo cierta. O bien m ≡ 0 (mod p ) o bien m ≡ 0 (mod q ) , y estos casos se pueden tratar utilizando la prueba anterior.

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

• Al cifrar con exponentes de cifrado bajos (por ejemplo, e = 3 ) y valores pequeños de m (es decir, m < n ^{1/ e} ), el resultado de m ^e es estrictamente menor que el módulo n . En este caso, los textos cifrados se pueden descifrar fácilmente tomando la raíz e del texto cifrado sobre los números enteros.
• Si se envía el mismo mensaje de texto claro a e o más destinatarios de forma cifrada, y los receptores comparten el mismo exponente e , pero diferentes p , q y, por tanto , n , entonces es fácil descifrar el mensaje de texto claro original mediante el teorema del resto chino . Johan Håstad se dio cuenta de que este ataque es posible incluso si los textos claros no son iguales, pero el atacante conoce una relación lineal entre ellos. ^[22] Este ataque fue mejorado posteriormente por Don Coppersmith (véase el ataque de Coppersmith ). ^[23]
• Debido a que el cifrado RSA es un algoritmo de cifrado determinista (es decir, no tiene un componente aleatorio), un atacante puede lanzar con éxito un ataque de texto simple elegido contra el criptosistema, cifrando los textos simples probables con la clave pública y probando si son iguales al texto cifrado. Un criptosistema se considera semánticamente seguro si un atacante no puede distinguir dos cifrados entre sí, incluso si el atacante conoce (o ha elegido) los textos simples correspondientes. El RSA sin relleno no es semánticamente seguro. ^[24]
• RSA tiene la propiedad de que el producto de dos textos cifrados es igual al cifrado del producto de los respectivos textos planos. Es decir, m ₁ ^e m ₂ ^e ≡ ( m ₁ m ₂ ) ^e (mod n ) . Debido a esta propiedad multiplicativa, es posible un ataque de texto cifrado elegido . Por ejemplo, un atacante que quiere saber el descifrado de un texto cifrado c ≡ m ^e (mod n ) puede pedir al poseedor de la clave privada d que descifre un texto cifrado de apariencia no sospechosa c ′ ≡ cr ^e (mod n ) para algún valor r elegido por el atacante. Debido a la propiedad multiplicativa, c ' es el cifrado de mr (mod n ) . Por lo tanto, si el atacante tiene éxito con el ataque, aprenderá mr (mod n ), del cual puede derivar el mensaje m multiplicando mr con el inverso modular de r módulo n . ^{[ cita requerida ]}
• Dado el exponente privado d , se puede factorizar eficientemente el módulo n = pq . Y dada la factorización del módulo n = pq , se puede obtener cualquier clave privada ( d ',  n ) generada a partir de una clave pública ( e ',  n ). ^[15]

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

Los estándares como PKCS#1 han sido cuidadosamente diseñados para rellenar de forma segura los mensajes antes del cifrado RSA. Debido a que estos esquemas rellenan el texto simple m con una cierta cantidad de bits adicionales, el tamaño del mensaje M sin rellenar debe ser algo menor. Los esquemas de relleno RSA deben diseñarse cuidadosamente para evitar ataques sofisticados que pueden verse facilitados por una estructura de mensaje predecible. Las primeras versiones del estándar PKCS#1 (hasta la versión 1.5) utilizaban 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. ^[25] demostraron que para algunos tipos de mensajes, este relleno no proporciona un nivel de seguridad lo suficientemente alto. Las versiones posteriores del estándar incluyen el relleno de cifrado asimétrico óptimo (OAEP), que evita estos ataques. Por lo tanto, se debe utilizar OAEP en cualquier aplicación nueva y se debe reemplazar el relleno de PKCS#1 v1.5 siempre que sea posible. El estándar PKCS#1 también incorpora esquemas de procesamiento diseñados para brindar seguridad adicional a las firmas RSA, por ejemplo, el Esquema de Firma Probabilística para RSA ( RSA-PSS ).

Los esquemas de relleno seguros como RSA-PSS son tan esenciales para la seguridad de la firma de mensajes como para el cifrado de mensajes. Se concedieron dos patentes estadounidenses sobre PSS ( patente estadounidense 6.266.771 y patente estadounidense 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 obstaculizado por las patentes. ^{[ ¿ Investigación original? ]} Nótese que el uso de diferentes pares de claves RSA para el cifrado y la firma es potencialmente más seguro. ^[26]

Para lograr mayor eficiencia, muchas bibliotecas criptográficas populares (como OpenSSL , Java y .NET ) utilizan para el descifrado y la firma la siguiente optimización basada en el teorema del resto chino . ^{[27] [ cita requerida ]} Los siguientes valores se precalculan y almacenan como parte de la clave privada:

• ${\displaystyle p}$y  – los primos de la generación de claves,${\displaystyle q}$
• ${\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 destinatario calcular la exponenciación m = c ^d (mod pq ) de manera más eficiente de la siguiente manera: , , , ^[c] .
     ${\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}$

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 utilizan un exponente y un módulo más pequeños.

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 es inviable si se supone que ambos problemas son difíciles , es decir, que no existe un algoritmo eficiente para resolverlos. Para proporcionar seguridad contra el descifrado parcial puede ser necesario añadir un esquema de relleno seguro . ^[28]

El problema RSA se define como la tarea de tomar raíces e ésimas módulo de un compuesto n : recuperar un valor m tal que c ≡ m ^e (mod n ) , donde ( n , e ) es una clave pública RSA y c es un texto cifrado RSA. Actualmente, el enfoque más prometedor para resolver el problema 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 utilizando el procedimiento estándar. Para lograr esto, un atacante factoriza n en p y q , y calcula mcm( p − 1, q − 1) que permite la determinación de d a partir de e . Todavía no se ha encontrado ningún método de tiempo polinomial para factorizar números enteros grandes en una computadora clásica, pero no se ha demostrado que no exista ninguno; consulte factorización de números enteros para una discusión de este problema.

La criba cuadrática de polinomios múltiples (MPQS) se puede utilizar para factorizar el módulo público n .

La primera factorización RSA-512, realizada en 1999, utilizó cientos de ordenadores y requirió el equivalente a 8.400 MIPS años, durante un tiempo transcurrido de unos siete meses. ^{[29] En 2009, Benjamin Moody podía factorizar una clave RSA de 512 bits en 73 días utilizando únicamente software público (GGNFS) y su ordenador de sobremesa (un} Athlon64 de doble núcleo con una CPU de 1.900 MHz). Se requirieron 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 observaron ^[1] que Miller ha demostrado que, suponiendo la verdad de la hipótesis de Riemann extendida , encontrar d a partir de n y e es tan difícil como factorizar n en p y q (hasta una diferencia de tiempo polinomial). ^[30] Sin embargo, Rivest, Shamir y Adleman observaron, en la sección IX/D de su artículo, que no habían encontrado una prueba de que invertir RSA sea tan difícil como factorizar.

En 2020 , el mayor número RSA^[update] factorizado conocido públicamente tenía 829 bits (250 dígitos decimales, RSA-250 ). ^[31] Su factorización, mediante una implementación distribuida de última generación, tomó alrededor de 2700 años de CPU. En la práctica, las claves RSA suelen tener entre 1024 y 4096 bits de longitud. En 2003, RSA Security estimó que era probable que las claves de 1024 bits se volvieran descifrables en 2010. ^[32] En 2020, no se sabe si dichas claves se pueden descifrar, pero las recomendaciones mínimas se han trasladado a al menos 2048 bits. ^[33] En general, se presume 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 que ya está disponible gratuitamente. Se ha demostrado que las claves de 512 bits son prácticamente descifrables en 1999, cuando se factorizó RSA-155 utilizando varios cientos de computadoras, y ahora se factorizan en unas pocas semanas utilizando hardware común. En 2011 se informó de exploits que utilizan certificados de firma de código de 512 bits que pueden haber sido factorizados. ^[34] Un dispositivo de hardware teórico llamado TWIRL , descrito por Shamir y Tromer en 2003, puso en duda la seguridad de las claves de 1024 bits. ^[32]

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 factorizar el tiempo polinomial , rompiendo el RSA; véase el algoritmo de Shor .

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "RSA" cryptosystem – news · newspapers · books · scholar · JSTOR (October 2017) (Learn how and when to remove this message)

Para encontrar los números primos grandes p y q se suelen probar números aleatorios del tamaño correcto con pruebas de primalidad probabilística que eliminan rápidamente prácticamente todos los números no primos.

Los números p y q no deben ser "demasiado cercanos", para que la factorización de Fermat para n no tenga éxito. Si p − q es menor que 2 n ^1/4 ( n = p ⋅ q , que incluso para valores "pequeños" de 1024 bits de n es3 × 10 ⁷⁷ ), resolver p y q es trivial. Además, si p − 1 o q − 1 tiene solo factores primos pequeños, n se puede factorizar rápidamente mediante el algoritmo p − 1 de Pollard y, por lo tanto, dichos valores de p o q se deben descartar.

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

No se conoce ningún ataque contra exponentes públicos pequeños como e = 3 , siempre que se utilice el relleno adecuado. El ataque de Coppersmith tiene muchas aplicaciones para atacar a RSA, específicamente si el exponente público e es pequeño y si el mensaje cifrado es corto y no tiene relleno. 65537 es un valor de uso común para  e ; este valor puede considerarse como un compromiso entre evitar posibles ataques de exponente pequeño y seguir permitiendo cifrados eficientes (o verificación de firmas). 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 una razón para esta restricción.

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

Para generar los primos p y q se debe utilizar un generador de números aleatorios criptográficamente fuerte, que haya sido correctamente sembrado con la entropía adecuada. A principios de 2012, Arjen K. Lenstra , James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung y Christophe Wachter realizaron un análisis que comparaba millones de claves públicas obtenidas de Internet . Pudieron factorizar el 0,2 % de las claves utilizando únicamente el algoritmo de Euclides. ^{[37] [38] [ ¿ Fuente autopublicada? ]}

Explotaron una debilidad exclusiva de los criptosistemas basados ​​en la factorización de números enteros. Si n = pq es una clave pública y n ′ = p ′ q ′ es otra, entonces si por casualidad p = p ′ (pero q no es igual a q '), entonces un simple cálculo de mcd( n , n ′) = p factoriza tanto n como n ', comprometiendo totalmente ambas claves. Lenstra et al. señalan que este problema se puede minimizar utilizando una semilla aleatoria fuerte de longitud de bits el doble del nivel de seguridad deseado, o empleando una función determinista para elegir q dado p , en lugar de elegir p y q independientemente.

Nadia Heninger formó parte de un grupo que realizó un experimento similar. Utilizaron una idea de Daniel J. Bernstein para calcular el MCD de cada clave RSA n por el producto de todas las demás claves n ' que 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 del MCD es de tamaño normal.

Heninger dice en su blog que las claves incorrectas se produjeron casi exclusivamente en aplicaciones integradas, incluidos "cortafuegos, enrutadores, dispositivos VPN, dispositivos de administración remota de servidores, impresoras, proyectores y teléfonos VOIP" de más de 30 fabricantes. Heninger explica que el problema del número primo compartido descubierto por los dos grupos es el resultado de situaciones en las que el generador de números pseudoaleatorios está mal inicializado y luego se vuelve a inicializar entre la generación del primer y el segundo número primo. El uso de semillas de entropía suficientemente alta obtenidas a partir de tiempos de pulsación de teclas o ruido de diodo electrónico o ruido atmosférico de un receptor de radio sintonizado entre estaciones debería resolver el problema. ^[39]

La generación de números aleatorios potentes es importante en todas las fases de la criptografía de clave pública. Por ejemplo, si se utiliza un generador débil para las claves simétricas que se distribuyen mediante RSA, un espía podría eludir RSA y adivinar las claves simétricas directamente.

Kocher describió un nuevo ataque a RSA en 1995: si el atacante Eve conoce el hardware de Alice con suficiente detalle y es capaz de 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 con Secure Sockets Layer (SSL)). ^[40] Este ataque aprovecha la información filtrada por la optimización del teorema del resto chino utilizado por muchas implementaciones RSA.

Una forma de frustrar estos ataques es asegurar que la operación de descifrado tome una cantidad de tiempo constante para cada texto cifrado. Sin embargo, este enfoque puede reducir significativamente el rendimiento. En su lugar, la mayoría de las implementaciones de RSA utilizan una técnica alternativa conocida como cegamiento criptográfico . El cegamiento 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 (mod n ) . El resultado de este cálculo, después de aplicar el teorema de Euler , es rc ^d (mod n ) , y por lo tanto el efecto de r se puede eliminar multiplicando por su inverso. 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, y por lo tanto el ataque de tiempo falla.

En 1998, Daniel Bleichenbacher describió el primer ataque práctico de texto cifrado adaptable contra mensajes cifrados RSA utilizando el esquema de relleno PKCS #1 v1 (un esquema de relleno aleatoriza y añade estructura a un mensaje cifrado RSA, de modo que es posible determinar si un mensaje descifrado es válido). Debido a las fallas del 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 demostrablemente seguros como Optimal Asymmetric Encryption Padding , y RSA Laboratories ha lanzado nuevas versiones de PKCS #1 que no son vulnerables a estos ataques.

Una variante de este ataque, denominada "BERserk", regresó en 2014. ^{[41] [42]} Afectó a la biblioteca criptográfica NSS de Mozilla, que era utilizada principalmente por Firefox y Chrome.

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

El análisis de predicción de ramificaciones simples (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 ramificaciones simples", ^[43] los autores del 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 por falla de energía en las implementaciones de RSA. ^{[44] [ ¿ fuente autopublicada? ]} El autor recuperó la clave variando el voltaje de energía de la CPU fuera de los límites; esto provocó múltiples fallas de energía en el servidor.

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

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

• Botánica
• Castillo inflable
• criptalib
• Criptomoneda++
• Libgcrypt
• Ortiga
• OpenSSL
• Cripta del lobo
• GnuTLS
• TLS mbed
• LibreSSL

• Criptoanálisis acústico
• Teoría de la complejidad computacional
• Intercambio de claves Diffie-Hellman
• Algoritmo de firma digital
• Criptografía de curva elíptica
• Intercambio de claves
• Gestión de claves
• Tamaño de la clave
• Criptografía de clave pública
• Criptosistema Rabin
• Función de trampilla

• Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (octubre de 1996). Manual de criptografía aplicada . CRC Press. ISBN 978-0-8493-8523-0.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. págs. 881–887. ISBN 978-0-262-03293-3.

• La patente original de RSA presentada ante la Oficina de Patentes de EE. UU. por Rivest; Ronald L. (Belmont, MA), Shamir; Adi (Cambridge, MA), Adleman; Leonard M. (Arlington, MA), 14 de diciembre de 1977, patente de EE. UU. 4.405.829 .
• RFC 8017: PKCS #1: Especificaciones de criptografía RSA versión 2.2
• Explicación del RSA mediante lámparas de colores en YouTube
• Recorrido completo por RSA
• El juego del escondite de los números primos: cómo funciona el cifrado RSA
• Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: Sobre el poder del análisis de predicción de ramas simple