Digital Signature Algorithm

Dla systemu wybierana jest pewna funkcja skrótu ${\displaystyle H(M)}$

Klucze tworzone są w następujący sposób:^[4]

• Wybierana jest liczba pierwsza ${\displaystyle p}$ , taka że ${\displaystyle 2^{L-1}<p<2^{L}}$ .
• Wybierana jest liczba pierwsza ${\displaystyle q}$ , taka że ${\displaystyle 2^{N-1}<q<2^{N}}$  i że liczba ${\displaystyle p-1}$  podzielna jest przez ${\displaystyle q}$ .
• Obliczany jest parametr ${\displaystyle g=h^{(p-1)/q}\ {\text{mod}}\ p}$ , gdzie ${\displaystyle h}$  jest losową liczbą spełniającą warunek ${\displaystyle 1<h<(p-1)}$ .
• Wybierany jest klucz prywatny ${\displaystyle x}$  będący losową liczbą całkowitą spełniającą warunek ${\displaystyle 0<x<q}$ .
• Obliczany jest klucz publiczny ${\displaystyle y=g^{x}\ {\text{mod}}\ p}$ .

Norma FIPS 186-4 przewiduje dla liczb ${\displaystyle (L,N)}$

Podpis składa się z pary liczb ${\displaystyle (r,s)}$

• Dla podpisywanej wiadomości ${\displaystyle M}$  wybierana jest losowa liczba całkowita ${\displaystyle k}$  spełniająca ${\displaystyle 0>k>q}$ .
• Obliczana jest liczba ${\displaystyle r=(g^{k}\ {\text{mod}}\ p)\ {\text{mod}}\ q}$ .
• Wyznaczane jest ${\displaystyle z}$ , czyli co najwyżej ${\displaystyle N}$  najbardziej znaczących bitów skrótu wiadomości ${\displaystyle H(M)}$ .
• Obliczana jest liczba ${\displaystyle s=(k^{-1}(z+xr))\ {\text{mod}}\ q}$ .

Jeżeli ${\displaystyle r=0}$

Niech ${\displaystyle M',r',s'}$

• Obliczane jest ${\displaystyle w=(s')^{-1}\ {\text{mod}}\ q}$ .
• Wyznaczane jest ${\displaystyle z}$ , czyli co najwyżej ${\displaystyle N}$  najbardziej znaczących bitów ${\displaystyle H(M')}$ .
• Wyznaczane są ${\displaystyle u_{1}=(zw)\ {\text{mod}}\ q}$  oraz ${\displaystyle u_{2}=((r')w)\ {\text{mod}}\ q}$ .
• Obliczane jest ${\displaystyle v=(((g)^{u_{1}}(y)^{u_{2}})\ {\text{mod}}\ p)\ {\text{mod}}\ q}$ .
• Jeżeli ${\displaystyle v=r'}$ , to podpis jest prawidłowy.

Jeżeli ${\displaystyle v\neq r'}$

Wybór zmiennej ${\displaystyle k}$

DSA umożliwia przesyłanie informacji podprogowej. Jeżeli zamiast liczby losowej ${\displaystyle k}$

• ElGamal
• RSA (kryptografia)