En criptografía, el problema RSA se refiere a la dificultad de efectuar una operación de clave privada mediante el sistema criptográfico RSA conociendo tan solo la clave pública.
Para recuperar este mensaje es necesario elevar de nuevo el resultado a un exponente privado, elegido de tal forma que si no se conoce, hallarlo equivale a factorizar el número
(esto es, hallar los dos números primos cuyo producto es N).
El sistema RSA es la primera propuesta práctica del método criptográfico de clave pública propuesto en 1976 por Whitfield Diffie y Martin Hellman.
Fue presentado en 1977 por Ronald Rivest, Adi Shamir y Leonhard Adleman, del MIT.
Pagarían 100 dólares a quien descifrara un mensaje numérico de 129 cifras decimales publicado en esas mismas páginas junto a su exponente público y módulo.
El problema fue bautizado como RSA-129, y los autores estimaron que harían falta varios millones de años para conseguirlo.
[2] No era la primera vez que se rompía RSA.
Meses después A. K. Lenstra rompió RSA-100, y a este hito le siguieron otros varios en años sucesivos: RSA-110, 120, 130, etc. hasta que el desafío terminó en 2007.
Actualmente no se conoce ningún método general de factorización de enteros y por ello RSA se considera un sistema seguro.
La estructura de la clave pública RSA requiere que
se escoge al azar dentro de dicho rango.
Para describir el problema con precisión, debe también especificarse cómo se generan
) para que sea inviable hallarlos mediante ordenadores convencionales.
El número más grande factorizado hasta la fecha es RSA-768, un número de 232 cifras decimales (con la actual notación binaria) hallado en enero de 2010 mediante la QFS.
[4] Este número está muy por debajo del rango manejado por el algoritmo RSA.
Sin embargo no hay absoluta certeza de que no existan métodos eficientes de factorización, ya sea mediante un nuevo método o una nueva herramienta.
La computación cuántica podría proveer de una solución a este problema.
Por el método descrito anteriormente, el sistema RSA es al menos igual de difícil que factorizar.
Pero podría ser incluso menor, ya que el problema RSA no pide expresamente hallar el exponente privado sino solo descifrar un texto.
Tal como sugieren D. Boneh y R. Venkatesan, entre descifrar un texto concreto y acceder a la clave privada de cualquier texto cifrado, lo que otorga poder no solo para descifrar cualquier mensaje sino para crear nuevos mensajes a voluntad, hay suficiente margen como para que se pueda romper RSA con un método menos ambicioso.
Esto podría explicar que aún no se haya demostrado que romper RSA no es equivalente a factorizar.
[5] Además, RSA posee también una estructura matemática que puede ser explotada sin necesidad de resolver el problema RSA directamente.
Para conseguir una funcionalidad completa, el algoritmo RSA debe incluir un «patrón de relleno» (padding scheme) como OAEP que proteja contra esta debilidad.