{"id":5178,"date":"2020-01-30T12:26:29","date_gmt":"2020-01-30T10:26:29","guid":{"rendered":"http:\/\/pimedios.es\/?p=5178"},"modified":"2020-01-30T12:26:29","modified_gmt":"2020-01-30T10:26:29","slug":"descifrando-el-rsa","status":"publish","type":"post","link":"http:\/\/pimedios.jesussoto.es\/?p=5178","title":{"rendered":"Descifrando el RSA"},"content":{"rendered":"
\"\"<\/a>
Token SecurID SID700<\/figcaption><\/figure>\n

En mis clases de Matem\u00e1tica Discreta les hablo a mis alumno del RSA, incluso hacemos peque\u00f1os ejemplos con el algoritmo. Es una de las formas para ver c\u00f3mo aplican esas cosas raras<\/em>\u00a0para ellos que llamamos \u00abcongruencias\u00bb.<\/p>\n

El RSA es un\u00a0 sistema criptogr\u00e1fico de clave p\u00fablica desarrollado en 1979. Dicen que es el primero y m\u00e1s extendido algoritmo de este tipo, v\u00e1lido tanto para cifrar como para firmar digitalmente.<\/p>\n

La seguridad del cifrado RSA radica en el hecho de que\u00a0hasta el momento no existe un algoritmo eficiente para factorizar enteros; hablamos de un algoritmo que factorice enteros con $n$ d\u00edgitos en un tiempo\u00a0polinomial del orden $\\mathcal{O}(n^k)$. De modo que si elegimos dos primos suficientemente grandes, $n=p\\cdot q$ no resulta pr\u00e1ctico calcular su factorizaci\u00f3n, en un tiempo prudencial.<\/p>\n

El funcionamiento de este sistema, descrito en 1977 por Ron R<\/strong>ivest, Adi S<\/strong>hamir y Leonard A<\/strong>dleman, del Instituto Tecnol\u00f3gico de Massachusetts (MIT), aunque\u00a0\u00a0el matem\u00e1tico brit\u00e1nico Clifford Cocks, que trabajaba para la agencia de inteligencia brit\u00e1nica, formaliz\u00f3 un sistema equivalente en un documento interno en 1973, est\u00e1 extensamente explicado, v\u00e9ase por ejemplo en wikipedia\u00a0 RSA<\/a>.\u00a0\u00a0Es de los sistemas de cifrado que se definen como sistema de clave p\u00fablica; cada usuario posee dos claves de cifrado: una p\u00fablica y otra privada. Esa calve p\u00fablica es un $n$, muy grande, como el que habl\u00e1bamos antes, y un entero $e$, el exponente de cifrado, con ciertas propiedades, muy pr\u00e1cticas para explicar conceptos de aritm\u00e9tica modular.<\/p>\n

Pero veamos un poco m\u00e1s de su historia.<\/p>\n

Seg\u00fan nos cuenta Richard Johnsonbaugh, en su libro Matem\u00e1ticas Discretas, la\u00a0primera descripci\u00f3n del sistema de cifrado RSA apareci\u00f3 en una columna de Martin\u00a0Gardner en la edici\u00f3n de febrero de 1977 del Scientific American(Una observaci\u00f3n, \u00a0R<\/strong>ivest,\u00a0S<\/strong>hamir y\u00a0A<\/strong>dleman lo publicaron como una \u00a0MIT \u00abTechnical Memo\u00bb en abril de 1977, y oficialmente en una publicaci\u00f3n en 1978, lo que nos dice que Gardner estaba al tanto de los avances en criptograf\u00eda de esos a\u00f1os). En esta columna se incluy\u00f3 un mensaje codificado utilizando una clave dada por el\u00a0producto de dos primos de 64 y 65 d\u00edgitos y e=9007, junto con un premio de 100 d\u00f3lares para\u00a0la primera persona que descifrase el c\u00f3digo. Cuando se escribi\u00f3 el art\u00edculo, se estimaba\u00a0que se necesitar\u00edan 40,000 billones de a\u00f1os para factorizar $n$. De hecho, en abril de 1994,\u00a0Arjen Lenstra, Paul Leyland, Michael Graff y Derek Atkins, con la ayuda de 600 voluntarios\u00a0de 25 pa\u00edses, utilizando m\u00e1s de 1600 computadoras, factorizaron $n$, coordinando la factorizaci\u00f3n mediante Internet. Antonio Ropero detall\u00f3 este reto en su post Martin Gardner, RSA y otros pasatiempos matem\u00e1ticos<\/a>.<\/p>\n

Y ahora, \u00bfen cu\u00e1nto tiempo lo descifrar\u00edais? Os anim\u00e1is a poner a trabajar a vuestros alumnos.<\/p>\n

Este post forma parte del\u00a0Carnaval de Matem\u00e1ticas<\/strong>, que en esta septuag\u00e9sima novena edici\u00f3n, tambi\u00e9n denominada X.6, est\u00e1 organizado por\u00a0@juanfisicahr<\/strong><\/a>\u00a0a trav\u00e9s de su blog\u00a0Esto no entra en el examen<\/a>.<\/p><\/blockquote>\n

PD: Si te ha gustado este post, quiz\u00e1s tambi\u00e9n te guste otras cosas que cuento en mi novela Muret<\/strong>, la batalla que marc\u00f3 a la Corona de Arag\u00f3n<\/p>\n

\"\"<\/a>
Muret, la novela sobre la batalla de Muret de 1213.<\/figcaption><\/figure>\n","protected":false},"excerpt":{"rendered":"

Un poco de historia sobre el RSA<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,9],"tags":[89,229,730],"class_list":["post-5178","post","type-post","status-publish","format-standard","hentry","category-historia","category-personajes","tag-criptografia","tag-martin-gardner","tag-rsa","entry"],"_links":{"self":[{"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/5178","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5178"}],"version-history":[{"count":5,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/5178\/revisions"}],"predecessor-version":[{"id":5183,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=\/wp\/v2\/posts\/5178\/revisions\/5183"}],"wp:attachment":[{"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5178"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/pimedios.jesussoto.es\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}