RSA (criptosistema)

Algoritmo para criptografía de clave pública

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 británica de inteligencia de señales , 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 secreta (privada). Un usuario de 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 puede descifrarlos alguien que conozca 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 del factoring es una cuestión abierta. ^[3] No existen métodos publicados para derrotar al sistema si se utiliza 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 utiliza para transmitir claves compartidas para criptografía de clave simétrica , que luego se utilizan para cifrado y descifrado masivo.

Historia

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

La idea de un criptosistema asimétrico de clave pública-privada 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 de un número primo. Sin embargo, dejaron abierto el problema de realizar una función unidireccional, posiblemente porque la dificultad de factorizar 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 hicieron varios intentos a lo largo de un año para crear una función 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, incluidos los " polinomios de permutación" y los "basados ​​en 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 casa de un estudiante y bebieron mucho vino antes de regresar a sus casas 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 al amanecer tenía gran parte del documento listo. 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, dados los ordenadores relativamente caros que se necesitaban para implementarlo en ese momento, era Se considera 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 ultrasecreta.

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 proporciona información sobre RSA y otros cifrados de clave pública, de forma análoga al DES simplificado . ^{[9] [10] [11] [12] [13]}

Patentar

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 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. Luego, 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 exponenciado 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 . ^[7] Esto precedió a la fecha de presentación de la patente de diciembre de 1977. En consecuencia, la patente no tenía valor legal fuera de los Estados Unidos . Si el trabajo de Cocks hubiera sido conocido públicamente, una patente en Estados Unidos tampoco habría sido legal.

Cuando se emitió la patente, la duración de la misma era 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. ^[14]

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 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 módulo congruente ): ${\displaystyle (m^{e})^{d}}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n}$

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

end

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

Además, como los dos exponentes se pueden intercambiar , las claves pública y privada también se pueden intercambiar, lo que permite firmar y verificar mensajes utilizando el mismo algoritmo.

Generación de claves

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

1. Elija dos números primos grandes p y q .
   • Para hacer la factorización más difícil, pyq deben elegirse al azar, ser grandes y tener una diferencia grande . ^[1] Para elegirlos, el método estándar es elegir números enteros aleatorios y utilizar una prueba de primalidad hasta que se encuentren dos números primos.
   • pyq deben mantenerse en secreto .
2. Calcular n = pq .
   • n se utiliza como módulo para las claves pública y privada. Su longitud, normalmente expresada en bits, es la longitud de la clave .
   • n se libera como parte de la clave pública.
3. Calcule λ ( n ) , donde λ es la función totiente de Carmichael . Como n = pq , λ ( n ) = lcm ( λ ( p ),  λ ( q )) , y como p y q son primos, λ ( p ) = φ ( p ) = p − 1 , y de la misma manera λ ( q ) = q − 1 . Por tanto λ ( n ) = lcm ( 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 número entero e tal que 1 < e < λ ( n ) y mcd ( e , λ ( n )) = 1 ; es decir, e y λ ( n ) son coprimos .
   • e tener una longitud de bits corta y un peso Hamming pequeño da como resultado un cifrado más eficiente: el valor elegido más comúnmente 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 que un valor tan pequeño para e es menos seguro en algunos entornos. ^[15]
   • e se libera como parte de la clave pública.
5. Determine 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 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 de 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, todos pueden descartarse después de calcular d . ^[dieciséis]

En el artículo original de RSA, ^[1] 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 resulta también del teorema de Lagrange aplicado al grupo multiplicativo de números 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, calcular d módulo φ ( 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 cualquiera de los métodos (si es que usan el exponente privado d , 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 (Sección B.3.1) puede requerir que d < λ ( n ) . Cualquier exponente privado "sobredimensionado" que no cumpla con este criterio siempre se puede reducir en 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 autoeditada? ]} se recomienda que ( p − 1) y ( q − 1) tengan solo factores comunes muy pequeños, si los hay, además del necesario 2. ^{[1] [18] [19] [ verificación fallida ] [20] [ verificación fallida ]}

Nota: Los autores del artículo RSA original 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 , no al revés (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. ^{[1] [21]}

Distribución de claves

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 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 sin formato sin relleno) en un número entero m (estrictamente hablando, el texto sin formato acolchado ), tal que 0 ≤ m < n mediante el uso de un protocolo reversible acordado conocido como relleno. esquema. 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 razonablemente rápido, 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.

Descifrado

Alice puede recuperar m de c usando el exponente de su 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.

Ejemplo

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

1. Elija dos números primos distintos, como

   ${\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 ) = lcm ( p − 1, q − 1) dando

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

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

   Dejar . ${\displaystyle e=17}$

5. Calcule 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 multiplicar al cuadrado para la exponenciación modular . En situaciones de la vida real, 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 gratuitamente) de nuevo a los números 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 utilizan el teorema del resto chino para acelerar el cálculo utilizando el módulo de 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}}}$$

Así es como se usan d _p , d _q y q _inv para un descifrado eficiente (el cifrado es eficiente eligiendo 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}}}$$

Firmar mensajes

Supongamos que Alice usa 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 era de Alice, ya que cualquiera puede usar la clave pública de Bob para enviarle mensajes cifrados. Para verificar el origen de un mensaje, RSA también se puede utilizar para firmar un mensaje.

Supongamos que Alice desea enviar un mensaje firmado a Bob. Puede utilizar su propia clave privada para hacerlo. Ella 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, utiliza 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 cifra 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 alterado desde que fue enviado.

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 tanto, 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 tenga la clave pública (transporte cifrado asimétrico).
2. Cifrar 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

Prueba utilizando el pequeño teorema de Fermat

La prueba de la exactitud 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 mostrar que

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

mpqeded ≡ 1 (mod λ ( pq ))

Dado que λ ( pq ) = lcm ( 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)}$$

hk^{[nota 2]}

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 mostrar m ^ed ≡ m (mod p ) , consideramos dos casos:

1. Si m ≡ 0 (mod p ) , m es múltiplo de p . Por tanto, m ^ed es un múltiplo de p . Entonces m ^ed ≡ 0 ≡ m (mod p ) .
2. Si m 0 (mod p ) ${\displaystyle \not \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 . Entonces m ^ed ≡ 0 ≡ m (mod q ) .
2. Si m 0 (mod q ) ${\displaystyle \not \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 número entero m , y enteros e , d tales que ed ≡ 1 (mod λ ( pq )) ,

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

Notas

1. No podemos romper trivialmente RSA aplicando el teorema (mod pq ) porque pq no es primo.
2. En particular, la afirmación anterior es válida para cualquier e y d que satisfagan ed ≡ 1 (mod ( p − 1)( q − 1)) , ya que ( p − 1)( q − 1) es divisible por λ ( pq ) , y por tanto trivialmente también por p − 1 y q − 1 . Sin embargo, en las implementaciones modernas de RSA, es común usar un exponente privado reducido d que solo satisface la condición más débil, pero suficiente, ed ≡ 1 (mod λ ( pq )) .
3. Esto es parte del teorema del resto chino , aunque no es la parte significativa de ese teorema.

Prueba utilizando el teorema de Euler

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 enteros positivos que satisfacen ed ≡ 1 (mod φ ( n )) . Como e y d son positivos, podemos escribir ed = 1 + hφ ( n ) para algún entero no negativo h . Suponiendo que m es primo relativo de 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 deriva del teorema de Euler .

De manera más general, para cualquier e y d que satisfagan 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 todo m relativamente primo al n .

Cuando m no es primo relativo de n , el argumento que se acaba de dar no es válido. Esto es muy improbable (sólo una proporción de números 1/ p + 1/ q − 1/( pq ) tiene esta propiedad), pero incluso en este caso, la congruencia deseada sigue siendo cierta. Ya sea m ≡ 0 (mod p ) o m ≡ 0 (mod q ) , y estos casos pueden tratarse utilizando la prueba anterior.

Relleno

Ataques contra RSA simple

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

• Cuando se cifra 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 -ésima del texto cifrado sobre los números enteros.
• Si el mismo mensaje de texto claro se envía 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. a través del teorema del resto chino . Johan Håstad advirtió 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 (ver El ataque de Coppersmith ). ^[23]
• Debido a que el cifrado RSA es un algoritmo de cifrado determinista (es decir, no tiene ningún componente aleatorio), un atacante puede lanzar con éxito un ataque de texto sin formato elegido contra el criptosistema, cifrando textos sin formato probables bajo la clave pública y probando si son iguales al texto cifrado. Un criptosistema se denomina semánticamente seguro si un atacante no puede distinguir dos cifrados entre sí, incluso si conoce (o ha elegido) los textos claros correspondientes. 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 claros. Es decir, m ₁ ^mi m ₂ ^mi ≡ ( m ₁ m ₂ ) ^mi (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 de aspecto no sospechoso 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 por el inverso modular de r módulo n . ^{[ cita necesaria ]}
• 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 ). ^[15]

Esquemas de relleno

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

Estándares como PKCS#1 se han diseñado cuidadosamente para rellenar mensajes de forma segura antes del cifrado RSA. Debido a que estos esquemas rellenan el texto plano m con algún número de bits adicionales, el tamaño del mensaje sin relleno M 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 suficientemente alto. Las versiones posteriores del estándar incluyen el relleno de cifrado asimétrico óptimo (OAEP), que previene 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 proporcionar seguridad adicional para las firmas RSA, por ejemplo, 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 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 patentes. ^{[ ¿investigacion original? ]} Tenga en cuenta que utilizar diferentes pares de claves RSA para cifrar y firmar es potencialmente más seguro. ^[26]

Seguridad y consideraciones prácticas.

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 . ^{[ cita necesaria ]} Los siguientes valores se calculan previamente y se almacenan como parte de la clave privada:

• ${\displaystyle p}$y  – los números primos de la generación clave, ${\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.

Factorización de enteros y el 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 bajo el supuesto de que ambos problemas son difíciles , es decir, que no existe ningún algoritmo eficiente para resolverlos. Proporcionar seguridad contra el descifrado parcial puede requerir la adición de un esquema de relleno seguro . ^[27]

El problema RSA se define como la tarea de tomar e th raíces módulo a n compuesto : recuperar un valor m tal que c ≡ m ^e (mod n ) , donde ( n , e ) es una clave pública RSA y c es una clave RSA. texto cifrado. 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 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 . Aún 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 exista ninguno; consulte factorización de números enteros para una discusión de este problema.

Se puede utilizar una criba cuadrática polinomial múltiple (MPQS) para factorizar el módulo público n .

La primera factorización RSA-512 en 1999 utilizó cientos de computadoras y requirió el equivalente a 8.400 años MIPS, durante un tiempo transcurrido de aproximadamente siete meses. ^{[28] 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 computadora de escritorio (un} Athlon64 de doble núcleo con una CPU de 1.900 MHz). Para el proceso de tamizado se necesitaron poco menos de 5 gigabytes de almacenamiento en disco y unos 2,5 gigabytes de RAM.

Rivest, Shamir y Adleman señalaron ^[1] que Miller ha demostrado que, asumiendo la verdad de la hipótesis de Riemann ampliada , 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). ^[29] 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^[update] factorizado más grande conocido públicamente tenía 829 bits (250 dígitos decimales, RSA-250 ). ^[30] Su factorización, mediante una implementación distribuida de última generación, tomó alrededor de 2.700 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 en 2010. ^[31] A partir de 2020, no se sabe si dichas claves se pueden descifrar, pero las recomendaciones mínimas se han movido a al menos 2048 bits. ^[32] Generalmente se supone 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 una computadora personal , utilizando software que ya está disponible gratuitamente. 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 utilizan certificados de firma de código de 512 bits que pueden haber sido factorizados. ^[33] 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. ^[31]

En 1994, Peter Shor demostró que una computadora cuántica (si es que alguna vez se pudiera crear una para ese propósito) sería capaz de factorizar el tiempo polinómico , rompiendo el RSA; ver algoritmo de Shor .

Generación de clave defectuosa

Para encontrar los primos grandes p y q generalmente se prueban números aleatorios del tamaño correcto con pruebas de primalidad probabilísticas que eliminan rápidamente prácticamente todos los 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 n de 1024 bits es3 × 10 ⁷⁷ ), resolver p y q es trivial. Además, si p − 1 o q − 1 tienen sólo factores primos pequeños, n puede factorizarse rápidamente mediante el algoritmo p − 1 de Pollard y, por 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 (lo cual es bastante típico) y d < n ^1/4/3 , entonces d se puede calcular eficientemente a partir de n y  e . ^[34]

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 está relleno. 65537 es un valor comúnmente utilizado para  e ; este valor puede considerarse como un compromiso entre evitar posibles ataques de pequeño exponente 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 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 incorporado en una biblioteca de Infineon conocida como RSALib. Se demostró que una gran cantidad de tarjetas inteligentes y módulos de plataforma confiable (TPM) estaban afectados. Las claves RSA vulnerables se identifican fácilmente mediante un programa de prueba que lanzó el equipo. ^[35]

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

Para generar los números primos p y q se debe utilizar un generador de números aleatorios criptográficamente fuerte , que haya sido adecuadamente 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 llevaron a cabo un análisis comparando millones de claves públicas recopiladas de Internet . Pudieron factorizar el 0,2% de las claves utilizando únicamente el algoritmo de Euclides. ^{[36] [37] [ ¿ fuente autoeditada? ]}

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. tenga en cuenta que este problema se puede minimizar utilizando una semilla aleatoria fuerte de longitud de bits dos veces 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 hizo un experimento similar. Usaron una idea de Daniel J. Bernstein para calcular el MCD de cada clave RSA n contra el producto de todas las otras 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 tiene un tamaño normal.

Heninger dice en su blog que las claves defectuosas ocurrieron casi en su totalidad en aplicaciones integradas, incluidos "firewalls, 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 primo compartido descubierto por los dos grupos resulta de situaciones en las que el generador de números pseudoaleatorios está mal sembrado inicialmente y luego se vuelve a sembrar entre la generación del primer y segundo primo. El problema debería resolverse utilizando semillas de entropía suficientemente alta obtenidas de tiempos de pulsación de teclas o ruido de diodos electrónicos o ruido atmosférico de un receptor de radio sintonizado entre estaciones. ^[38]

La generación sólida de números aleatorios 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 distribuye RSA, entonces un espía podría pasar por alto RSA y adivinar las claves simétricas directamente.

Ataques de tiempo

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 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). ^[39] Este ataque aprovecha la información filtrada por la optimización del teorema del resto chino utilizado por muchas implementaciones de RSA.

Una forma de frustrar estos ataques es garantizar que la operación de descifrado demore una cantidad constante de tiempo 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 utiliza 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 puede eliminarse 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, por lo que el ataque de sincronización falla.

Ataques adaptativos de texto cifrado elegido

En 1998, Daniel Bleichenbacher describió el primer ataque práctico de texto cifrado elegido adaptativo 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 demostrablemente seguros, como Optimal Ametric 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", volvió en 2014. ^{[40] [41]} Afectó a la biblioteca criptográfica NSS de Mozilla, que fue utilizada principalmente por Firefox y Chrome.

Ataques de análisis de canal lateral

Se ha descrito un ataque de canal lateral que utiliza análisis de predicción de ramas (BPA). Muchos procesadores utilizan un predictor de bifurcación para determinar si es probable que se realice 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 ramas 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 Rama Simple (SBPA) pretende mejorar el BPA de forma no estadística. En su artículo, "Sobre el poder del análisis de predicción de rama simple", ^[42] los autores de SBPA (Onur Aciicmez y Cetin Kaya Koc) afirman haber descubierto 508 de 512 bits de una clave RSA en 10 iteraciones.

En 2010 se describió un ataque por falla de energía en implementaciones RSA. ^{[43] [ fuente autoeditada? ]} El autor recuperó la clave variando el voltaje de alimentación de la CPU fuera de los límites; esto provocó 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 fuerte , exponente público aceptable, etc.). Esto hace que la implementación sea un desafío, hasta el punto que el libro Practical Cryptography With Go sugiere evitar RSA si es posible. ^[44]

Implementaciones

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

• botánico
• Castillo inflable
• criptolib
• Cripto++
• Libgcrypt
• Ortiga
• AbiertoSSL
• loboCripta
• GnuTLS
• TLS mbed
• libreSSL

Ver también

• Portal de matemáticas

• 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 llaves
• Gestión de claves
• Tamaño de clave
• Criptografía de clave pública
• Criptosistema Rabin
• Función de trampilla

Notas

1. Es decir, los valores de m que son iguales a −1, 0 o 1 módulo p y también iguales a −1, 0 o 1 módulo q . Habrá más valores de m teniendo c = m si p  − 1 o q  − 1 tienen otros divisores en común con e  − 1 además de 2 porque esto da más valores de m tales que o respectivamente. ${\displaystyle m^{e-1}{\bmod {p}}=1}$ ${\displaystyle m^{e-1}{\bmod {q}}=1}$
2. 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.
3. Si , entonces algunas bibliotecas ^{[ se necesita aclaración ]} calculan h como . ${\displaystyle m_{1}<m_{2}}$ ${\displaystyle q_{\text{inv}}\left[\left(m_{1}+\left\lceil {\frac {q}{p}}\right\rceil p\right)-m_{2}\right]{\pmod {p}}}$

Referencias

1. Rivest, R.; Shamir, A.; Adleman, L. (febrero de 1978). "Un método para la obtención de firmas digitales y criptosistemas de clave pública" (PDF) . Comunicaciones de la ACM . 21 (2): 120–126. CiteSeerX  10.1.1.607.2677 . doi :10.1145/359340.359342. S2CID  2873616. Archivado desde el original (PDF) el 27 de enero de 2023.
2. Inteligente, Nigel (19 de febrero de 2008). "Dr. Clifford Cocks CB". Universidad de Bristol . Consultado el 14 de agosto de 2011 .
3. Castelvecchi, Davide (30 de octubre de 2020). "El pionero de la computación cuántica advierte sobre la complacencia con respecto a la seguridad de Internet". Naturaleza . 587 (7833): 189. Bibcode :2020Natur.587..189C. doi :10.1038/d41586-020-03068-9. PMID  33139910. S2CID  226243008.Entrevista 2020 de Peter Shor .
4. Diffie, W.; Hellman, ME (noviembre de 1976). "Nuevas direcciones en criptografía". Transacciones IEEE sobre teoría de la información . 22 (6): 644–654. CiteSeerX 10.1.1.37.9720 . doi :10.1109/TIT.1976.1055638. ISSN  0018-9448. 
5. Rivest, Ronald. "Los primeros días de RSA: historia y lecciones" (PDF) .
6. Calderbank, Michael (20 de agosto de 2007). "El criptosistema RSA: historia, algoritmo, números primos" (PDF) .
7. Robinson, Sara (junio de 2003). "Aún guardando secretos después de años de ataques, RSA obtiene elogios para sus fundadores" (PDF) . Noticias SIAM . 36 (5).
8. Pollas, CC (20 de noviembre de 1973). "Una nota sobre el cifrado no secreto" (PDF) . www.gchq.gov.uk. ​Archivado desde el original (PDF) el 28 de septiembre de 2018 . Consultado el 30 de mayo de 2017 .
9. Jim Sauerberg. "De cifrados de clave privada a pública en tres sencillos pasos".
10. Margaret Cozzens y Steven J. Miller. "Las matemáticas del cifrado: una introducción elemental". pag. 180.
11. Alasdair McAndrew. "Introducción a la criptografía con software de código abierto". pag. 12.
12. Surender R. Chiluka. "Criptografía de clave pública".
13. Neal Koblitz. "La criptografía como herramienta de enseñanza". Criptología, vol. 21, núm. 4 (1997).
14. "RSA Security lanza el algoritmo de cifrado RSA al dominio público". Archivado desde el original el 21 de junio de 2007 . Consultado el 3 de marzo de 2010 .
15. Boneh, Dan (1999). "Veinte años de ataques al criptosistema RSA". Avisos de la Sociedad Matemática Estadounidense . 46 (2): 203–213.
16. Criptografía aplicada, John Wiley & Sons, Nueva York, 1996. Bruce Schneier , p. 467.
17. McKee, James; Pellizco, Richard (1998). "Más ataques a criptosistemas RSA asistidos por servidor". CiteSeerX 10.1.1.33.1333 . 
18. Un curso de teoría de números y criptografía, textos de posgrado en matemáticas. No. 114, Springer-Verlag, Nueva York, 1987. Neal Koblitz , Segunda edición, 1994. p. 94.
19. Dukhovni, Viktor (31 de julio de 2015). "factores comunes en (p - 1) y (q - 1)". openssl-dev (lista de correo).
20. Dukhovni, Viktor (1 de agosto de 2015). "factores comunes en (p - 1) y (q - 1)". openssl-dev (lista de correo).
21. Johnson, J.; Kaliski, B. (febrero de 2003). Estándares de criptografía de clave pública (PKCS) n.º 1: Especificaciones de criptografía RSA Versión 2.1. Grupo de Trabajo de Red. doi : 10.17487/RFC3447 . RFC 3447 . Consultado el 9 de marzo de 2016 .
22. Håstad, Johan (1986). "Sobre el uso de RSA con exponente bajo en una red de clave pública". Avances en criptología: actas de CRYPTO '85 . Apuntes de conferencias sobre informática. vol. 218, págs. 403–408. doi :10.1007/3-540-39799-X_29. ISBN 978-3-540-16463-0.
23. Calderero, Don (1997). "Pequeñas soluciones para ecuaciones polinómicas y vulnerabilidades RSA de bajo exponente" (PDF) . Revista de criptología . 10 (4): 233–260. CiteSeerX 10.1.1.298.4806 . doi :10.1007/s001459900030. S2CID  15726802. 
24. Goldwasser, Shafi ; Micali, Silvio (5 de mayo de 1982). "Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial". Actas del decimocuarto simposio anual de ACM sobre teoría de la informática - STOC '82 . Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 365–377. doi : 10.1145/800070.802212. ISBN 978-0-89791-070-5. S2CID  10316867.
25. Corón, Jean-Sébastien; Joye, Marc; Naccache, David; Paillier, Pascal (2000). "Nuevos ataques al cifrado PKCS#1 v1.5". En Preneel, Bart (ed.). Avances en criptología - EUROCRYPT 2000 . Apuntes de conferencias sobre informática. vol. 1807. Berlín, Heidelberg: Springer. págs. 369–381. doi : 10.1007/3-540-45539-6_25 . ISBN 978-3-540-45539-4.
26. "Algoritmo RSA".
27. Machie, Edmond K. (29 de marzo de 2013). Ataque de rastreo de seguridad de red y reacción en la red del Departamento de Defensa de los Estados Unidos. Trafford. pag. 167.ISBN​ 978-1466985742.
28. Lenstra, Arjen; et al. (Grupo) (2000). "Factorización de un módulo RSA de 512 bits" (PDF) . Eurocripta.
29. Molinero, Gary L. (1975). "Hipótesis y pruebas de primalidad de Riemann" (PDF) . Actas del Séptimo Simposio Anual ACM sobre Teoría de la Computación . págs. 234-239.
30. Zimmermann, Paul (28 de febrero de 2020). "Factorización de RSA-250". Cado-nfs-discutir. Archivado desde el original el 28 de febrero de 2020 . Consultado el 12 de julio de 2020 .
31. Kaliski, Burt (6 de mayo de 2003). "Tamaño de clave TWIRL y RSA". Laboratorios RSA . Archivado desde el original el 17 de abril de 2017 . Consultado el 24 de noviembre de 2017 .
32. Ladrador, Elaine; Dang, Quynh (22 de enero de 2015). "Publicación especial del NIST 800-57 Parte 3 Revisión 1: Recomendación para la administración de claves: Guía de administración de claves específicas de la aplicación" (PDF) . Instituto Nacional de Estándares y Tecnología . pag. 12. doi : 10.6028/NIST.SP.800-57pt3r1 . Consultado el 24 de noviembre de 2017 .
33. Sandee, Michael (21 de noviembre de 2011). "Se abusa de los certificados RSA-512 en la naturaleza". Blog internacional de Fox-IT .
34. Wiener, Michael J. (mayo de 1990). "Criptoanálisis de exponentes secretos RSA cortos" (PDF) . Transacciones IEEE sobre teoría de la información . 36 (3): 553–558. doi : 10.1109/18.54902. S2CID  7120331.
35. Nemec, Matus; Sistema, Marek; Svenda, Petr; Klinec, Dusan; Matyas, Vashek (noviembre de 2017). "El regreso del ataque del calderero: factorización práctica de módulos RSA ampliamente utilizados" (PDF) . Actas de la Conferencia ACM SIGSAC 2017 sobre seguridad informática y de las comunicaciones . CCS '17. doi :10.1145/3133956.3133969.
36. Markoff, John (14 de febrero de 2012). "Defecto encontrado en un método de cifrado en línea". Los New York Times .
37. Lenstra, Arjen K.; Hughes, James P.; Augier, Maxime; Bos, Joppe W.; Kleinjung, Thorsten; Wachter, Christophe (2012). "Ron estaba equivocado, Whit tiene razón" (PDF) .
38. Heninger, Nadia (15 de febrero de 2012). "Nueva investigación: no hay necesidad de entrar en pánico por las claves factorizables, solo tenga en cuenta sus P y Q". Libertad para jugar .
39. Brumley, David; Boneh, Dan (2003). "Los ataques de sincronización remota son prácticos" (PDF) . Actas de la 12.ª Conferencia sobre el Simposio de seguridad USENIX . SSYM'03.
40. "'El error BERserk descubierto en la biblioteca criptográfica NSS de Mozilla afecta a Firefox y Chrome ". 25 de septiembre de 2014 . Consultado el 4 de enero de 2022 .
41. "Falsificación de firma RSA en NSS". Mozilla .
42. Acıiçmez, Onur; Koç, Çetin Kaya; Seifert, Jean-Pierre (2007). "Sobre el poder del análisis de predicción de ramas simples". Actas del 2º Simposio ACM sobre seguridad de la información, la informática y las comunicaciones . ASIACCS '07. págs. 312–320. CiteSeerX 10.1.1.80.1438 . doi :10.1145/1229285.1266999. 
43. Pellegrini, Andrea; Bertacco, Valeria; Austin, Todd (2010). "Ataque basado en fallos de autenticación RSA" (PDF) .
44. Isom, Kyle. "Criptografía práctica con Go" . Consultado el 4 de enero de 2022 .

Otras lecturas

• Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (octubre de 1996). Manual de criptografía aplicada . Prensa CRC. 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.

enlaces externos

• La patente RSA original 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 estadounidense 4.405.829 .
• PKCS #1: Estándar de criptografía RSA ( sitio web de RSA Laboratories )
  • El estándar PKCS #1 "proporciona recomendaciones para la implementación de criptografía de clave pública basada en el algoritmo RSA , cubriendo los siguientes aspectos: primitivas criptográficas ; esquemas de cifrado ; esquemas de firma con apéndice; sintaxis ASN.1 para representar claves y para identificar los esquemas. " .
• Explicación de RSA usando lámparas de colores en YouTube
• Repaso completo de RSA
• El escondite de 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 simples
• Ejemplo de una implementación RSA con relleno PKCS#1 (código fuente GPL) Archivado el 22 de julio de 2012 en Wayback Machine.
• Artículo de Kocher sobre ataques de sincronización
• Una explicación animada de RSA con su trasfondo matemático por CrypTool
• Suciedad, James. "Cifrado RSA". Numéfilo . Brady Harán . Archivado desde el original el 6 de octubre de 2018 . Consultado el 13 de abril de 2013 .
• Cómo se utiliza la clave RSA para el cifrado en el mundo real