De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

En criptografía , el problema RSA resume la tarea de realizar una operación de clave privada RSA dada solo la clave pública . El algoritmo RSA eleva un mensaje a un exponente , módulo a un número compuesto N cuyos factores se desconocen. Por lo tanto, la tarea se puede describir perfectamente como encontrar el correo ª raíces de un número arbitrario, módulo N. Para grandes RSA tamaños de clave(más de 1024 bits), no se conoce ningún método eficaz para resolver este problema; si alguna vez se ha desarrollado un método eficiente, sería un peligro para la seguridad actual o eventual de sistemas criptográficos basados-tanto-RSA para el cifrado de clave pública y firmas digitales .

Más específicamente, el problema de RSA es calcular de manera eficiente 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 con φ ( N ) y que 0 ≤  C  <  N . C  se elige al azar dentro de ese rango; para especificar el problema con total precisión, también se debe especificar cómo se generan N y e , que dependerá de los medios precisos de generación de pares de claves aleatorios RSA en uso.

El método más eficiente conocido para resolver el problema de RSA es factorizar primero el módulo N, una tarea que se cree que no es práctica si N es lo suficientemente grande (ver 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 , por lo que exactamente el mismo algoritmo permite que cualquiera que factorice N obtenga la clave privada . Cualquier C se puede descifrar con la clave privada.

Así como no hay pruebas de que la factorización de enteros sea computacionalmente difícil, tampoco hay pruebas de que el problema RSA sea igualmente difícil. Con el método anterior, el problema de RSA es al menos tan fácil como factorizar, pero bien podría ser más fácil. De hecho, existe una fuerte evidencia que apunta a esta conclusión: que un método para romper el método RSA no se puede convertir necesariamente en un método para factorizar semiprimes grandes. [1] Esto es quizás más fácil de ver por la pura exageración del enfoque de factorización: el problema RSA nos pide que descifremos un texto cifrado arbitrario, mientras que el método de factorización revela la clave privada: descifrando así todostextos cifrados arbitrarios, y también permite realizar cifrados de clave privada RSA arbitrarios. En esta misma línea, encontrar el exponente de descifrado d hecho es computacionalmente equivalente a la factorización de N , a pesar de que el problema RSA no pide d . [2]

Además del problema RSA, RSA también tiene una estructura matemática particular que potencialmente puede explotarse sin resolver el problema RSA directamente. Para lograr toda la fuerza del problema de RSA, un criptosistema basado en RSA también debe usar un esquema de relleno como OAEP , para protegerse contra tales problemas estructurales en RSA.

Ver también [ editar ]

Referencias [ editar ]

  1. ^ Boneh, Dan; Venkatesan, Ramarathnam (1998). "Romper RSA puede no ser equivalente a factorizar". Avances en Criptología - EUROCRYPT'98 . Apuntes de conferencias en Ciencias de la Computación. 1403 . Saltador. págs. 59–71. doi : 10.1007 / BFb0054117 . ISBN 978-3-540-64518-4.
  2. ^ Un algoritmo para esto se da, por ejemplo, en Menezes; van Oorschot; Vanstone (2001). "Cifrado de clave pública" (PDF) . Manual de criptografía aplicada .

Lectura adicional [ editar ]