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 , unde h este o rădăcină primitivă în .
  • , unde .
  • Se alege arbitrar .
  • Se calculează .
  • Cheia publică este .
  • Cheia privată este .

Semnarea[modificare | modificare sursă]

  • Se alege arbitrar .
  • 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ă .
  • Se calculează .
Dacă vreuna dintre cele două valori ( sau ) este egală cu zero, atunci se reia calculul cu generarea unui alt k.
  • Cheia de semnare este .

Verificarea[modificare | modificare sursă]

  • Se calculează .
  • Se calculează .
  • Se calculează .
  • Se calculează .
  • Semnătura este validă dacă și numai dacă .

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 rezultă din Teorema lui Fermat. Deoarece și q este prim, are ordinul q.

Expeditorul calculează

Deci

Deoarece are ordinul q

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

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ă]