Digital Signature Algorithm

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] Arhivat în , la Wayback Machine. și în 2009 ca FIPS 186-3 [3].

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

Generarea cheii

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

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

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

Legături externe

modificare