Algoritm pentru Semnături Digitale

De la Wikipedia, enciclopedia liberă

Salt la: Navigare, căutare

Digital Signature Algorithm ("Algoritm pentru Semnături Digitale"), cunoscut şi sub acronimul DSA, este un standard al Guvernului Statelor Unite ale Americii pentru semnăturile digitale. A fost propus de National Institute of Standards and Technology (NIST) în august 1991 pentru utilizare în Digital Signature Standard (DSS), adoptat în 1993. O revizie minoră a fost emisă în 1996 sub numele de FIPS 186-1 [1], iar standardul a fost extins în 2000 sub numele FIPS 186-2 [2].

Algoritmul este format din trei etape.

Cuprins

[modifică] Generarea cheii

  • Se alege q, astfel încât el este prim şi are o dimensiune de 160 de biţi (2159 < q < 2160).
  • Se alege p, astfel încât el este prim şi p = 2qz+1 (2512 < p < 21024).
Ultimele reglementări specifică faptul că p ar trebui să fie pe fix 1024 de biţi, ceea ce înseamnă că z trebuie să fie pe 864 de biţi.
  • Se alege h \in \mathbb{Z}_{p}^{*}, unde h este o rădăcină primitivă în \mathbb{Z}_{p}^{*}.
  • \alpha = h^{z'}\mod p\,, unde z'=\frac{p-1}{q}.
  • Se alege arbitrar a \in \mathbb{Z}_{q}^{*}.
  • Se calculează \beta = \alpha^a \mod p\,.
  • Cheia publică este (p,q,\alpha,\beta)\,.
  • Cheia privată este a\,.

[modifică] Semnarea

  • Se alege arbitrar k \in \mathbb{Z}_{q}^{*}.
  • Se calculează x=SHA-1(mesaj), cu x pe 160 de biţi; SHA-1 este funcţia de hash, care realizează rezumatul mesajului (returnează un număr în funcţie de conţinutul mesajului).
  • Se calculează \gamma = (\alpha ^k \mod p)\mod q\,.
  • Se calculează \delta = (k^{-1}(x + a\gamma))\mod q\,.
Dacă vreuna dintre cele două valori (\gamma\, sau \delta\,) este egală cu zero, atunci se reia calculul cu generarea unui alt k.
  • Cheia de semnare este (\gamma,\delta)\,.

[modifică] Verificarea

  • Se calculează w=\delta^{-1} \mod q\,.
  • Se calculează e_1=(xw) \mod q\,.
  • Se calculează e_2=(\gamma w) \mod q\,.
  • Se calculează v=((\alpha^{e_1}\beta^{e_2})\mod p) \mod q\,.
  • Semnătura este validă dacă şi numai dacă v=\gamma\,.

Algoritmul Semnăturii Digitale este similar Schemei de semnătură ElGamal.

[modifică] Corectitudine

Algoritmul este corect în sensul că destinatarul va accepta întotdeauna doar semnături originale. Acest lucru poate fi demonstrat după cum urmează:

Din \alpha = h^{z'} \mod p\, rezultă \alpha^q \equiv h^{qz'} \equiv h^{p-1} \equiv 1 \pmod p\, din Teorema lui Fermat. Deoarece \alpha>1\, şi q este prim, \alpha\, are ordinul q.

Expeditorul calculează

\delta=(k^{-1}(x+a\gamma)) \mod{q}.

Deci

\begin{matrix} k & \equiv & x\delta^{-1}+a\gamma\delta^{-1}\\ & \equiv & xw + a\gamma w \pmod{q}.\\ \end{matrix}

Deoarece \alpha\, are ordinul q

\begin{matrix} \alpha^k & \equiv & \alpha^{xw}\alpha^{a\gamma w}\\ & \equiv & \alpha^{xw}\beta^{\gamma w}\\ & \equiv & \alpha^{e_1}\beta^{e_2} \pmod{p}.\\ \end{matrix}

În sfârşit, corectitudinea algoritmului vine din

\gamma=(\alpha^k \mod p) \mod q = (\alpha^{e_1}\beta^{e_2} \mod p) \mod q = v.

[modifică] Securitate

Acest algoritm este considerat imposibil de spart, datorită siguranţei mari asigurate de câteva puncte, cum ar fi generarea aleatoare a lui p, q, a şi k. Pentru a se afla k, de exemplu, ar trebui rezolvată o problemă de tipul logaritmilor discreţi, care este o problemă "dificilă", în sensul că ajungerea la o soluţie poate dura câteva luni.

Adus de la http://ro.wikipedia.org/wiki/Algoritm_pentru_Semn%C4%83turi_Digitale
Unelte personale