RSA (cryptosystem) (Español)

Usando el algoritmo chino del resto

para la eficiencia muchas bibliotecas criptográficas populares (como OpenSSL, Java y.NET) utilizan la siguiente optimización para descifrar y firmar basado en el teorema chino del resto. Los siguientes valores son precalculados y almacenados como parte de la Clave Privada:

estos valores permiten al receptor calcular la exponenciación M = cd (mod pq) de manera más eficiente de la siguiente manera:

esto es más eficiente que calcular la exponenciación por cuadratura a pesar de que dos exponenciaciones modulares tienen que ser calculadas., La razón es que estas dos exponenciaciones modulares utilizan un exponente más pequeño y un módulo más pequeño.

Integer factorization and RSA problemEdit

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

el problema RSA se define como la tarea de tomar ETH roots modulo a composite n: recuperar un valor M tal que c me me (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 A partir de una Clave Pública (n, e), luego descifrar c utilizando el procedimiento estándar., Para lograr esto, un atacante factoriza n en p y q, y calcula 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 polinómico para factorizar enteros grandes en una computadora clásica, pero no se ha demostrado que ninguno exista. Vea la factorización de enteros para una discusión de este problema.

El tamiz cuadrático polinómico múltiple (MPQS) se puede utilizar 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 MIPS años, durante un tiempo transcurrido de aproximadamente siete meses. En 2009, Benjamin Moody pudo factorizar una clave de bits RSA-512 en 73 días utilizando solo software público (ggnfs) y su computadora de escritorio (un Athlon64 de doble núcleo con una cpu de 1.900 MHz). Se requirió menos de cinco gigabytes de almacenamiento en disco y aproximadamente 2.5 gigabytes de RAM para el proceso de tamizado.,

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

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

si n es de 300 bits o menos, se puede factorizar en unas pocas horas en una computadora personal, utilizando software ya disponible de forma gratuita., Las claves de 512 bits han demostrado ser prácticamente rompibles en 1999 cuando RSA-155 se factorizó mediante el uso de varios cientos de computadoras, y estos ahora se factorizan en unas pocas semanas utilizando hardware común. Los Exploits que utilizan certificados de firma de código de 512 bits que pueden haber sido factorizados se informaron en 2011. Un dispositivo de hardware teórico llamado TWIRL, descrito por Shamir y Tromer en 2003, cuestionó la seguridad de las claves de 1024 bits.,

en 1994, Peter Shor mostró que una computadora cuántica – si alguna vez se pudiera crear prácticamente para el propósito-sería capaz de factorizar el tiempo polinómico, rompiendo RSA; véase el algoritmo de Shor.

generación de claves Defectuosaeditar

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

los números P y q no deben estar «demasiado cerca», no sea que la factorización de Fermat para n sea exitosa., Si p-q es menor que 2n1 / 4 (n = P * q, que incluso para valores pequeños de 1024 bits de n es 3×1077) resolver para P y q es trivial. Además, si p – 1 o q − 1 tienen solo factores primos pequeños, n puede ser factorizado rápidamente por el algoritmo P − 1 de Pollard, y por lo tanto tales valores de P O q deben ser descartados.

es importante que el exponente privado d sea lo suficientemente grande. Michael J. Wiener mostró que si p está entre q y 2Q (lo cual es bastante típico) y d < n1/4/3, entonces d puede calcularse eficientemente a partir de n y e.,

no hay ningún ataque conocido contra exponentes públicos pequeños como e = 3, siempre que se utilice el relleno adecuado. El ataque de Coppersmith tiene muchas aplicaciones para atacar RSA específicamente si el exponente público e es pequeño y si el mensaje cifrado es corto y no acolchado. 65537 es un valor comúnmente utilizado para e; este valor puede ser considerado como un compromiso entre evitar posibles ataques de exponentes pequeños y aún permitir 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 menor que 65537, pero no indica una razón para 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 un gran número de tarjetas inteligentes y módulos de plataforma de confianza (TPMs) estaban afectados. Las claves RSA vulnerables se identifican fácilmente usando un programa de prueba que el equipo lanzó.,

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 se ha sembrado correctamente con entropía adecuada.a principios de 2012, Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung y Christophe Wachter realizaron un análisis comparando millones de claves públicas recogidas de Internet. Fueron capaces de factorizar el 0,2% de las claves usando solo el algoritmo de Euclides.

explotaron una debilidad única de los criptosistemas basada 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 gcd(n, n’) = P factoriza tanto n como n’, comprometiendo totalmente ambas claves. Lenstra et al. tenga en cuenta que este problema se puede minimizar mediante el uso de una semilla aleatoria fuerte de longitud de bits dos veces el nivel de seguridad previsto, o mediante el empleo de una función determinista para elegir q dado p, en lugar de elegir P y q de forma independiente.

Nadia Heninger fue 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 otras claves n’ que habían encontrado (un número de 729 millones de dígitos), en lugar de calcular cada gcd(n,n’) por separado, logrando así una aceleración muy significativa ya que después de una gran división, el problema GCD es de tamaño normal.

Heninger dice en su blog que las malas claves ocurrieron casi en su totalidad 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 tiempos de carrera clave o ruido de diodos electrónicos o ruido atmosférico de un receptor de radio sintonizado entre estaciones debe resolver el problema.

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

ataques de Temporizacióneditar

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 para varios textos cifrados conocidos, Eve puede deducir la clave de descifrado D rápidamente. Este ataque también se puede aplicar contra el esquema de firma RSA., En 2003, Boneh y Brumley demostraron un ataque más práctico capaz de recuperar factorizaciones RSA a través de una conexión de red (por ejemplo, desde un servidor web habilitado para Secure Sockets Layer (SSL)) este ataque aprovecha la información filtrada por la optimización del teorema del resto chino utilizada por muchas implementaciones de RSA.

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

adaptive chosen ciphertext attacksEdit

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

ataques de análisis de canal Sideditar

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

simple Branch Prediction Analysis (SBPA) afirma mejorar el BPA de una manera no estadística. En su artículo, «On the Power of simple Branch Prediction Analysis», los autores de SBPA (Onur Aciicmez y Cetin Kaya Koc) afirman haber descubierto 508 de 512 bits de una clave RSA en 10 iteraciones.

un ataque de falla de energía en implementaciones de RSA fue descrito en 2010., El autor recuperó la clave variando el voltaje de potencia de la CPU fuera de los límites; esto causó múltiples fallas de alimentación en el servidor.