RSA y factorización de enteros

RSA es el criptosistema de clave pública más conocido, que proporciona cifrado y firmas digitales cuya seguridad se basa en la dificultad de factorizar el producto de dos números primos grandes.

Definition

RSA es un criptosistema de clave pública en el que un módulo público n es el producto de dos números primos secretos; el cifrado eleva el mensaje a un exponente público módulo n, y el descifrado utiliza un exponente privado derivable solo de la factorización de n.

Scope

Este tema cubre el algoritmo RSA —generación de claves, cifrado, descifrado y firma mediante exponenciación modular—, junto con el problema de factorización de enteros en el que se basa, los algoritmos de factorización que lo amenazan y los esquemas de relleno (OAEP, PSS) que hacen que el RSA de libro de texto sea seguro en la práctica. Aborda las recomendaciones sobre el tamaño de las claves y los ataques de implementación, como los ataques de temporización y de fallos. Excluye los esquemas basados en logaritmos discretos y la criptografía de curva elíptica, que se tratan por separado.

Core questions

• ¿Cómo surgen los exponentes públicos y privados de RSA de la estructura de la aritmética modular?
• ¿Por qué la seguridad de RSA depende de la dificultad de factorizar el módulo?
• ¿Qué tan rápido se pueden factorizar enteros grandes y qué implica esto para los tamaños de clave?
• ¿Por qué el RSA de libro de texto es inseguro y cómo lo solucionan los esquemas de relleno como OAEP y PSS?
• ¿Qué ataques a nivel de implementación (temporización, fallos, aleatoriedad débil) amenazan a RSA en la práctica?

Key concepts

• exponenciación modular
• exponentes públicos y privados
• función totiente de Euler y de Carmichael
• problema de factorización
• criba de campo numérico general
• relleno OAEP
• relleno de firma PSS
• tamaño de clave y nivel de seguridad

Key theories

Permutación de puerta trampa RSA

RSA define una permutación unidireccional de puerta trampa: elevar al exponente público módulo n es fácil, pero invertirlo requiere el exponente privado, que solo puede calcularse a partir de la factorización prima de n — la puerta trampa.

Supuesto de factorización y tamaño de clave

La seguridad práctica de RSA sigue a los mejores algoritmos de factorización (actualmente la criba de campo numérico general, subexponencial en la longitud del módulo); resistirlos es la razón por la que el RSA moderno utiliza módulos de 2048 bits o más.

Mechanisms

La generación de claves elige dos números primos grandes aleatorios p y q, establece n = p*q, selecciona un exponente público e coprimo con (p-1)(q-1), y calcula el exponente privado d como el inverso modular de e. El cifrado calcula c = m^e mod n; el descifrado recupera m = c^d mod n. La corrección se deriva del teorema de Euler. La implementación segura envuelve el texto plano en relleno OAEP para el cifrado y utiliza PSS para las firmas, ya que el RSA 'de libro de texto' sin procesar es maleable y determinista.

Clinical relevance

RSA asegura décadas de infraestructura desplegada: certificados de servidor TLS, firma de código, claves SSH, correo electrónico PGP/S-MIME, tarjetas inteligentes y firma de documentos. Aunque los esquemas de curva elíptica son cada vez más preferidos para los nuevos sistemas debido a las claves más pequeñas, RSA sigue siendo omnipresente en los certificados y protocolos heredados, y comprenderlo es esencial para evaluar el riesgo criptográfico en el mundo real.

Evidence & guidelines

RSA está estandarizado en PKCS #1 (RFC 8017), que especifica OAEP y PSS. El NIST (SP 800-57) recomienda un módulo mínimo de 2048 bits, con 3072 bits para niveles de seguridad más altos. Fallos notables (el error de clave débil de Debian, la vulnerabilidad ROCA en la generación de claves de Infineon y la degradación FREAK a RSA de exportación de 512 bits) subrayan la importancia de una correcta generación de claves y tamaños de parámetros.

History

RSA fue publicado en 1977-1978 por Rivest, Shamir y Adleman en el MIT, la primera realización práctica del concepto de clave pública propuesto por Diffie y Hellman. (Clifford Cocks había descubierto un esquema equivalente en secreto en GCHQ en 1973). Los avances en la factorización —la criba cuadrática y luego la criba de campo numérico en los años 1980-1990— aumentaron progresivamente el tamaño seguro de la clave, y los Desafíos de Factorización RSA siguieron el progreso práctico.

Key figures

• Ronald Rivest
• Adi Shamir
• Leonard Adleman
• Carl Pomerance
• Arjen Lenstra

Seminal works

• rivest1978
• katz2020
• menezes1996

Frequently asked questions

¿Está roto RSA?

Ningún ataque clásico rompe un RSA correctamente implementado con un módulo suficientemente grande (2048 bits o más). Los fallos de RSA en el mundo real se deben a claves demasiado pequeñas, generación de números aleatorios débiles o relleno faltante/incorrecto, no a una ruptura del algoritmo en sí. Sin embargo, una gran computadora cuántica rompería RSA mediante el algoritmo de Shor.

¿Por qué no puedo simplemente cifrar directamente con la función RSA?

El RSA 'de libro de texto' sin procesar es determinista y maleable, lo que filtra información y permite la manipulación del texto cifrado. El uso seguro requiere un relleno aleatorio como OAEP para el cifrado y PSS para las firmas, razón por la cual los estándares exigen estos esquemas.