DSA

DSA (Digital Signature Algorithm), skaitmeninio parašo algoritmas yra Jungtinių Valstijų federalinės valdžios (Šablonas:En) standartinis skaitmeninis parašas. Jis buvo patvirtintas Nacionalinės standartų ir technologijų instituto (NIST, National Institute of Standards and Technology) 1991 metais.

Raktų generavimas

• Pasirenkamas 160-bitų pirminis skaičius $q$.
• Pasirenkamas $L$-bitų ilgio pirminis skaičius $p$, toks kad tenkintu sąlygą $p=qz+1$ kur $z$ yra sveikas skaičius ir kad $L$ tenkintu sąlygą $512<=L<=1024$ ir $L$ dalintusi iš 64.
• Pasirenkamas $h$, kuris $1<h<p-1$ toks kad tenkinama lygybė $g=h*zmodp>1$
• Pasirenkamas atsitiktinai sugeneruota skaičių x kuris tenkintu sąlyga $0<x<q$
• Suskaičiuojamas $y=g*xmodp$
• Viešas raktas yra $(p,q,g,y)$. Privatus raktas yra $x$.

Pasirašymas

• Generuojama atsitiktinė žinutė, kurios reikšmė k būtų $0<k<q$
• Suskaičiuojama $r=(g^{k}modp)modq$
• Suskaičiuojama $s=(k^{-1}(SHA-1(m)+x*r))modq$ , kur $SHA-1(m)$ yra SHA-1 santraukos funkcija taikoma žinutei $m$.
• Perskaičiuojam parašą mažai tikėtinu atveju kai $r=0$ arba $s=0$
• Parašas yra $(r,s)$.

Patvirtinimas

• Atmesti parašą jei netenkinama bent viena iš sąlygų $0<r<q$ arba $0<s<q$
• Suskaičiuojama $w=s^{-1}modq$
• Suskaičiuojama $u_1=(SHA-1(m)*w)modq$
• Suskaičiuojama $u_2=(r*w)modq$
• Suskaičiuojama $v=((g^{u_1}*y^{u_2})modp)modq$
• Parašas galioja jeigu tenkinama lygybe $v=r$.