Digital Signature Algorithm

Digital Signature Algorithm
DSA
Rodzaj algorytmu	kryptografia asymetryczna, algorytm podpisu cyfrowego
Data stworzenia	1991
Autorzy	NIST
Długość klucza	od 1024/160 do 3072/256 (L/N) [bit]
Data złamania	2023
Skuteczne ataki	ataki kleptograficzne przy niewłaściwym wyborze zmiennej k

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ż

Przypisy

↑ Reported Statement from NIST regarding use of DSA. IETF Datatracker, 1993-07-23. [dostęp 2025-07-10]. (ang.).
↑ FIPS PUB 186-5: Digital Signature Standard (DSS), National Institute of Standards and Technology, 3 lutego 2023, s. 16 [dostęp 2025-07-09] (ang.).
↑ FIPS PUB 180-4: Secure Hash Standard (SHS), National Institute of Standards and Technology, sierpień 2015, s. 10 [dostęp 2025-07-09] (ang.).
1 2 3 4 FIPS PUB 186-4: Digital Signature Standard (DSS), National Institute of Standards and Technology, 19 lipca 2013, s. 15-21, 41-42 [dostęp 2025-07-09] (ang.).
↑ T.T. Pornin T.T., Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), RFC 6979, IETF, sierpień 2013, DOI: 10.17487/RFC6979, ISSN 2070-1721, OCLC 943595667 (ang.).
↑ Brunon Hołyst, Jacek Pomykała. Kryminalistyczne metody ujawnialności przekazów kryptograficznych. „Prokuratura i Prawo”. 5, s. 15, 2008. (pol.).

[ipr-1] Reported Statement from NIST regarding use of DSA. IETF Datatracker, 1993-07-23. [dostęp 2025-07-10]. (ang.).

[fips186-5-2] FIPS PUB 186-5: Digital Signature Standard (DSS), National Institute of Standards and Technology, 3 lutego 2023, s. 16 [dostęp 2025-07-09] (ang.).

[fips180-4-3] FIPS PUB 180-4: Secure Hash Standard (SHS), National Institute of Standards and Technology, sierpień 2015, s. 10 [dostęp 2025-07-09] (ang.).

[fips186-4-4] 1 2 3 4 FIPS PUB 186-4: Digital Signature Standard (DSS), National Institute of Standards and Technology, 19 lipca 2013, s. 15-21, 41-42 [dostęp 2025-07-09] (ang.).

[rfc-5] T.T. Pornin T.T., Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), RFC 6979, IETF, sierpień 2013, DOI: 10.17487/RFC6979, ISSN 2070-1721, OCLC 943595667 (ang.).

[pip-6] Brunon Hołyst, Jacek Pomykała. Kryminalistyczne metody ujawnialności przekazów kryptograficznych. „Prokuratura i Prawo”. 5, s. 15, 2008. (pol.).