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^[1].

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)^[2].

Opis algorytmu

Dla systemu wybierana jest pewna funkcja skrótu ${\displaystyle H(M)}$; norma FIPS 180-4 zaleca korzystanie z SHA-1 lub SHA-2^[3].

Tworzenie kluczy

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)}$ pary wartości: ${\displaystyle (1024,160)}$, ${\displaystyle (2048,224)}$, ${\displaystyle (2048,256)}$ i ${\displaystyle (3072,256)}$^[4].

Podpis

Podpis składa się z pary liczb ${\displaystyle (r,s)}$ obliczanych w następujący sposób:^[4]

• 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}$ lub ${\displaystyle s=0}$, liczby te powinny zostać obliczone ponownie obierając inną wartość ${\displaystyle k}$, jest to jednak skrajnie rzadki przypadek.

Weryfikacja podpisu

Niech ${\displaystyle M',r',s'}$ będą otrzymanymi przez odbiorcę wartościami ${\displaystyle M,r,s}$. Prawidłowość podpisu można zweryfikować następująco:^[4]

• 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'}$, 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 ${\displaystyle x}$ domniemanego nadawcy wiadomości.

Bezpieczeństwo

Wybór zmiennej ${\displaystyle 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 ${\displaystyle H(M)}$ oraz klucz prywatny ${\displaystyle x}$^[5].

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

Zobacz też

• ElGamal
• RSA (kryptografia)