Problema RSA

En criptografia, el problema RSA es refereix a la dificultat d'efectuar una operació de clau privada mitjançant el sistema criptogràfic RSA coneixent tan sols la clau pública. L'algorisme RSA eleva un missatge numèric a un exponent públic, mòdul un nombre compost que és producte $N$ de dos primers desconeguts.Per recuperar aquest missatge és necessari elevar de nou el resultat a un exponent privat, triat de tal forma que si no es coneix, trobar-ho equival a factoritzar el nombre $N$ (això és, trobar els dos nombres primers el producte dels quals és N).

Per a nombres suficientment grans (majors de 1024 bits) no es coneix un mètode eficient de factorització. D'arribar a desenvolupar-se, suposaria una amenaça per als sistemes de seguretat basats en RSA, tant de xifrat com de signatura digital.

Història

El sistema RSA és la primera proposta pràctica del mètode criptogràfic de clau pública proposat el 1976 per Whitfield Diffie i Martin Hellman. Va ser presentat el 1977 per Ronald Rivest, Adi Shamir i Leonhard Adleman, del MIT. Poc després de la seva presentació el MIT va proposar en Scientific American un repte per tranquil·litzar al públic sobre l'eficiència d'RSA. Pagarien 100 dòlars a qui desxifrés un missatge numèric de 129 xifres decimals publicat en aquestes mateixes pàgines al costat del seu exponent públic i mòdul. El problema va ser batejat com RSA-129, i els autors van estimar que farien falta diversos milions d'anys per aconseguir-ho.

El 26 d'abril de 1994 un equip de 600 voluntaris coordinats per Atkins, Graff, Lenstra i Leyland va aconseguir trencar RSA-129, guanyant els 100 $ promesos i donant-los a la Free Programari Foundation. No era la primera vegada que es trencava RSA. El 1991 l'RSA Security, empresa al càrrec de la seguretat d'RSA amb seu a Massachusetts, va proposar diversos nombres semiprimers (això és, producte d'exactament dos primers) d'a partir de 100 xifres decimals i va oferir premis en metàl·lic als qui trobessin la seva descomposició. És el que es va conèixer per RSA Challenge. Mesos després A. K. Lenstra va trencar RSA-100, i a aquesta fita la van seguir altres en anys successius: RSA-110, 120, 130, etc. fins que el desafiament va acabar el 2007. En paraules del laboratori, «Ara que la indústria ha aconseguit una comprensió considerablement major de la seguretat criptoanalítica dels algorismes simètrics comuns i els de clau pública, aquests reptes deixen d'estar actius».

Encara que notables, aquestes fites de factorització no deixen de ser casos aïllats. Actualment no es coneix cap mètode general de factorització d'enters i per això RSA es considera un sistema segur.

Formes d'abordar el problema

Tècnicament, el problema RSA és el següent: donada una clau pública RSA$(N,e)$ i un text xifrat $C\equiv P^{e}{\pmod {N}}$, calcular $P$ de forma eficient. L'estructura de la clau pública RSA requereix que $N$ siga un producte de dos primers grans, $2<e<N$ siga coprimer amb $\varphi (N)$ (la funció φ d'Euler), i $0\leq C<N$. $C$ es tria a l'atzar dins d'aquest rang. Per descriure el problema amb precisió, deu també especificar-se com es generen $N$ i $e$, la qual cosa dependrà del sistema de generació de claus aleatòries usat.

Factorització

Anomenem $p$ i $q$ als factors primers de $N$, això és, $N=pq$ Busquem un $d$ tal que $C^{d}\equiv P{\pmod {N}}$. Pel petit teorema de Fermat basta que $d$ complisca$de\equiv 1{\pmod {\varphi (N)}}$. Resta per conèixer $\varphi (N)$, però l'única forma de fer-ho és mitjançant la fórmula$\varphi (N)=(p-1)(q-1)$, cosa que es tradueix en factoritzar $N$.

L'algorisme RSA està dissenyat per escollir primers $p$ i $q$suficientment grans (de l'ordre de $10^{200}$) perquè siga inviable trobar-los mitjançant ordinadors convencionals. Els mètodes més eficients de factorització de nombres generals que es coneixen són el garbell en cossos de nombres (QFS per les seves sigles en anglès) i les corbes el·líptiques. El nombre més gran factoritzat fins avui és RSA-768, un nombre de 232 xifres decimals (amb l'actual notació binària) trobat el gener de 2010 mitjançant la QFS. Aquest nombre està molt per sota del rang emprat per l'algorisme RSA.

No obstant això no hi ha absoluta certesa que no existeixin mètodes eficients de factorització, ja siga mitjançant un nou mètode o una nova eina. La computació quàntica podria proveir d'una solució a aquest problema.

Altres mètodes

Així com no hi ha proves que la factorització d'enters siga computacionalment difícil, tampoc n'hi ha que el problema RSA no ho siga. Pel mètode descrit anteriorment, el sistema RSA és almenys igual de difícil que factoritzar. Però podria ser fins i tot menor, ja que el problema RSA no demana expressament trobar l'exponent privat sinó només desxifrar un text. Tal com suggereixen D. Boneh i R. Venkatesan, entre desxifrar un text concret i accedir a la clau privada de qualsevol text xifrat, la qual cosa atorga poder no només per desxifrar qualsevol missatge sinó per crear nous missatges a voluntat, hi ha suficient marge com perquè es puga trencar RSA amb un mètode menys ambiciós. Això podria explicar que encara no s'haja demostrat que trencar RSA no és equivalent a factoritzar.

A més, RSA posseeix també una estructura matemàtica que pot ser explotada sense necessitat de resoldre el problema RSA directament. Per aconseguir una funcionalitat completa, l'algorisme RSA ha d'incloure un «patró de farcit» (padding scheme) com OAEP que protegeixi contra aquesta feblesa.

Bibliografia

• Koblitz, Neal. A Course in Number Theory and Cryptography (en anglès). 2a edició. Springer-Verlag, 1994. 
• Quirós, Adolfo «Números primos y Criptografía» (en castellà). Boletín de la Sociedad Española de Matemática Aplicada, 17, 2001, pàg. 13-21. Arxivat de l'original el 2010-02-16 [Consulta: 9 febrer 2010].