En criptografía , el problema RSA resume la tarea de realizar una operación de clave privada RSA dada únicamente la clave pública . El algoritmo RSA eleva un mensaje a un exponente , módulo un número compuesto N cuyos factores no se conocen. Por lo tanto, la tarea se puede describir claramente como encontrar las raíces e ésimas de un número arbitrario, módulo N. Para tamaños de clave RSA grandes (superiores a 1024 bits), no se conoce ningún método eficiente para resolver este problema; si alguna vez se desarrolla un método eficiente, amenazaría la seguridad actual o futura de los criptosistemas basados en RSA, tanto para el cifrado de clave pública como para las firmas digitales .
Más específicamente, el problema RSA es calcular eficientemente P dada una clave pública RSA ( N , e ) y un texto cifrado C ≡ P e ( mod N ). La estructura de la clave pública RSA requiere que N sea un semiprimo grande (es decir, un producto de dos números primos grandes ), que 2 < e < N , que e sea coprimo a φ ( N ), y que 0 ≤ C < N . C se elige aleatoriamente dentro de ese rango; para especificar el problema con total precisión, también se debe especificar cómo se generan N y e , lo que dependerá de los medios precisos de generación de pares de claves aleatorias RSA en uso.
El método más eficiente conocido para resolver el problema RSA es factorizar primero el módulo N, una tarea que se considera poco práctica si N es suficientemente grande (véase factorización de enteros ). La rutina de configuración de la clave RSA ya convierte el exponente público e , con esta factorización prima, en el exponente privado d , y por lo tanto exactamente el mismo algoritmo permite que cualquiera que factorice N obtenga la clave privada . Cualquier C puede entonces descifrarse con la clave privada.
Así como no hay pruebas de que la factorización de números enteros sea computacionalmente difícil, tampoco hay pruebas de que el problema RSA sea igualmente difícil. Con el método anterior, el problema RSA es al menos tan fácil como la factorización, pero bien podría ser más fácil. De hecho, hay pruebas sólidas que apuntan a esta conclusión: que un método para descifrar el método RSA no puede convertirse necesariamente en un método para factorizar números semiprimos grandes. [1] Esto es quizás más fácil de ver por la exageración del enfoque de factorización: el problema RSA nos pide descifrar un texto cifrado arbitrario, mientras que el método de factorización revela la clave privada: descifrando así todos los textos cifrados arbitrarios, y también permite realizar cifrados RSA de clave privada arbitrarios. En esta misma línea, encontrar el exponente de descifrado d es de hecho computacionalmente equivalente a factorizar N , aunque el problema RSA no pide d . [2]
Además del problema RSA, RSA también tiene una estructura matemática particular que puede potencialmente explotarse sin resolver el problema RSA directamente. Para lograr la máxima solidez del problema RSA, un criptosistema basado en RSA también debe utilizar un esquema de relleno como OAEP para protegerse contra este tipo de problemas estructurales en RSA.