Digital Signature Algorithm

Digital Signature Algorithm (DSA) – algorytm kryptografii asymetrycznej zaproponowany w 1991 przez amerykański instytut NIST do wykorzystania w ramach DSS, standardu dla podpisów cyfrowych. Jego bezpieczeństwo opiera się na trudności znalezienia logarytmu dyskretnego w ciele skończonym. NIST opatentował DSA w 1993, umożliwił jednak korzystanie z algorytmu za darmo na całym świecie.

Opublikowana przez NIST w 2023 norma FIPS 186-5 wycofała użycie DSA w podpisach cyfrowych, zalecając w zamian korzystanie z nowszych algorytmów, takich jak ECDSA (opierający się na kryptografii krzywych eliptycznych) lub EdDSA (wykorzystujący krzywe Edwardsa).

Opis algorytmu

Dla systemu wybierana jest pewna funkcja skrótu $H(M)$; norma FIPS 180-4 zaleca korzystanie z SHA-1 lub SHA-2.

Tworzenie kluczy

Klucze tworzone są w następujący sposób:

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

Norma FIPS 186-4 przewiduje dla liczb $(L,N)$ pary wartości: $(1024,160)$, $(2048,224)$, $(2048,256)$ i $(3072,256)$.

Podpis

Podpis składa się z pary liczb $(r,s)$ obliczanych w następujący sposób:

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

Jeżeli $r=0$ lub $s=0$, liczby te powinny zostać obliczone ponownie obierając inną wartość $k$, jest to jednak skrajnie rzadki przypadek.

Weryfikacja podpisu

Niech $M',r',s'$ będą otrzymanymi przez odbiorcę wartościami $M,r,s$. Prawidłowość podpisu można zweryfikować następująco:

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

Jeżeli $v\neq r'$, to znaczy, że otrzymana wiadomość lub podpis zostały zmodyfikowane, nastąpił błąd w implementacji algorytmu po stronie podpisującego albo doszło do próby podrobienia podpisu przez osobę nieznającą klucza prywatnego $x$ domniemanego nadawcy wiadomości.

Bezpieczeństwo

Wybór zmiennej $k$ dla wiadomości jest krytyczny z punktu widzenia bezpieczeństwa implementacji algorytmu, ponieważ nawet niewielkie odchylenia w procesie wyboru mogą zostać wykorzystane w atakach kleptograficznych. Dokument RFC 6979 określa deterministyczną metodę wyboru zmiennej wykorzystując skrót wiadomości $H(M)$ oraz klucz prywatny $x$.

DSA umożliwia przesyłanie informacji podprogowej. Jeżeli zamiast liczby losowej $k$ w podpisie wiadomości wykorzystana zostanie wiadomość podprogowa, a odbiorcy udostępniony zostanie klucz prywatny nadawcy $x$, odbiorca będzie w stanie odczytać wiadomość podprogową. Publiczna weryfikacja podpisu nie umożliwi w tym przypadku odczytania tej informacji.

Zobacz też

• ElGamal
• RSA (kryptografia)