Problema RSA

En criptografia, el problema RSA es referix a la dificultat d'efectuar una operació de clau privada per mig del sistema criptográfico RSA coneixent tan sol la clau pública. l'algoritme RSA eleva un mensage numèric a un exponent públic, mòdul un número compuesto $N$ que és producte de dos primers desconeguts. Per a recuperar este mensage és necessari elevar de nou el resultat a un exponent privat, elegit de tal forma que si no es coneix, trobar-ho equival a factorizar el número $N$ (açò és, trobar els dos número primo el producte dels quals és N).

Per a números suficientment grans (majors de 1024 bits) no es coneix un método eficient de factorización. D'aplegar a desenrollar-se, supondria una amenaça per als sistemes de seguritat basats en RSA, tant de sifrat com de firma digital.

Història

El sistema RSA és la primera proposta pràctica del método criptográfico de clau pública propost en 1976 per Whitfield Vaig donarffii i Martin Hellman. Va ser presentat en 1977 per Ronald Rivest, Adi Shamir i Leonhard Adleman, del MIT. Poc despuix de la seua presentació el MIT va propondre en Scientific American un repte per a tranquilisar al públic sobre l'eficiència de RSA. Pagarien 100 dólars a qui dessifrara un mensage numèric de 129 sifres decimals publicat en eixes mateixes pàgines junt al seu exponent públic i mòdul. El problema va ser batejat com RSA-129, i els autors varen estimar que farien falta varis millons d'anys per a conseguir-ho.

El 26 d'abril de 1994 un equip de 600 voluntaris coordinats per Atkins, Graff, Lenstra i Leyland va conseguir trencar RSA-129, guanyant els 100 $ promesos i donándolos a la Free Software Foundation. No era la primera volta que es trencava RSA. En 1991 la RSA Security, empresa al càrrec de la seguritat de RSA en sèu en Massachusetts, va propondre varis números semiprimos (açò és, producte d'exactament dos cosins) d'a partir de 100 sifres decimals i va oferir premis en metàlic a els qui trobaren la seua descomposició. És lo que es va conéixer per RSA Challenge. Mesos despuix A. K. Lenstra va trencar RSA-100, i a esta fita li varen seguir atres varis en anys successius: RSA-110, 120, 130, etc. fins que el desafiu va terminar en 2007. En paraules del laboratori, «Ara que l'indústria ha alcançat una comprensió considerablement major de la seguritat criptoanalítica dels algoritmes simètrics comuns i els de clau pública, estos reptes deixen d'estar actius».

Encara que notables, estes fites d'factorización no deixen de ser casos aïllats. Actualment no es coneix cap método general d'factorización de sancers 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 sifrat $C\equiv P^e(\mathrm{mod}N)$, calcular $P$ de forma eficient. L'estructura de la clau pública RSA requerix que $N$ siga un producte de dos cosins grans, $2<e<N$ siga coprimo en $\phi (N)$ (la funció φ de Euler), i $0\le C<N$. $C$ es tria a l'encert dins de dit ranc. Per a descriure el problema en precisió, deu també especificar-se cóm es generen $N$ i $e$, lo que dependrà del sistema de generació de claus aleatòries usat.

Factorización

Cridem $p$ i $q$ als factors primers de $N$, açò és, $N=pq$. Busquem un $d$ tal que $C^d\equiv P(\mathrm{mod}N)$. Pel menuda teorema de Fermat basta que $d$ complixca $de\equiv 1(\mathrm{mod}\phi (N))$. Falta conéixer $\phi (N)$, pero l'única forma de fer-ho és per mig de la fòrmula $\phi (N)=(p-1)(q-1)$, lo que es traduïx en factorizar $N$.

L'algoritme RSA està dissenyat per a triar primers $p$ i $q$ suficientment grans (de l'orde de $10^{200}$) per a que siga inviable trobar-los per mig d'ordenadors convencionals. Els métodos més eficients d'factorización de números generals que es coneixen són la garbell en cossos de números (QFS per les seues sigles en anglés) i les curves elíptiques. El número més gran factorizado fins a la data és RSA-768, un número de 232 sifres decimals (en l'actual notació binaria) trobat en giner de 2010 per mig de la QFS. Este número està molt per baix del ranc manejat per l'algoritme RSA.

No obstant no hi ha absoluta certea de que no existixquen métodos eficients d'factorización, ya siga per mig d'un nou método o una nova ferramenta. La computació quàntica podria proveir d'una solució a este problema.

Atres métodos

Aixina com no hi ha proves de que la factorización de sancers siga computacionalment difícil, tampoc l'hi ha de que el problema RSA no ho siga. Pel método descrit anteriorment, el sistema RSA és a lo manco igual de difícil que factorizar. Pero podria ser inclús menor, ya que el problema RSA no demana expressament trobar l'exponent privat sino solament dessifrar un text. Tal com sugerixen D. Boneh i R. Venkatesan, entre dessifrar un text concret i accedir a la clau privada de qualsevol text sifrat, lo que otorga poder no solament per a dessifrar qualsevol mensage sino per a crear nous mensages a voluntat, hi ha suficient marge com per a que es puga trencar RSA en un método menys ambiciós. Açò podria explicar que encara no s'haja demostrat que trencar RSA no és equivalent a factorizar.

Ademés, RSA posseïx també una estructura matemàtica que pot ser explotada sense necessitat de resoldre el problema RSA directament. Per a conseguir una funcionalitat completa, l'algoritme RSA deu incloure un «patró de farcidura» (padding scheme) com OAEP que protegixca contra esta debilitat.

Vore també

• Competició d'factorización RSA
• Factorización de sancers
• NP-complet
• RSA
• The Magic Words llaure Squeamish Ossifrage (solució de RSA-129)