Diferència entre revisions de la pàgina «RSA»

34 octets eliminats ,  fa 6 anys
m (Corregit: descrit al [[1977 > descrit el [[1977)
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 els següents passos per generar una clau pública i una clau privada:
 
#Tria dos [[nombre primer|nombres primers]] grans <math>''p \,</math>'' i <math>''q'' \,</math> tals que <math>p \ne q</math>,diferents de forma aleatòria i independents l'un de l'altre.
#Calcula el seu [[producte (matemàtiques)|producte]] ''n'' = ''pq''.
#Calcula <math>n = p q \,</math>.
#Calcula la [[Funció Fifi d'Euler]] <math>\phi{{nowrap|1=φ(''n'') = (''p-'' − 1)(''q-'' − 1) \,</math>}}.
#Tria un enter <math>''e</math>'' amb <math>{{nowrap|1 < ''e'' < \phiφ(''n'') \,</math> i}} que sigui [[coprimer]] amb <math>\phiφ(''n'') \,</math>.
#Calcula <math>''d</math>'' tal que <math>d e \equiv 1\pmod{\phivarphi(n)}</math>. És a dir <math>d=e^{\phivarphi(n)-1} \,</math>
 
* elsEls nombres primers poden ser comprovats de forma probabilística usant el [[Funció Fi d'Euler|Petit teorema de Fermat]]: <math>a^{(p-1)} \equiv 1 \pmod{p}</math>, si <math>''p \,</math>'' és primer;. comprovantComprovant amb uns quants valors d'<math>'a'' \diferents,</math> dóna un bona probabilitat que <math>''p'' \,</math> éssigui primer. (Elsels [[Nombresnombres de Carmichael]] poden passar la comprovació per a tot <math>''a \,</math>,'' però són extremadament rars).)
*( Els passos 3 i 4 es poden millorar amb l'[[Algorisme d'Euclides ampliat]]; vegeu [[aritmètica modular]].)
*( El pas 4, alternativament, també es pot considerar com trobar un enter <math>''x \,</math>'' tal que <math>d = \frac{x(p-1)(q-1)+1}{e}</math> éssigui un enter, aleshores usant el valor de <math>''d'' \pmod{(p-1)(q-1)}mòd \,</math>;''n''.
*( Del pas 2 PKCS#1 v2.1 usa <math>\lambda{{nowrap|1=''λ'' = m.c.mmcm(''p-'' − 1, ''q-'' − 1) \,</math>}} en lloc de <math>\phi{{nowrap|1=φ(''n'') = (''p-'' − 1)(''q-'' − 1) \,</math>)}}.
 
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'' i, ''q'', elsde nombres primers que generen la clau,.
* El parell ''d'' modmòd (''p-1)'' i− 1), ''d'' modmòd (''q-1)'' (− 1) habitualment coneguts com a ''«dmp1''» i ''«dmq1'')».
* ''(1/''q'') modmò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, ja que 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 deformade forma segura amb tots els valors intermedis usats en la generació de la clau.
 
=== Xifrat 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'':
#Calcula :<math>n c = p qm^e \,bmod n</math>.
 
: <math> c = m^e \mod{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.
 
=== Desxifrat de missatges ===
Per a llegir el missatge l'Alice calcula el text desxifrat ''m'' així
: <math> cm = mc^ed \mod{bmod n}</math>
 
: <math> m = c^d \mod{n}</math>
 
 
== Vegeu també ==