Digital Signature Algorithm

From Quire, the open reference··2 min read

Digital Signature Algorithm
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^[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#edit

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#edit

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#edit

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#edit

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#edit

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ż#edit

Przypisy#edit

^ 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.).
^ a b c d 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. Pornin, 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.).

This article is mirrored from “Digital Signature Algorithm” on Polski Wikipedia, revision 80629946, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 80629946 · just now