Mostra la font per a RSA

En [[criptografia]], l''''RSA''' és un [[algorisme]] de [[xifratge de clau pública]]. Fou el primer algorisme conegut útil per [[signatura digital|signar]] i també per a [[encriptar|xifrar]], i un dels primers en la criptografia de clau pública. L'RSA encara s'empra en protocols de [[comerç electrònic]], i es considera segur si s'empren claus prou llargues.

== Història de l'RSA ==
L'algorisme fou descrit el [[1977]] per [[Ron Rivest]], [[Adi Shamir]] i [[Len Adleman]] a l'[[MIT|Institut de Tecnologia de Massachusetts]]. Les lletres RSA corresponen a les inicials dels seus cognoms.

[[Clifford Cocks]], un matemàtic anglès que treballa pel [[GCHQ]], va descriure un sistema equivalent en un document intern el [[1973]]. A causa del cost relativament alt dels ordinadors necessaris per implementar-lo en aquell temps va ser considerat com una curiositat, i no es va desenvolupar. La seva descoberta, tot i això, no es va saber fins al [[1997]], per culpa de la seva classificació de secreta.

L'algorisme va ser patentat per l'[[MIT|Institut de Tecnologia de Massachusetts]] el [[1983]] als [[Estats Units d'Amèrica]]. Aquesta patent expirà el [[21 de setembre]] del [[2000]].

== Operativa ==
=== Generació de claus ===
Suposeu que una usuària, l'[[Alice i Bob|Alice]], desitja que un altre usuari, en Bob, li enviï un missatge privat a través d'un mitjà de transmissió no segur. Alice fa les següents passes per generar una clau pública i una clau privada:

#Tria dos [[nombre primer|nombres primers]] grans ''p'' i ''q'' diferents de forma aleatòria i independents l'un de l'altre.
#Calcula el seu [[producte (matemàtiques)|producte]] ''n'' = ''pq''.
#Calcula el valor de la [[Funció fi d'Euler]] {{nowrap|1=φ(''n'') = (''p'' − 1)(''q'' − 1)}}.
#Tria un nombre enter ''e'' amb {{nowrap|1 < ''e'' < φ(''n'')}} que sigui [[coprimer]] amb φ(''n'').
#Calcula ''d'' tal que <math>d e \equiv 1\pmod{\varphi(n)}</math>. És a dir <math>de=1+k\varphi(n)</math> per algun ''k'' enter. d és l'invers de e mòdul φ(''n'').

* Els nombres primers poden ser comprovats de forma probabilística usant el [[Petit teorema de Fermat]]: <math>a^{p-1} \equiv 1 \pmod{p}</math>, si ''p'' és primer i no divideix a. Comprovant amb uns quants valors ''a'' diferents, dona un bona probabilitat que ''p'' sigui primer (els [[nombres de Carmichael]] poden passar la comprovació per a tot ''a'' però són extremadament rars).
* El pas 5 es fa amb l'[[Algorisme d'Euclides ampliat]]; vegeu [[aritmètica modular]].
* Del pas 2 PKCS#1 v2.1 usa {{nowrap|1=''λ'' = mcm(''p'' − 1, ''q'' − 1)}} en lloc de {{nowrap|1=φ(''n'') = (''p'' − 1)(''q'' − 1)}}.

La '''[[clau pública]]''' consisteix en
* ''n'', el mòdul, i
* ''e'', l'exponent públic (algunes vegades anomenat «exponent de xifrat»).

La '''clau privada''' consisteix en
* ''n'', el mòdul, que és públic i apareix a la clau pública, i
* ''d'', l'exponent privat (algunes vegades anomenat «exponent de desxifrat»), que ha de romandre en secret.

Habitualment, s'emmagatzema una forma alternativa de clau privada (incloent-hi els «paràmetres TXR»):
* El parell ''p'', ''q'' de nombres primers que generen la clau.
* El parell ''d'' mòd (''p'' − 1), ''d'' mòd (''q'' − 1) habitualment coneguts com a «dmp1» i «dmq1».
* (1/''q'') mòd ''p'' habitualment conegut com a «iqmp».
Aquesta forma permet un desxifrat i una signatura ràpids fent servir el [[Teorema xinès del residu]] (TXR). En aquesta forma, totes les parts de la clau privada han de romandre en secret.

L'Alice transmet la clau pública al Bob, i conserva en secret la clau privada. ''p'' i ''q'' són necessaris, perquè són els únics factors divisors de ''n'', i permeten la computació de ''d'' donat ''e''. Si ''p'' i ''q'' no s'emmagatzemen en la forma TXR de clau privada, s'han d'esborrar de manera segura amb tots els valors intermedis usats en la generació de la clau.

=== Xifratge de missatges ===
Suposeu que en Bob desitja enviar un missatge ''M'' a l'Alice. Primer converteix ''M'' en un nombre ''m'' < ''n'', fent servir algun protocol reversible acordat prèviament, conegut com a [[tècnica de farciment]].

En Bob ara té ''m'', i coneix ''n'' i ''e'', que l'Alice ha publicat. Aleshores, calcula el text xifrat corresponent a ''m'':
:<math> c = m^e \bmod n</math>
Això es pot fer ràpidament fent servir el mètode de l'[[exponenciació per quadrats]]. Aleshores en Bob transmet ''c'' a l'Alice.

=== Desxifratge de missatges ===
Per a llegir el missatge l'Alice calcula el text desxifrat ''m'' així
:<math> m = c^d \bmod n</math>

== Vegeu també ==
* [[DSA]]
* [[Xifratge de Cèsar]]
* [[clau (criptografia)|Clau]]
* [[Signatura digital]]
* [[Màquina Enigma]]
* [[Criptografia de corba el·líptica]]

== Enllaços externs ==
* [http://www.rsasecurity.com/rsalabs/node.asp?id=2125 PKCS #1: RSA Cryptography Standard (lloc web dels laboratoris RSA)] {{Webarchive|url=https://web.archive.org/web/20051029040347/http://rsasecurity.com/rsalabs/node.asp?id=2125 |date=2005-10-29}}

[[Categoria:Seguretat informàtica]]
[[Categoria:Algorismes criptogràfics]]