Sistema criptográfico RSA

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

1. Elige dos números primos grandes y distintos, p y q .
   • Para que la factorización sea inviable, p y q deben elegirse aleatoriamente de un amplio espacio de posibilidades, como todos los números primos entre 2¹⁰²³ y ^2¹⁰²⁴ (correspondientes a una clave de 2048 bits). En la práctica se utilizan muchos algoritmos diferentes para la selección ^de primos. ^{[ 29 ]}
   • p y q se mantienen en secreto.
2. Calcula n = pq .
   • n se utiliza como módulo tanto para la clave pública como para la privada. Su longitud, generalmente expresada en bits, es la longitud de la clave .
   • n se publica como parte de la clave pública.
3. Calcula λ ( n ) , donde λ es la función totiente de Carmichael . Como n = pq , λ ( n ) = mcm ( λ ( p ), λ ( q ))  , y como p y q son primos, λ ( p ) = φ ( p ) = p − 1 , y de igual manera λ ( q ) = q − 1 . Por lo tanto λ ( n ) = mcm( p − 1, q − 1) .
   • El mcm se puede calcular mediante el algoritmo euclidiano , ya que mcm( a , b   ) = | ab | / 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 con una longitud de bits corta y un peso de Hamming pequeño 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 un valor tan pequeño para e puede exponer vulnerabilidades en esquemas de relleno inseguros. ^{[ 30 ] [ a ]}
   • e se publica como parte de la clave pública.
5. Determina 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 se puede calcular 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 la clave privada .

La clave pública consta del módulo n y el exponente público e . La clave privada consta del exponente privado d , que debe mantenerse en secreto. p , q y λ ( n ) también deben mantenerse en secreto porque pueden usarse para calcular d . De hecho, todos ellos pueden descartarse una vez que se haya calculado d . ^{[ 31 ]}

En el artículo original de RSA, ^{[ 3 ]} se utiliza la función totiente 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 también funciona. La posibilidad de utilizar la función totiente de Euler también resulta del teorema de Lagrange aplicado al grupo multiplicativo de enteros módulo pq . Por lo tanto, cualquier d que satisfaga d ⋅ e ≡ 1 (mod φ ( n )) también satisface d ⋅ e ≡ 1 (mod λ ( n )) . Sin embargo, el cálculo de d módulo φ ( n ) a veces dará un resultado mayor de lo necesario (es decir, d > λ ( n ) ). La mayoría de las implementaciones de RSA aceptarán exponentes generados mediante cualquiera de los dos métodos (siempre que utilicen el exponente privado d , en lugar del método de descifrado optimizado basado en el teorema chino del resto 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 "sobredimensionado" que no cumpla este criterio siempre se puede reducir módulo λ ( n ) para obtener un exponente equivalente más pequeño.

Nota: Los autores del artículo original sobre 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 : eligen e y calculan d a partir de él. Dado que e puede ser pequeño y fijo de forma segura, mientras que d debe elegirse de un espacio lo suficientemente grande como para resistir ataques, el enfoque moderno puede reducir el coste de la operación de clave pública sin pérdida de seguridad. ^{[ 3 ] [ 32 ]}

Supongamos que Bob quiere enviar mensajes secretos a Alice o verificar los mensajes de Alice. Si deciden usar RSA, Bob debe conocer la clave pública de Alice para cifrar sus mensajes secretos o verificar los de Alice, y Alice debe usar su clave privada para descifrar los mensajes secretos de Bob o firmar los suyos.

Para que Bob pueda enviar sus mensajes cifrados o verificar los mensajes futuros de Alice, ella le transmite su clave pública ( n , e ) a través de una ruta confiable, pero no necesariamente secreta. La clave privada de Alice ( d ) nunca se distribuye.

Una vez que Bob obtiene la clave pública de Alice, puede enviarle un mensaje M.

Para ello, primero convierte M en un número entero m , el texto plano rellenado , de modo que 0 ≤ m < n , utilizando un protocolo reversible acordado conocido como esquema de relleno . A continuación, calcula el texto cifrado c , utilizando la clave pública e de Alice , mediante:

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

Esto se puede hacer con bastante rapidez, incluso para números muy grandes, usando exponenciación modular . Bob luego transmite c a Alice. Nótese que al menos nueve valores de m producirán un texto cifrado c igual a m , ^{[ b ]} pero es muy improbable que esto ocurra en la práctica.

Alice puede recuperar m a partir de c utilizando su exponente de clave privada d mediante el cálculo

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

Dado m , ella puede recuperar el mensaje original M invirtiendo el esquema de relleno, o descartarlo como corrupto si el relleno no es válido.

Alice debe descartar m si el relleno es inválido: si revela alguna información sobre m cuando tiene un relleno inválido, un adversario podría aprovechar esto para descifrar (o firmar) mensajes sin conocer la clave privada, enviándole textos cifrados aleatorios o diseñados maliciosamente y observando cómo responde. ^{[ 33 ]}

Aquí hay un ejemplo de cifrado y descifrado RSA, ignorando los detalles del relleno: ^{[ c ]}

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

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

2. Calcula n = pq dando

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

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

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

4. Escoge cualquier número 1 < e < 780 que sea coprimo con 780. Si elegimos un número primo para e, solo nos queda comprobar que e no sea divisor de 780.

   Dejar${\displaystyle e=17}$.

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

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

Las implementaciones prácticas utilizan el teorema chino del resto para acelerar el cálculo utilizando el módulo de los factores (mod pq usando 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}}}$$

Aquí 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 adecuados):$${\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 desea enviar un mensaje firmado m a Bob. Ella produce un valor hash h = hash( m ) del mensaje m , lo eleva a la potencia de d (módulo n ) y adjunta s = h ^d mod n como una "firma" al mensaje.

Cuando Bob recibe el mensaje m y la firma s , utiliza el mismo algoritmo hash junto con la clave pública de Alice para calcular h = hash( m ) . Eleva la firma s a la potencia de e (módulo n ) y compara el valor hash resultante con el valor hash del mensaje:$${\displaystyle s^{e}\mathrel {\stackrel {?}{\equiv }} h{\pmod {n}}}$$Si ambos coinciden, él sabe 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 fue enviado.

Esta ecuación se satisface cuando s = h ^d mod n debido a las reglas de exponenciación : $${\displaystyle s^{e}=(h^{d})^{e}=h^{de}=h^{ed}=(h^{e})^{d}\equiv h{\pmod {n}}.}$$

La exponenciación modular para la firma y la verificación se basa en las mismas matemáticas que para el descifrado y el cifrado, pero todos los demás detalles del esquema de relleno para el cifrado seguro de clave pública y el hash para la firma digital segura son diferentes. ^{[ 32 ]}

El uso de un hash, propuesto por primera vez en 1978 por Michael O. Rabin en el algoritmo de firma de Rabin relacionado , ^{[ 34 ] [ 35 ]} y la seguridad del hash, es esencial para la seguridad de la firma: ^{[ 36 ] [ 37 ]} si Alice y Bob omitieran el hash, y Bob verificara s ^e ≡ m (mod n ) en su _{lugar , entonces cualquiera podría} falsificar la firma s = 1 en el mensaje m = 1 , o tomar dos mensajes firmados ( m1 _, s1 ) y ( m2 , _{s2 )} de Alice y luego falsificar un tercero por multiplicación, ₍ m1m2 , s1s2 ) _, sin conocimiento de la clave privada .

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 , que no divida a . ^{[ nota 1 ]}

Queremos demostrar que $${\displaystyle (m^{e})^{d}\equiv m{\pmod {pq}}}$$ 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 )) .

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

Para comprobar si dos números, como m ^ed y m , son congruentes módulo pq  , basta (y de hecho es equivalente) comprobar que son congruentes módulo p  y módulo 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 . Así que m ^ed ≡ 0 ≡ m (mod p ) .
2. Si m ≢ 0 (mod p ) ,

   ${\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 utilizamos 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 ) procede de una manera 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 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 demostración de que, para cualquier entero m y enteros e y 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 demostraciones 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 distintos, y e y d son enteros positivos que satisfacen ed ≡ 1 (mod φ ( n )) . Dado que e y d son positivos, podemos escribir ed = 1 + h φ ( n ) para algún entero no negativo h . Suponiendo que m es coprimo con 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 penúltima congruencia se deduce del teorema de Euler .

De manera más general, para cualquier e y d que satisfagan ed ≡ 1 (mod λ ( n )) , se llega a la misma conclusión a partir de la generalización de Carmichael del teorema de Euler , que establece que m ^{λ (n)} ≡ 1 (mod n ) para todo m relativamente primo a n .

Cuando m no es primo relativo con n , el argumento anterior es inválido. Esto es muy improbable (solo una proporción de los números 1/ p + 1/ q − 1/( pq ) poseen 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 pueden tratarse utilizando la demostración anterior.

Existen varios ataques contra RSA estándar, 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 enteros.
• Si se envía el mismo mensaje en texto plano a e o más destinatarios de forma cifrada, y los receptores comparten el mismo exponente e , pero diferentes p , q y, por lo tanto , n , entonces es fácil descifrar el mensaje original en texto plano mediante el teorema chino del resto . Johan Håstad observó que este ataque es posible incluso si los textos planos no son iguales, pero el atacante conoce una relación lineal entre ellos. ^{[ 38 ]} Este ataque fue mejorado posteriormente por Don Coppersmith (véase el ataque de Coppersmith ). ^{[ 39 ]}
• 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 plano elegido contra el criptosistema, cifrando posibles textos planos con la clave pública y comprobando 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 conoce (o ha elegido) los textos planos correspondientes. RSA sin relleno no es semánticamente seguro. ^{[ 40 ]}
• 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 quiera conocer el descifrado de un texto cifrado c ≡ m ^e (mod n ) puede pedirle al poseedor de la clave privada d que descifre un texto cifrado aparentemente inofensivo 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, conocerá mr (mod n ), a partir del cual puede derivar el mensaje m multiplicando mr por el inverso modular de r módulo n . ^{[ 33 ] [ 41 ]}
• 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 contra una clave pública ( e ', n ). ^{[ 30 ]}  

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

Estándares como PKCS#1 se han diseñado cuidadosamente para rellenar mensajes de forma segura antes del cifrado RSA. Dado que estos esquemas rellenan el texto plano m con una cierta cantidad de bits adicionales, el tamaño del mensaje sin rellenar M debe ser algo menor. Los esquemas de relleno RSA deben diseñarse cuidadosamente para prevenir ataques sofisticados que podrían 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 aparentemente hacía que RSA fuera semánticamente seguro. Sin embargo, en Crypto 1998, Bleichenbacher demostró que esta versión es vulnerable a un ataque práctico adaptativo de texto cifrado elegido . Además, en Eurocrypt 2000, Coron et al. ^{[ 42 ]} demostraron que, para algunos tipos de mensajes, este relleno no proporciona un nivel de seguridad suficientemente alto. Las versiones posteriores del estándar incluyen el Relleno de Cifrado Asimétrico Óptimo (OAEP), que previene estos ataques. Por lo tanto, se recomienda utilizar OAEP en cualquier aplicación nueva y  reemplazar el relleno 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, como 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 para su cifrado. 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 limitado por patentes. Cabe señalar que el uso de diferentes pares de claves RSA para el cifrado y la firma es potencialmente más seguro. ^{[ 43 ]}

Para 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 chino del resto . ^{[ 44 ]} Los siguientes valores se precalculan y almacenan como parte de la clave privada:

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

Esto resulta más eficiente que calcular la exponenciación elevando al cuadrado , aunque se deban calcular dos exponenciaciones modulares. La razón es que ambas exponenciaciones modulares utilizan un exponente y un módulo menores.

La seguridad del criptosistema RSA se basa en dos problemas matemáticos: el problema de factorizar números grandes y el problema RSA . Se considera que el descifrado completo de un texto cifrado RSA es inviable, dado 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 . ^{[ 45 ]}

El problema RSA se define como la tarea de tomar e -ésimas raíces módulo un número 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 ) , y luego descifrar c usando el procedimiento estándar. Para lograr esto, un atacante factoriza n en p y q , y calcula mcm( p -1, q -1) que permite determinar d a partir de e . Aún no se ha encontrado ningún método de tiempo polinomial para factorizar grandes enteros en una computadora clásica, pero no se ha demostrado que no exista ninguno; consulte factorización de enteros para una discusión de este problema.

La primera factorización RSA-512 en 1999 utilizó cientos de computadoras y requirió el equivalente a 8400 años MIPS, en un tiempo transcurrido de aproximadamente siete meses. ^{[ 46 ]} Para 2009, Benjamin Moody podía factorizar una clave RSA de 512 bits en 73 días utilizando solo software público (GGNFS) y su computadora de escritorio (un Athlon64 de doble núcleo con una CPU de 1900 MHz). Se requirieron  poco menos de 5 gigabytes de almacenamiento en disco y alrededor de 2,5 gigabytes de RAM para el proceso de cribado.  

Rivest, Shamir y Adleman señalaron ^{[ 3 ]} que Miller ha demostrado que, asumiendo la veracidad 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 (salvo una diferencia de tiempo polinomial). ^{[ 47 ]} 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 sea tan difícil como factorizar.

A partir de 2020, el número RSA factorizado más grande conocido públicamente tenía 829  bits (250 dígitos decimales, RSA-250 ). ^{[ 48 ]} 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 una longitud de 1024 a 4096 bits. En 2003, RSA Security estimó que las claves de 1024 bits probablemente se volverían descifrables para 2010. ^{[ 49 ]} A partir de 2020, no se sabe si tales claves pueden descifrarse, pero las recomendaciones mínimas han pasado a al menos 2048  bits. ^{[ 50 ]} Generalmente se presume que RSA es seguro si n es 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 un ordenador personal , utilizando software ya disponible gratuitamente. Se ha demostrado que las claves de 512 bits son prácticamente vulnerables desde 1999, cuando se factorizó RSA-155 utilizando varios cientos de ordenadores, y ahora se factorizan en unas pocas semanas utilizando hardware común. En 2011 se informaron exploits que utilizaban certificados de firma de código de 512 bits que podrían haber sido factorizados. ^{[ 51 ]} 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. ^{[ 49 ]}  

En 1994, Peter Shor demostró que una computadora cuántica , si alguna vez se pudiera crear una de manera práctica para ese propósito, sería capaz de factorizar en tiempo polinomial , rompiendo RSA; véase el algoritmo de Shor .

La búsqueda de los números primos grandes p y q generalmente se realiza probando números aleatorios del tamaño correcto con pruebas de primalidad probabilísticas que eliminan rápidamente casi todos los números no primos.

Los números p y q no deben estar "demasiado cerca", 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 para p y q es trivial. Además, si p − 1 o q − 1 tienen solo factores primos pequeños, n se puede factorizar rápidamente mediante 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 suficientemente grande. Michael J. Wiener demostró que si p está entre q y 2q (lo cual es bastante típico) y d < n ^1/4 /3 , entonces d se puede calcular eficientemente a partir de n y e . ^{[ 52 ]} 

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 en ataques a RSA, especialmente si el exponente público e es pequeño y si el mensaje cifrado es corto y no tiene relleno. 65537 es un valor comúnmente utilizado para e ; este valor puede considerarse un compromiso entre evitar posibles ataques de exponentes pequeños y 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 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 un gran número de tarjetas inteligentes y módulos de plataforma segura (TPM) estaban afectados. Las claves RSA vulnerables se identifican fácilmente mediante un programa de prueba publicado por el equipo. ^{[ 53 ]}

Para generar los números primos p y q , se debe utilizar un generador de números aleatorios criptográficamente robusto , debidamente inicializado 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 comparativo de millones de claves públicas recopiladas de Internet . Lograron factorizar el 0,2 % de las claves utilizando únicamente el algoritmo de Euclides. ^{[ 54 ] [ 55 ]}   

Explotaron una vulnerabilidad exclusiva de los criptosistemas basados ​​en la factorización de 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 cálculo simple de mcd( n , n ′) = p factoriza tanto n como n ', comprometiendo totalmente ambas claves. Lenstra et al. señalan que este problema puede minimizarse utilizando una semilla aleatoria robusta con una longitud de bits que duplica el nivel de seguridad previsto, o empleando una función determinista para elegir q dado p , en lugar de elegir p y q de forma independiente.

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 contra 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 división grande, el problema del MCD tiene un tamaño normal.

Heninger afirma en su blog que las teclas defectuosas se produjeron casi exclusivamente en aplicaciones integradas, incluyendo «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, se debe a situaciones en las que el generador de números pseudoaleatorios se inicializa con una semilla deficiente y luego se reinicializa entre la generación del primer y el segundo número primo. El uso de semillas con una entropía suficientemente alta, obtenidas a partir de la temporización de las pulsaciones de teclas, el ruido de los diodos electrónicos o el ruido atmosférico de un receptor de radio sintonizado entre estaciones, debería solucionar el problema. ^{[ 56 ]}

La generación de números aleatorios robustos es fundamental 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 distribuidas por RSA, un intruso podría eludir RSA y adivinar directamente las claves simétricas.

Kocher describió un nuevo ataque contra RSA en 1995: si la atacante Eve conoce el hardware de Alice con suficiente detalle y puede medir los tiempos de descifrado para varios textos cifrados conocidos, Eve puede deducir rápidamente la clave de descifrado d . 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)). ^{[ 57 ]} Este ataque aprovecha la información filtrada por la optimización del teorema chino del resto utilizada por muchas implementaciones de RSA.

Una forma de frustrar estos ataques es asegurar que la operación de descifrado tome un 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 enmascaramiento criptográfico . El enmascaramiento RSA aprovecha 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 ) , por lo que el efecto de r se puede eliminar multiplicando por su inverso. Se elige un nuevo valor de r para cada texto cifrado. Con el enmascaramiento aplicado, el tiempo de descifrado ya no está correlacionado con el valor del texto cifrado de entrada, por lo que el ataque de temporización falla.

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 añade estructura a un mensaje cifrado con RSA, lo que permite determinar si un mensaje descifrado es válido). Debido a fallos en el esquema PKCS #1, Bleichenbacher pudo realizar un ataque práctico contra las implementaciones RSA del protocolo Secure Sockets Layer y recuperar las claves de sesión. Como resultado de este trabajo, los criptógrafos recomiendan ahora el uso de esquemas de relleno con seguridad demostrable, como el Relleno de Cifrado Asimétrico Óptimo , y RSA Laboratories ha publicado nuevas versiones de PKCS #1 que no son vulnerables a estos ataques.  

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

Se ha descrito un ataque de canal lateral mediante análisis de predicción de bifurcaciones (BPA). Muchos procesadores utilizan un predictor de bifurcaciones para determinar si es probable que se ejecute una bifurcación condicional en el flujo de instrucciones de un programa. A menudo, estos procesadores también implementan multihilo simultáneo (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 Simple de Predicción de Ramas (SBPA) afirma mejorar el BPA de una manera no estadística. En su artículo, "Sobre el poder del Análisis Simple de Predicción de Ramas" ^{[ 60 ]} , 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 de fallo de alimentación en implementaciones de RSA. ^{[ 61 ]} El autor recuperó la clave variando el voltaje de alimentación de la CPU fuera de los límites; esto provocó múltiples fallos de alimentación en el servidor.

La implementación de CRT es sensible a los ataques de inyección de fallos . Si un atacante puede obtener una firma defectuosa, se puede calcular la clave privada. ^{[ 62 ]}

Hay muchos detalles que tener en cuenta para implementar RSA de forma segura ( un generador de números pseudoaleatorios robusto , un exponente público aceptable, etc.). Esto hace que la implementación sea compleja, hasta el punto de que el libro Criptografía práctica con Go sugiere evitar RSA si es posible. ^{[ 63 ]}