RSA: diferència entre les revisions

Contingut suprimit Contingut afegit

En línia

Revisió del 07:25, 19 gen 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 al 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 al 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\,$ tals que $p\neq q$ , de forma aleatòria i independents l'un de l'altre.
Calcula $n=pq\,$ .
Calcula la Funció Fi d'Euler $\phi (n)=(p-1)(q-1)\,$ .
Tria un enter $e$ amb $1<e<\phi (n)\,$ i que sigui coprimer amb $\phi (n)\,$ .
Calcula $d$ tal que $de\equiv 1{\pmod {\phi (n)}}$ . És a dir $d=e^{\phi (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 d' $a\,$ dóna un bona probabilitat que $p\,$ és 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}}$ és un enter, aleshores usant el valor de $d{\pmod {(p-1)(q-1)}}\,$ ;
(Del pas 2 PKCS#1 v2.1 usa $\lambda =m.c.m(p-1,q-1)\,$ en lloc de $\phi =(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):

p i q, els nombres primers que generen la clau,
d mod (p-1) i d mod (q-1) (habitualment coneguts com a dmp1 i dmq1)
(1/q) mod 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 d'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.

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}\mod {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}\mod {n}

Vegeu també

Enllaços externs

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

@@ Línia 37: / Línia 37: @@
 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 d'''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 d'''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.
 === Xifrat de missatges ===