Problema RSA

Llamemos ${\displaystyle p}$ y ${\displaystyle q}$ a los factores primos de ${\displaystyle N}$, esto es, ${\displaystyle N=pq}$. Buscamos un ${\displaystyle d}$ tal que ${\displaystyle C^{d}\equiv P{\pmod {N}}}$. Por el pequeño teorema de Fermat basta que ${\displaystyle d}$ cumpla ${\displaystyle de\equiv 1{\pmod {\varphi (N)}}}$. Falta conocer ${\displaystyle \varphi (N)}$, pero la única forma de hacerlo es mediante la fórmula ${\displaystyle \varphi (N)=(p-1)(q-1)}$, lo que se traduce en factorizar ${\displaystyle N}$.

El algoritmo RSA está diseñado para escoger primos ${\displaystyle p}$ y ${\displaystyle q}$ suficientemente grandes (del orden de ${\displaystyle 10^{200}}$) para que sea inviable hallarlos mediante ordenadores convencionales. Los métodos más eficientes de factorización de números generales que se conocen son la criba en cuerpos de números (QFS por sus siglas en inglés) y las curvas elípticas. 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.

Así como no hay pruebas de que la factorización de enteros sea computacionalmente difícil, tampoco la hay de que el problema RSA no lo sea. 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.