Problema RSA 1

Problema RSAEn criptografía, el problema RSA se refiere a la dificultad de efectuar una operación de clave privada mediante elsistema criptográfico RSA conociendo tan solo la clave pública. El algoritmo RSA eleva un mensaje numérico a unexponente público, módulo un número compuesto que es producto de dos primos desconocidos. Para recuperareste mensaje es necesario elevar de nuevo el resultado a un exponente privado, elegido de tal forma que si no seconoce, hallarlo equivale a factorizar el número .Para números suficientemente grandes (mayores de 1024 bits) no se conoce un método eficiente de factorización. Dellegar a desarrollarse, supondría una amenaza para los sistemas de seguridad basados en RSA, tanto de cifrado comode firma digital.

HistoriaEl sistema RSA es la primera propuesta práctica del método criptográfico de clave pública propuesto en 1976 porWhitfield Diffie y Martin Hellman. Fue presentado en 1977 por Jon Rivest, Adi Shamir y Leonhard Adleman, delMIT. Poco después de su presentación el MIT propuso en Scientific American un reto para tranquilizar al públicosobre la eficacia de RSA. Pagarían 100 dólares a quien descifrara un mensaje numérico de 129 cifras decimalespublicado en esas mismas páginas junto a su exponente público y módulo. El problema fue bautizado comoRSA-129, y los autores estimaron que harían falta varios millones de años para conseguirlo.[1]

El 26 de abril de 1994 un equipo de 600 voluntarios coordinados por Atkins, Graff, Lenstra y Leyland consiguióromper RSA-129, ganando los 100 $ prometidos y donándolos a la Free Software Foundation.[2] No era la primeravez que se rompía RSA. En 1991 la RSA Security, empresa al cargo de la seguridad de RSA con sede enMassachusetts, propuso varios números semiprimos (esto es, producto de exactamente dos primos) de a partir de 100cifras decimales y ofreció premios en metálico a quienes encontraran su descomposición. Es lo que se conoció porRSA Challenge. Meses después A. K. Lenstra rompió RSA-100, y a este hito le siguieron otros varios en añossucesivos: RSA-110, 120, 130, etc. hasta que el desafío terminó en 2007. En palabras del laboratorio, «Ahora que laindustria ha alcanzado una comprensión considerablemente mayor de la seguridad criptoanalítica de los algoritmossimétricos comunes y los de clave pública, estos retos dejan de estar activos».[3]

Aunque notables, estos hitos de factorización no dejan de ser casos aislados. Actualmente no se conoce ningúnmétodo general de factorización de enteros y por ello RSA se considera un sistema seguro.

Formas de abordar el problemaTécnicamente, el problema RSA es el siguiente: dada una clave pública RSA y un texto cifrado

, calcular de forma eficiente. La estructura de la clave pública RSA requiere que seaun producto de dos primos grandes, sea coprimo con (la función φ de Euler), y

. se escoge al azar dentro de dicho rango. Para describir el problema con precisión, debe tambiénespecificarse cómo se generan y , lo que dependerá del sistema de generación de claves aleatorias usado.

Problema RSA 2

Factorización

Llamemos y a los factores primos de , esto es, . Buscamos un tal que. Por el pequeño teorema de Fermat basta que cumpla . Falta

conocer , pero la única forma de hacerlo es mediante la fórmula , lo que setraduce en factorizar .El algoritmo RSA está diseñado para escoger primos y suficientemente grandes (del orden de ) para quesea inviable hallarlos mediante ordenadores convencionales. Los métodos más eficientes de factorización denúmeros generales que se conocen son la criba en cuerpos de números (QFS por sus siglas en inglés) y las curvaselípticas. El número más grande factorizado hasta la fecha es RSA-768, un número de 232 cifras decimales (con laactual notación binaria) hallado en enero de 2010 mediante la QFS.[4] Este número está muy por debajo del rangomanejado por el algoritmo RSA.Sin embargo no hay absoluta certeza de que no existan métodos eficientes de factorización, ya sea mediante unnuevo método o una nueva herramienta. La computación cuántica podría proveer de una solución a este problema.

Otros métodosAsí como no hay pruebas de que la factorización de enteros sea computacionalmente difícil, tampoco la hay de queel problema RSA no lo sea. Por el método descrito anteriormente, el sistema RSA es al menos igual de difícil quefactorizar. Pero podría ser incluso menor, ya que el problema RSA no pide expresamente hallar el exponente privadosino solo descifrar un texto. Tal como sugieren D. Boneh y R. Venkatesan, entre descifrar un texto concreto yacceder a la clave privada de cualquier texto cifrado, lo que otorga poder no solo para descifrar cualquier mensajesino para crear nuevos mensajes a voluntad, hay suficiente margen como para que se pueda romper RSA con unmétodo menos ambicioso. Esto podría explicar que aún no se haya demostrado que romper RSA no es equivalente afactorizar.[5]

Además, RSA posee también una estructura matemática que puede ser explotada sin necesidad de resolver elproblema RSA directamente. Para conseguir una funcionalidad completa, el algoritmo RSA debe incluir un «patrónde relleno» (padding scheme) como OAEP que proteja contra esta debilidad.

Véase también• Competición de factorización RSA• Factorización de enteros• NP-completo• RSA• The Magic Words are Squeamish Ossifrage (solución de RSA-129)

Problema RSA 3

Referencias• Koblitz, Neal (1994). A Course in Number Theory and Cryptography, 2ª edición (en inglés), Springer-Verlag.• Quirós, Adolfo (2001). «Números primos y Criptografía [6]» (en español). Boletín de la Sociedad Española de

Matemática Aplicada. n.º 17. pp. 13-21. Consultado el 9-2-2010.

Referencias[1] Gardner, Martin (agosto 1977). « A new kind of cipher that would take millions of years to break (http:/ / www. fortunecity. com/ emachines/

e11/ 86/ cipher1. html)» (en inglés). Scientific American. n.º 237. pp. 120-124. Consultado el 9-2-2010.[2] Atkins, Derek; Michael Graff, Arjen K. Lenstra, Paul C. Leyland (26 abril 1994). « The Magic Words Are Squeamish Ossifrage (http:/ /

www. fortunecity. com/ emachines/ e11/ 86/ cipher1. html)» (en inglés). Lecture Notes In Computer Science. n.º 917. pp. 263-277. Consultadoel 9-2-2010.

[3] RSA Laboratories. « The RSA Factoring Challenge FAQ (http:/ / www. rsa. com/ rsalabs/ node. asp?id=2094)» (en inglés). Consultado el9-2-2010.

[4] Kleinjung et. al, «Factorization of a 768-bit RSA modulus», versión 1.21, 13 de enero de 2010.[5] Boneh, Dan; Ramarathnam Venkatesan (1998). « Breaking RSA may not be equivalent to factoring (http:/ / crypto. stanford. edu/ ~dabo/

papers/ no_rsa_red. pdf)» (en inglés). Proceedings Eurocrypt '98 (Lecture Notes In Computer Science). n.º1233. pp. 59-71. Springer-Verlag. Consultado el 9-2-2010.

[6] http:/ / www. euroestan. com/ criptografia. pdf

Fuentes y contribuyentes del artículo 4

Fuentes y contribuyentes del artículoProblema RSA  Fuente: http://es.wikipedia.org/w/index.php?oldid=33835598  Contribuyentes: JViejo

LicenciaCreative Commons Attribution-Share Alike 3.0 Unportedhttp:/ / creativecommons. org/ licenses/ by-sa/ 3. 0/