RSA (criptosistema)

Algoritmo para criptografía de clave pública

Este artículo trata sobre un criptosistema. Para la empresa, consulte Seguridad RSA .

RSA

General
Diseñadores	Ron Rivest , Adi Shamir y Leonard Adleman
Publicado por primera vez	1977
Certificación	PKCS # 1 , ANSI X9.31 , IEEE 1363
Detalle de cifrado
Tamaños de clave	2.048 a 4.096 bits típicos
Rondas	1
Mejor criptoanálisis público
Tamiz de campo numérico general para ordenadores clásicos; Algoritmo de Shor para computadoras cuánticas. Se ha roto una clave de 829 bits .

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

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. Cualquier persona puede cifrar los mensajes a través de la clave pública, pero solo puede decodificarlos alguien que conozca los números primos. ^[2]

La seguridad de RSA se basa en la dificultad práctica de factorizar el producto de dos números primos grandes , el " problema de factorización ". Romper el cifrado RSA se conoce como el problema RSA . Si es tan difícil como el problema de la factorización es una pregunta abierta. ^[3] No existen métodos publicados para anular el 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-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 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]

Ron Rivest , Adi Shamir y Leonard Adleman en el Instituto de Tecnología de Massachusetts , hicieron varios intentos en el transcurso de un año para crear una función unidireccional que era difícil de invertir. Rivest y Shamir, como informáticos, propusieron muchas funciones potenciales, mientras que Adleman, como matemático, fue responsable de encontrar sus debilidades. Probaron muchos enfoques, incluidos " polinomios basados ​​en mochila " y "polinomios de permutación". 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 una buena cantidad de Manischewitz.vino antes de regresar a sus hogares alrededor de la medianoche. ^[6] Rivest, incapaz de dormir, se acostó en el sofá con un libro de texto de matemáticas y comenzó a pensar en su función unidireccional. Pasó el resto de la noche formalizando su idea y tenía gran parte del papel listo para el amanecer. El algoritmo ahora se conoce como RSA: las iniciales de sus apellidos en el mismo orden que su papel. ^[7]

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

Kid-RSA (KRSA) es un cifrado de clave pública simplificado publicado en 1997, diseñado con fines educativos. Algunas personas sienten que aprender Kid-RSA brinda información sobre RSA y otros cifrados de clave pública, análogos a 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 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).

Una descripción detallada del algoritmo fue publicado en agosto de 1977, en la revista Scientific American 's juegos matemáticos columna. ^[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 los Estados Unidos tampoco habría sido legal.

Cuando se emitió la patente, la duración de la patente era de 17 años. La patente estaba a punto de expirar el 21 de septiembre de 2000, cuando RSA Security lanzó el algoritmo al dominio público, el 6 de septiembre de 2000. ^[14]

Operación

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

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

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

y que el conocimiento de correo y n , o incluso m , puede ser extremadamente difícil encontrar d . La barra triple (≡) aquí denota congruencia modular .

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

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

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

Generación de claves

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

1. Elija dos distintos números primos p y q .
   • Por razones de seguridad, los enteros p y q deben ser elegidos al azar, y deben ser similares en magnitud, pero difieren en longitud por unos pocos dígitos para hacer más difícil la factorización. ^{[2] Los} números primos se pueden encontrar de manera eficiente usando una prueba de primalidad .
   • p y q se mantienen en secreto.
2. Calcule 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 . Desde n = pq , λ ( n ) = lcm ( λ ( p ), λ ( q )), y puesto que p y q son primos, λ ( p ) = φ ( p ) = p - 1 y del mismo modo λ ( q ) = q - 1. Por lo tanto, λ ( n ) = lcm (p - 1, q - 1).
   • λ ( n ) se mantiene en secreto.
   • El mcm se puede calcular mediante el algoritmo euclidiano , ya que lcm ( a , b ) = | ab | / mcd ( a , b ).
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 que tiene un corto bit de longitud y pequeñas de peso de Hamming resultados en el 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 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: resuelva para d la ecuación d ⋅ e ≡ 1 (mod λ ( n )) ; d se puede calcular de manera eficiente mediante el uso de la algoritmo de Euclides extendido , ya que, gracias a e y λ ( n ) ser primos entre sí, 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 ny el exponente público (o cifrado) e . La clave privada consta del exponente privado (o descifrado) d , que debe mantenerse en secreto. p , q y λ ( n ) también deben mantenerse en secreto porque se pueden usar para calcular d . De hecho, todos pueden descartarse después de que se haya calculado d . ^[dieciséis]

En el documento de RSA original, ^[2] el Euler función totient φ ( n ) = ( p - 1) ( q - 1) se utiliza en lugar de λ ( n ) para el cálculo del exponente privado d . Dado que φ ( n ) siempre es divisible por λ ( n ), el algoritmo también funciona. El hecho de que se pueda utilizar la función totient de Euler también puede verse como una consecuencia del teorema de Lagrange aplicado al grupo multiplicativo de enteros módulo pq . Por lo tanto, cualquier d satisfactoriod ⋅ 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 usan el exponente privado d en absoluto, en lugar de usar el método de descifrado optimizado basado en el teorema del resto chinose describe a continuación), pero algunos estándares como FIPS 186-4 pueden requerir que d < λ ( n ) . Cualquier exponente privado "sobredimensionado" que no cumpla con ese criterio siempre puede reducirse 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] se recomienda que ( p - 1) y ( q - 1) tengan solo factores comunes muy pequeños, si los hay además de los necesarios 2. ^{[2] [18] [19] [20]}

Nota: Los autores del artículo RSA original llevan a cabo la generación de claves eligiendo dy 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 , lo hacen lo contrario (elija ey calcule d ). Dado que la clave elegida puede ser pequeña, mientras que la clave calculada normalmente no lo es, el algoritmo del papel RSA optimiza el descifrado en comparación con el cifrado, mientras que el algoritmo moderno optimiza el cifrado. ^{[2] [21]}

Distribución de claves

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

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

Cifrado

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

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

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

Esto se puede hacer razonablemente rápido, incluso para números muy grandes, usando exponenciación modular . Bob luego transmite c a Alice.

Descifrado

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

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

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. 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 .

1. Elija dos números primos distintos, como

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

2. Calcule n = pq dando

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

3. Calcule la función totient 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 1 < e <780 que sea coprimo de 780. Elegir un número primo para e nos deja solo para verificar que e no es un divisor de 780.

   Dejar ${\displaystyle e=17}$

5. Calcule d , el inverso multiplicativo modular de e (mod λ ( n )) dando,
   
   $${\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}}\\c(m)&=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}}\\m(c)&=c^{413}{\bmod {3}}233\end{aligned}}}$

Por ejemplo, para cifrar m = 65 , calculamos

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

Para descifrar c = 2790 , calculamos

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

Ambos cálculos se pueden calcular de manera eficiente utilizando el algoritmo de multiplicar y cuadrar para exponenciación modular . En situaciones de la vida real, los números primos seleccionados serían mucho mayores; en nuestro ejemplo sería trivial al factor n , 3233 (obtenido de la clave pública de libre acceso) de nuevo al primos p y q . e , también de la clave pública, se invierte para obtener d , adquiriendo así la clave privada.

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

Los valores d _p , d _q y q _inv , que 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 utilizan d _p , d _q y q _inv para un descifrado eficiente. (El cifrado es eficiente mediante la elección de un adecuado d y e par)

${\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

Suponga que Alice usa la clave pública de Bob para enviarle un mensaje encriptado. En el mensaje, ella puede afirmar que es 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.

Suponga que Alice desea enviar un mensaje firmado a Bob. Puede usar su propia clave privada para hacerlo. Produce un valor hash del mensaje, lo eleva a la potencia de d (módulo n ) (como lo hace al descifrar un mensaje) y lo adjunta como una "firma" al mensaje. Cuando Bob recibe el mensaje firmado, usa el mismo algoritmo hash junto con la clave pública de Alice. Eleva la firma a la potencia de e (módulo n ) (como lo hace cuando encripta un mensaje) y compara el valor hash resultante con el valor hash del mensaje. Si los dos están de acuerdo, él 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 fue enviado.

Esto funciona debido a las reglas de exponenciación :

${\displaystyle h={\text{hash}}(m);}$

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

Por lo 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. Descifre un mensaje destinado únicamente al destinatario, que puede ser cifrado por cualquiera que tenga la clave pública (transporte cifrado asimétrico).
2. Encriptar un mensaje que puede ser desencriptado por cualquier persona, pero que solo puede ser encriptado por una persona; esto proporciona una firma digital.

Pruebas de corrección

Prueba usando el pequeño teorema de Fermat

La prueba de la exactitud de RSA se basa en el pequeño teorema de Fermat , que indica que un ^{p - 1} ≡ 1 (mod p ) para cualquier entero una y el primer p , no dividiendo una . ^{[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 )) .

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

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

para algunos enteros no negativos h y k . ^{[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 un 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 ) procede 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 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 RSA trivialmente aplicando el teorema (mod pq ) porque pq no es primo.
2. En particular, la declaración anterior se cumple para cualquier e y d que satisfacen ed ≡ 1 (mod ( p - 1) ( q - 1)) , ya que ( p - 1) ( q - 1) es divisible por λ ( pq ) , y así trivialmente también por p - 1 y q - 1 . Sin embargo, en 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 usando 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 cambio en el teorema de Euler .

Queremos mostrar 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 )) . Desde e y d son positivos, podemos escribir ed = 1 + hφ ( n ) para algunos no negativo número entero h . Suponiendo que m es primo 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 sigue del teorema de Euler .

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

Cuando m no es primo con n , el argumento que acabamos de dar no es válido. Esto es muy 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 m ≡ 0 (mod p ) o m ≡ 0 (mod q ) , y estos casos pueden tratarse utilizando la demostración anterior.

Relleno

Ataques contra RSA simple

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

• Cuando se encripta con exponentes de encriptación 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 el correo ª raíz del texto cifrado sobre los números enteros.
• Si se envía el mismo mensaje de texto sin cifrar a e o más destinatarios de forma cifrada, y los receptores comparten el mismo exponente e , pero p , q , y por lo tanto n diferentes , entonces es fácil descifrar el mensaje de texto sin cifrar original a través del Teorema del resto chino . Johan Håstad notó que este ataque es posible incluso si los textos claros no son iguales, pero el atacante conoce una relación lineal entre ellos. ^[22] Este ataque fue posteriormente mejorado por Don Coppersmith (ver 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 sin formato elegido contra el criptosistema, cifrando los posibles textos sin formato 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 el atacante conoce (o ha elegido) los textos sin formato correspondientes. Como se describió anteriormente, 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 sin formato. Eso es 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 saber el descifrado de un texto cifrado c ≡ m ^e (mod n ) puede pedir al titular de la clave privada d que descifre un texto cifrado de aspecto poco sospechoso c ′ ≡ cr^e (mod n )por algún valorrelegido por el atacante. Debido a la propiedad multiplicativac′ 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 mensajemmultiplicandomrcon el inverso modular dermódulon.^{[ cita requerida ]}
• Dado el exponente privado d, uno 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 asegura que m no caiga en el rango de textos planos inseguros, y que un mensaje dado, 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 de forma segura los mensajes antes del cifrado RSA. Debido a que estos esquemas rellenan el texto plano m con cierto número de bits adicionales, el tamaño del mensaje no rellenado M debe ser algo menor. Los esquemas de relleno RSA deben diseñarse cuidadosamente para evitar ataques sofisticados que pueden ser facilitados por una estructura de mensaje predecible. Las primeras versiones del estándar PKCS # 1 (hasta la versión 1.5) usaban una construcción que parece hacer que RSA sea semánticamente seguro. Sin embargo, en Crypto 1998, Bleichenbacher demostró que esta versión es vulnerable a un ataque práctico de texto cifrado adaptable elegido . Además, en Eurocrypt 2000, Coron et al.^[25] mostró que para algunos tipos de mensajes, este relleno no proporciona un nivel de seguridad suficientemente alto. Las versiones posteriores del estándar incluyen Optimal Asymmetric Encryption Padding (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 de EE. UU. Sobre PSS (USPTO 6266771 y USPTO 70360140); sin embargo, estas patentes expiraron el 24 de julio de 2009 y el 25 de abril de 2010, respectivamente. El uso de PSS ya no parece estar gravado por las patentes. ^{[ investigación original? ]} Tenga en cuenta que el uso de diferentes pares de claves RSA para el cifrado y la firma es potencialmente más seguro. ^[26]

Consideraciones prácticas y de seguridad

Usando el algoritmo de resto chino

Para mayor eficiencia, muchas bibliotecas de cifrado populares (como OpenSSL , Java y .NET ) utilizan la siguiente optimización para el descifrado y la firma basada en el teorema del resto chino . 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 de claves,${\displaystyle q}$
• ${\displaystyle d_{P}=d{\pmod {p-1}}}$,
• ${\displaystyle d_{Q}=d{\pmod {q-1}}}$ y
• ${\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:

• ${\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}}}$(si entonces algunas bibliotecas ^{[se necesitan aclaraciones ]} calculan h as )${\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}}}$
• ${\displaystyle m=m_{2}+hq\,{\pmod {p*q}}}$

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

Factorización de enteros y problema de RSA

Consulte también: Desafío de factorización RSA , registros de factorización de enteros y algoritmo de Shor

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 asumiendo 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 . ^[27]

El problema RSA se define como la tarea de tomar e º raíces módulo un compuesto n : la recuperación de un valor de 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 de RSA es factorizar el módulo n . Con la capacidad de recuperar factores primos, un atacante puede calcular el exponente secreto d de una clave pública ( n , e ), luego descifre c usando el procedimiento estándar. Para lograr esto, un atacante factores n en p y q , y calcula lcm ( p - 1, q - 1) que permite la determinación de d 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 la factorización de enteros para una discusión de este problema .

Se puede utilizar un tamiz cuadrático polinomial múltiple (MPQS) para factorizar el módulo público n .

La primera factorización de RSA-512 en 1999 utilizó cientos de computadoras y requirió el equivalente a 8.400 MIPS años, durante un tiempo transcurrido de aproximadamente siete meses. ^[28] Para 2009, Benjamin Moody podría factorizar una clave RSA-512 bit en 73 días usando solo software público (GGNFS) y su computadora de escritorio (una Athlon64 de doble núcleo con una cpu de 1.900 MHz). Se requirieron menos de cinco gigabytes de almacenamiento en disco y alrededor de 2.5 gigabytes de RAM para el proceso de tamizado.

Rivest, Shamir y Adleman observó ^[2] que Miller ha demostrado que - suponiendo la verdad de la extendida hipótesis de Riemann - encontrar d de n y e es tan dura como la factorización n en p y q (hasta una diferencia de tiempo polinómico). ^[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 es tan difícil como factorizar.

A partir de 2020 ^[update], el número RSA factorizado más grande conocido públicamente era de 829 bits (250 dígitos decimales, RSA-250 ). ^[30] Su factorización, mediante una implementación distribuida de última generación, tomó aproximadamente 2700 años de CPU. En la práctica, las claves RSA suelen tener una longitud de 1024 a 4096 bits. En 2003, RSA Security estimó que era probable que las claves de 1024 bits se pudieran descifrar para 2010. ^[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 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 demostró que las claves de 512 bits eran prácticamente rompibles en 1999 cuando RSA-155 se factorizó utilizando varios cientos de computadoras, y ahora se factorizan en unas pocas semanas utilizando 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, cuestionó 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 prácticamente para ese propósito, sería capaz de factorizar el tiempo polinomial , rompiendo RSA; consulte el algoritmo de Shor .

Generación de clave defectuosa

Esta sección necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Buscar fuentes:  criptosistema "RSA"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( octubre de 2017 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

Ver también: Ataque de calderero y Ataque de Wiener

Encontrar el números primos grandes p y q por lo general se realiza mediante pruebas de números aleatorios del tamaño correcto con probabilísticos pruebas de primalidad que eliminan rápidamente la práctica totalidad de los nonprimes.

El número p y q no debe ser "demasiado cerca", no sea que la factorización de Fermat para n tener é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 ⁷⁷ ) Resolviendo para p y q es trivial. Además, si p - 1 o q - 1 tiene solo pequeños factores primos, n puede factorizarse rápidamente mediante el algoritmo p - 1 de Pollard y, por lo tanto, dichos valores de p o q deben descartarse.

Es importante que el exponente privado d sea ​​lo suficientemente grande. Michael J. Wiener mostró que si p es entre q y 2 q (que es bastante típico) y d < n ^1/4 / 3 , a continuación, d puede ser calculado de manera eficiente 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. Coppersmith's Attack tiene muchas aplicaciones para atacar RSA específicamente si el exponente público e es pequeño y si el mensaje encriptado es corto y no relleno. 65537 es un valor comúnmente utilizado para  e ; este valor puede considerarse como un compromiso entre evitar posibles ataques de pequeños exponentes 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 inferiores a 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) se vieron 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

A criptográficamente fuerte generador de números aleatorios , que ha sido correctamente sembrado con entropía adecuada, debe ser utilizado para generar el números primos p y q . A principios de 2012, Arjen K. Lenstra , James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung y Christophe Wachter llevaron a cabo un análisis que compara millones de claves públicas recopiladas de Internet . Pudieron factorizar el 0.2% de las claves usando solo el algoritmo de Euclid. ^{[36] [37]}

Explotaron una debilidad exclusiva de los criptosistemas basados ​​en la factorización de enteros. Si n = pq es una clave pública y n ′ = p ′ q ′ es otra, entonces si por casualidad p = p ′ (pero q no es igual a q ′), entonces un simple cálculo de mcd ( n , n ′) = p factores tanto n como n′, Comprometiendo totalmente ambas claves. Lenstra y col. tenga en cuenta que este problema se puede minimizar mediante el uso de una semilla aleatoria fuerte de longitud de bits dos veces el nivel de seguridad pretendido, o empleando una función determinista para elegir q dado p , en lugar de elegir p y q independientemente.

Nadia Heninger era parte de un grupo que hizo un experimento similar. Usaron una idea de Daniel J. Bernstein para calcular el GCD de cada clave RSA n contra el producto de todas las demás claves n ′ 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 de GCD es de tamaño normal.

Heninger dice en su blog que las claves incorrectas ocurrieron casi por completo en aplicaciones integradas, incluidos "firewalls, enrutadores, dispositivos VPN, dispositivos de administración de servidores remotos, impresoras, proyectores y teléfonos VOIP" de más de 30 fabricantes. Heninger explica que el problema de un primo compartido descubierto por los dos grupos resulta de situaciones en las que el generador de números pseudoaleatorios está mal sembrado inicialmente y luego se vuelve a sembrar entre la generación del primer y segundo primos. El uso de semillas de entropía suficientemente alta obtenidas de los tiempos de pulsación de teclas o el ruido de diodos electrónicos o el ruido atmosférico de un receptor de radio sintonizado entre estaciones debería resolver el problema. ^[38]

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

Ataques de tiempo

Kocher describió un nuevo ataque a RSA en 1995: si 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 para Secure Sockets Layer (SSL)) ^[39] Este ataque aprovecha la información filtrada por el teorema chino del resto. optimización utilizada por muchas implementaciones de RSA.

Una forma de frustrar estos ataques es asegurarse de que la operación de descifrado requiera 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 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 ), 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 cegamiento aplicado, el tiempo de descifrado ya no se correlaciona con el valor del texto cifrado de entrada, por lo que falla el ataque de tiempo.

Ataques adaptativos de texto cifrado elegido

En 1998, Daniel Bleichenbacher describió el primer ataque práctico de texto cifrado adaptable elegido , contra mensajes cifrados con RSA utilizando el esquema de relleno PKCS # 1 v1 (un esquema de relleno aleatoriza y agrega estructura a un mensaje cifrado con RSA, por lo que es posible determinar si el mensaje descifrado es válido). Debido a fallas con 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 comprobables como el relleno de cifrado asimétrico óptimo.y RSA Laboratories ha lanzado nuevas versiones de PKCS # 1 que no son vulnerables a estos ataques.

Ataques de análisis de canal lateral

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

El análisis de predicción de rama simple (SBPA) afirma mejorar el BPA de una manera no estadística. En su artículo, "Sobre el poder del análisis de predicción de rama simple", ^[40] 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. ^[41] 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.

Implementaciones

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

• Botan
• Castillo inflable
• cryptlib
• Cripto ++
• Libgcrypt
• Ortiga
• OpenSSL
• WolfCrypt
• GnuTLS
• mbed TLS
• LibreSSL

Ver también

• Criptoanálisis acústico
• Teoría de la complejidad computacional
• Longitud de la clave criptográfica
• Intercambio de claves Diffie-Hellman
• Intercambio de llaves
• Gestión de claves
• Criptografía de curva elíptica
• Criptografía de clave pública
• Función de trampilla

Referencias

1. Smart, Nigel (19 de febrero de 2008). "Dr. Clifford Cocks CB" . Universidad de Bristol . Consultado el 14 de agosto de 2011 .
2. Rivest, R .; Shamir, A .; Adleman, L. (febrero de 1978). "Un método para obtener 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 .   
3. Casteivecchi, Davide, pionero de la computación cuántica advierte sobre la complacencia en la seguridad de Internet , Nature, entrevista del 30 de octubre de 2020 a 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, primos" (PDF) .
7. Robinson, Sara (junio de 2003). "Aún guardando secretos después de años de ataques, RSA gana elogios para sus fundadores" (PDF) . Noticias SIAM . 36 (5).
8. Cocks, CC (20 de noviembre de 1973). "Una nota sobre el cifrado no secreto" (PDF) . www.gchq.gov.uk . Consultado el 30 de mayo de 2017 .
9. Jim Sauerberg "De cifrado 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. "Criptografía como herramienta didáctica" . Cryptologia, vol. 21, N ° 4 (1997).
14. "RSA Security lanza el algoritmo de cifrado RSA en 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; Pinch, Richard (1998). "Más ataques en 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) # 1: Especificaciones de criptografía RSA Versión 2.1 . Grupo de trabajo en 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 en Ciencias de la Computación. 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 polinomiales 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. S. Goldwasser y S. Micali , Cifrado probabilístico y cómo jugar al póquer mental manteniendo en secreto toda la información parcial , Simposio anual de ACM sobre teoría de la computación, 1982.
25. Coron, Jean-Sébastien; Joye, Marc; Naccache, David; Paillier, Pascal (2000). Preneel, Bart (ed.). "Nuevos ataques al cifrado PKCS # 1 v1.5" . Avances en criptología - EUROCRYPT 2000 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 1807 : 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 reaccione en la red del Departamento de Defensa de los Estados Unidos . pag. 167. ISBN 978-1466985742.
28. Lenstra, Arjen; et al. (Grupo) (2000). "Factorización de un módulo RSA de 512 bits" (PDF) . Eurocrypt.
29. Miller, Gary L. (1975). "Hipótesis de Riemann y pruebas de primalidad" (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-discus.
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. Barker, 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 para aplicaciones específicas" (PDF) . Instituto Nacional de Estándares y Tecnología : 12. doi : 10.6028 / NIST.SP.800-57pt3r1 . Consultado el 24 de noviembre de 2017 .
33. Sandee, Michael (21 de noviembre de 2011). "Certificados RSA-512 abusados ​​en la naturaleza" . Blog de Fox-IT International .
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 .
35. Nemec, Matus; Sys, 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 comunicaciones . CCS '17. doi : 10.1145 / 3133956.3133969 .
36. Markoff, John (14 de febrero de 2012). "Fallo encontrado en un método de cifrado en línea" . The 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 Tinker .
39. Brumley, David; Boneh, Dan (2003). "Los ataques de tiempo remoto son prácticos" (PDF) . Actas de la 12ª Conferencia sobre el Simposio de Seguridad de USENIX . SSYM'03.
40. Acıiçmez, Onur; Koç, Çetin Kaya; Seifert, Jean-Pierre (2007). "Sobre el poder del análisis de predicción de rama simple". Actas del 2º Simposio ACM sobre Seguridad de la Información, Informática y Comunicaciones . ASIACCS '07. págs. 312–320. CiteSeerX 10.1.1.80.1438 . doi : 10.1145 / 1229285.1266999 (inactivo 2021-05-25). 
41. Pellegrini, Andrea; Bertacco, Valeria; Austin, Todd (2010). "Ataque basado en fallas de autenticación RSA" (PDF) .

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. pp.  881 -887. ISBN 978-0-262-03293-3.

enlaces externos

• La patente RSA original presentada por Rivest en la Oficina de Patentes de EE. UU. 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 .
• 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 encriptación ; esquemas de firma con apéndice; sintaxis ASN.1 para representar claves e identificar los esquemas " .
• Explicación de RSA usando lámparas de colores en YouTube
• Recorrido minucioso 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 rama simple
• Ejemplo de una implementación de RSA con relleno PKCS # 1 (código fuente GPL)
• El artículo de Kocher sobre los ataques de tiempo
• Una explicación animada de RSA con su trasfondo matemático por CrypTool
• Grime, James. "Cifrado RSA" . Numberphile . Brady Haran .
• Cómo se usa la clave RSA para el cifrado en el mundo real