Algoritm pentru Semnături Digitale

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Algoritmul pentru semnături digitale (engleză: "Digital Signature Algorithm"), 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 cadrul standardului Digital Signature Standard (DSS), specificat în FIPS 186 și adoptat în 1993. O revizie minoră a fost emisă în 1996 sub numele de FIPS 186-1 [1]. Standardul a fost extins în 2000 ca FIPS 186-2 [2] și în 2009 ca FIPS 186-3 [3].

Algoritmul este format din trei proceduri: generarea cheii, semnarea, verificarea semnăturii.

Generarea cheii[modificare | modificare sursă]

  • 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\,.

Semnarea[modificare | modificare sursă]

  • 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)\,.

Verificarea[modificare | modificare sursă]

  • 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.

Corectitudine[modificare | modificare sursă]

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.

Securitate[modificare | modificare sursă]

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.

Vezi și[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]