RSA: diferència entre les revisions

Contingut suprimit Contingut afegit

En línia

Revisió del 00:50, 11 des 2014

En criptografia, l'RSA és un algorisme de xifrat de clau pública. Fou el primer algorisme conegut útil per signar i també per a 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 suficientment llargues.

Història de l'RSA

L'algorisme fou descrit el 1977 per Ron Rivest, Adi Shamir i Len Adleman a l'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. Degut al cost relativament alt dels ordinadors necessaris per implementar-lo en aquell temps fou considerat com una curiositat i, fins es coneix en aquest moment, no es va desenvolupar. La seva descoberta, tot i això, no es va saber fins al 1997, degut a la seva classificació de secreta.

L'algorisme fou patentat per l'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, 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 nombres primers grans p i q diferents de forma aleatòria i independents l'un de l'altre.
Calcula el seu producte n = pq.
Calcula la Funció fi d'Euler φ(n) = (p − 1)(q − 1).
Tria un enter e amb 1 < e < φ(n) que sigui coprimer amb φ(n).
Calcula d tal que $de\equiv 1{\pmod {\varphi (n)}}$ . És a dir $d=e^{\varphi (n)-1}\,$

Els nombres primers poden ser comprovats de forma probabilística usant el Petit teorema de Fermat: $a^{(p-1)}\equiv 1{\pmod {p}}$ , si p és primer. Comprovant amb uns quants valors a diferents, dóna un bona probabilitat que p sigui primer (els nombres de Carmichael poden passar la comprovació per a tot a 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 x tal que $d={\frac {x(p-1)(q-1)+1}{e}}$ sigui un enter, aleshores usant el valor de d mòd n.
Del pas 2 PKCS#1 v2.1 usa λ = mcm(p − 1, q − 1) en lloc de φ(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, 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 de 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:

c=m^{e}{\bmod {n}}

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í

m=c^{d}{\bmod {n}}

Vegeu també

Enllaços externs

PKCS #1: RSA Cryptography Standard (lloc web dels laboratoris RSA)

@@ Línia 12: / Línia 12: @@
 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>, de forma aleatòria i independents l'un de l'altre.
+#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 <math>n = p q \,</math>.
-#Calcula la [[Funció Fi d'Euler]] <math>\phi(n) = (p-1)(q-1) \,</math>.
+#Calcula la [[Funció fi d'Euler]] {{nowrap|1=φ(''n'') = (''p'' − 1)(''q'' − 1)}}.
-#Tria un enter <math>e</math> amb <math>1 < e < \phi(n) \,</math> i que sigui [[coprimer]] amb <math>\phi(n) \,</math>.
+#Tria un enter ''e'' amb {{nowrap|1 < ''e'' < φ(''n'')}} que sigui [[coprimer]] amb φ(''n'').
-#Calcula <math>d</math> tal que <math>d e \equiv 1\pmod{\phi(n)}</math>. És a dir <math>d=e^{\phi(n)-1} \,</math>
+#Calcula ''d'' tal que <math>d e \equiv 1\pmod{\varphi(n)}</math>. És a dir <math>d=e^{\varphi(n)-1} \,</math>
-* els 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; comprovant amb uns quants valors d'<math>a \,</math> dóna un bona probabilitat que <math>p \,</math> és primer. (Els [[Nombres de Carmichael]] poden passar la comprovació per a tot <math>a \,</math>, però són extremadament rars.)
+* 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. Comprovant amb uns quants valors ''a'' diferents, dóna un bona probabilitat que ''p'' sigui primer (els [[nombres de Carmichael]] poden passar la comprovació per a tot ''a'' però són extremadament rars).
-*(Els passos 3 i 4 es poden millorar amb l'[[Algorisme d'Euclides ampliat]]; vegeu [[aritmètica modular]].)
+* 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> és un enter, aleshores usant el valor de <math>d \pmod{(p-1)(q-1)} \,</math>;
+* El pas 4, alternativament, també es pot considerar com trobar un enter ''x'' tal que <math>d = \frac{x(p-1)(q-1)+1}{e}</math> sigui un enter, aleshores usant el valor de ''d'' mòd ''n''.
-*(Del pas 2 PKCS#1 v2.1 usa <math>\lambda = m.c.m(p-1, q-1) \,</math> en lloc de <math>\phi = (p-1)(q-1) \,</math>).
+* 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
+La '''[[clau pública]]''' consisteix en
 * ''n'', el mòdul, i
-* ''e'', l'exponent públic (algunes vegades anomenat ''exponent de xifrat'').
+* ''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.
+* ''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'''):
+Habitualment, s'emmagatzema una forma alternativa de clau privada (incloent-hi els «paràmetres TXR»):
-* ''p'' i ''q'', els nombres primers que generen la clau,
+* El parell ''p'', ''q'' de nombres primers que generen la clau.
-* ''d mod (p-1)'' i ''d mod (q-1)'' (habitualment coneguts com a ''dmp1'' i ''dmq1'')
+* El parell ''d'' mòd (''p'' − 1), ''d'' mòd (''q'' − 1) habitualment coneguts com a «dmp1» i «dmq1».
-* ''(1/q) mod p'' (habitualment conegut com a ''iqmp'')
+* (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, 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 deforma segura amb tots els valors intermedis usats en la generació de la clau.
+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 de 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:
+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>
-: <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í
+Per a llegir el missatge l'Alice calcula el text desxifrat ''m'' així
+:<math> m = c^d \bmod n</math>
-: <math> m = c^d \mod{n}</math>
 == Vegeu també ==