Algoritmul de criptografie DSA

Articol postat de:

DSA

Algoritmul pentru semnaturi digitale (engleza: „Digital Signature Algorithm„), cunoscut si sub acronimul DSA, este un standard al guvernului Statelor Unite ale Americii pentru semnaturile digitale. A fost propus de National Institute of Standards and Technology (NIST) in august 1991 pentru utilizare in cadrul standardului Digital Signature Standard (DSS), adoptat in 1993.

O revizie minora a fost emisa in 1996 sub numele de FIPS 186-1, iar standardul a fost extins in 2000 sub numele FIPS 186-2.

Algoritmul este format din trei proceduri: generarea cheii, semnarea, verificarea semnaturii.

Generarea cheii

DSA

  • Se alege q, astfel incât el este prim si are o dimensiune de 160 de biti (2159 < q < 2160)
  • Se alege p, astfel incât el este prim si p = 2qz+1 (2512< p < 21024)
Ultimele reglementari specifica faptul ca p ar trebui sa fie pe fix 1024 de biti, ceea ce inseamna ca z trebuie sa fie pe 864 de biti.
  • Se alege h ∈ Zp*, unde h este o radacina primitiva in Zp*.
  • α = hz’ mod p, unde z’ = (p-1)/q .
  • Se alege arbitrar α ∈ Zp*.
  • Se calculeaza β = αa mod p.
  • Cheia publica este (p, q, α, β).
  • Cheia privata este a.

Semnarea

  • Se alege arbitrar k ∈ Zq*.
  • Se calculeaza x=SHA-1(mesaj), cu x pe 160 de biti; SHA-1 este functia de hash, care realizeaza rezumatul mesajului (returneaza un numar in functie de continutul mesajului).
  • Se calculeaza γ = ( αk mod p).
  • Se calculeaza δ = ( k-1(x + aγ)) mod q.

Daca vreuna dintre cele doua valori (γ sau δ) este egala cu zero, atunci se reia calculul cu generarea unui alt k.

  • Cheia de semnare este (γ, δ).

Verificarea

  • Se calculeaza w = δ-1 mod q.
  • Se calculeaza e1 = (xw) mod q.
  • Se calculeaza e2 = (γw) mod q.
  • Se calculeaza v = ((αe1βe2) mod p) mod q.
  • Semnatura este valida daca si numai daca v = γ.

Algoritmul Semnaturii Digitale este similar Schemei de semnatura ElGamal.

Corectitudine

Algoritmul este corect in sensul ca destinatarul va accepta intotdeauna doar semnaturi originale. Acest lucru poate fi demonstrat dupa cum urmeaza:

Din α = hz’ mod p rezulta αq ≡ hqz’ ≡ hp-1 ≡ 1 (mod p) din Teorema lui Fermat. Deoarece α > 1 si q este prim, α are ordinul q.

Expeditorul calculeaza

δ = (k-1 (x + α γ))

Deci

k ≡ xδ-1 + a γδ – 1k ≡ xw + aγw

Deoarece α are ordinul q

αk ≡ αxwαaγwαk ≡ αxwβγwαk ≡ αe1βe2 (mod p).

in sfârsit, corectitudinea algoritmului vine din

γ = (αk mod p) mod q = (αe1βe2 mod p) mod q = v.

Securitate

Acest algoritm este considerat imposibil de spart, datorita sigurantei mari asigurate de câteva puncte, cum ar fi generarea aleatoare a lui p, q, a si k. Pentru a se afla k, de exemplu, ar trebui rezolvata o problema de tipul logaritmilor discreti, care este o problema „dificila”, in sensul ca ajungerea la o solutie poate dura câteva luni.

Sursa: Wikipedia


Add Comment Register



Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile necesare sunt marcate *


*

Poți folosi aceste etichete HTML și atribute: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>