DSA

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 12 septembrie 2016; verificările necesită 76 de modificări .

DSA, algoritm de semnătură digitală
Creator	NIST
Creată	1991
publicat	1998
Dimensiunea cheii	închis: 160-256 biți, deschis: 1024-3072 biți
Dimensiunea semnăturii	două numere de 160-256 de biți

DSA ( Digital Signature Algorithm - algoritm de semnătură digitală ) - un algoritm criptografic care utilizează o cheie privată (de la o pereche de chei: <public; private>) pentru a crea o semnătură electronică , dar nu pentru criptare (spre deosebire de RSA și schema ElGamal ). Semnătura este creată în secret (cheie privată), dar poate fi verificată public (cheie publică). Aceasta înseamnă că un singur subiect poate crea o semnătură de mesaj, dar oricine poate verifica dacă este corectă. Algoritmul se bazează pe complexitatea de calcul a luării de logaritmi în câmpuri finite .

Algoritmul a fost propus de Institutul Național de Standarde și Tehnologie ( SUA ) în august 1991 și este brevetat [1] (autorul brevetului - David W. Kravitz), NIST a făcut acest brevet disponibil pentru utilizare fără drepturi de autor . DSA face parte din DSS ( Digital Signature Standard), publicat pentru prima dată la 15 decembrie 1998 (document FIPS-186 [2] ( Federal Information Processing Standards ) . Standardul a fost actualizat de mai multe ori [3] [4] , cea mai recentă versiune este FIPS-186-4 [5] . (Iulie 2013).

Descrierea algoritmului

DSA include doi algoritmi (S, V): pentru a crea o semnătură de mesaj (S) și pentru a o verifica (V).

Ambii algoritmi calculează mai întâi hash -ul mesajului folosind o funcție hash criptografică . Algoritmul S folosește hash și cheia secretă pentru a crea semnătura, algoritmul V folosește hash-ul mesajului, semnătura și cheia publică pentru a verifica semnătura.

Merită să subliniem că nu mesajul (de lungime arbitrară) este semnat efectiv, ci hash-ul său (160 - 256 biți), prin urmare coliziunile sunt inevitabile și o singură semnătură, în general, este valabilă pentru mai multe mesaje cu același hash. . Prin urmare, alegerea unei funcții hash suficient de „bună” este foarte importantă pentru întregul sistem în ansamblu. Prima versiune a standardului a folosit funcția hash SHA-1 [6] [2] ( Secure Hash Algorithm - secure hashing algorithm) , în cea mai recentă versiune puteți folosi și orice algoritm din familia SHA-2 [6] [5 ] . În august 2015, a fost publicat FIPS-202 [7] , care descrie noua funcție hash SHA-3 . Dar astăzi nu este inclus în standardul DSS [5] .

Sistemul necesită o bază de corespondență între detaliile reale ale autorului (pot fi fie o persoană fizică, fie o organizație) și cheile publice , precum și toți parametrii necesari ai schemei de semnătură digitală (funcția hash, numere prime ). De exemplu, o autoritate de certificare poate servi drept bază .

Opțiuni pentru schema de semnătură digitală

Pentru a construi un sistem de semnătură digitală, trebuie să efectuați următorii pași:

Alegerea funcției hash criptografice H(x).
Alegerea unui număr prim q a cărui dimensiune N în biți este aceeași cu dimensiunea în biți a valorilor hash H(x).
Alegerea unui număr prim p astfel încât (p-1) să fie divizibil cu q . Lungimea bitului p este notată cu L .
Alegerea unui număr g ( ) astfel încât ordinea lui multiplicativă modulo p să fie egală cu q . Pentru a-l calcula, puteți folosi formula , unde h este un număr arbitrar astfel încât . În cele mai multe cazuri, valoarea h = 2 satisface această cerință. [5] $g\neq 1$ $g=h^{{(p-1)/q}}\mod p$ $h\in(1;p-1)$ $g\neq 1$

După cum sa menționat mai sus, parametrul principal al schemei de semnătură digitală este funcția hash criptografică utilizată pentru a converti textul mesajului într-un număr pentru care este calculată semnătura. O caracteristică importantă a acestei funcții este lungimea de biți a secvenței de ieșire, notată cu N mai jos . În prima versiune a standardului DSS , se recomandă funcția SHA-1 [2] și, în consecință, lungimea de biți a numărului cu semn este de 160 de biți. Acum SHA-1 nu mai este suficient de sigur [8] [9] . Standardul specifică următoarele perechi posibile de valori pentru numerele L și N :

L=1024, N=160
L=2048, N=224
L=2048, N=256
L=3072, N=256

Funcțiile hash ale familiei SHA-2 sunt recomandate conform acestui standard . Organizațiile guvernamentale din SUA trebuie să utilizeze una dintre primele trei opțiuni, CA trebuie să utilizeze o pereche egală sau mai mare decât perechea utilizată de abonați [5] . Proiectantul de sistem poate alege orice funcție hash validă. Prin urmare, o atenție suplimentară nu se va concentra asupra utilizării unei anumite funcții hash.

Puterea unui criptosistem bazat pe DSA nu depășește puterea funcției hash utilizată și puterea perechii (L,N), a cărei putere nu este mai mare decât puterea fiecăruia dintre numere separat. De asemenea, este important să se ia în considerare cât timp trebuie să rămână sigur sistemul. În prezent, pentru sistemele care trebuie să fie persistente până în 2010 ( 2030 ), se recomandă o lungime de 2048 (3072) biți. [5] [10]

Chei publice și private

Cheia secretă este un număr $x\in(0,q)$
Cheia publică se calculează folosind formula $y=g^{x}\mod p$

Parametrii publici sunt numerele (p, q, g, y) . Există un singur parametru privat - numărul x . În acest caz, numerele (p, q, g) pot fi comune pentru un grup de utilizatori, iar numerele x și y sunt cheile private și, respectiv, publice ale unui anumit utilizator. La semnarea unui mesaj se folosesc numerele secrete x și k , iar numărul k trebuie ales aleatoriu (în practică, pseudoaleatoriu) la calcularea semnăturii fiecărui mesaj următor.

Deoarece (p, q, g) poate fi utilizat pentru mai mulți utilizatori, în practică utilizatorii sunt adesea împărțiți în funcție de anumite criterii în grupuri cu același (p, q, g) . Prin urmare, acești parametri sunt numiți Parametri de domeniu. [5]

Semnătura mesajului

Semnătura mesajului se realizează conform următorului algoritm [5] :

Alegerea unui număr aleatoriu $k\in(0,q)$
calcul $r=(g^{k}\mod p)\mod q$
Alegând un alt k dacă $r=0$
calcul $s=k^{{-1}}(H(m)+x\cdot r)\mod q$
Alegând un alt k dacă $s=0$
Semnătura este o pereche de lungime totală $(r,s)$ $2N$

Operațiile complexe din punct de vedere computațional sunt modul de exponențiere (calcul ), pentru care există algoritmi rapizi , calculul hash , unde complexitatea depinde de algoritmul de hashing ales și de dimensiunea mesajului de intrare și găsirea elementului invers folosind, de exemplu, euclidianul extins. algoritm sau mica teoremă a lui Fermat în formă . $g^{k}{\bmod {p}}$ $H(x)$ $k^{-1}{\bmod {q)}$ $k^{-1}{\bmod {q}}=k^{q-2}{\bmod {q}}$

Verificarea semnăturii

Verificarea semnăturii se realizează conform algoritmului [5] :

1 Calcul 2 Calcul 3 Calcul 4 Calculul 5 Semnătura este corectă dacă

w=s^{{-1}}\mod q

u_{1}=H(m)\cdot w\mod q

u_{2}=r\cdot w\mod q

v=(g^{{u_{1}}}\cdot y^{{u_{2}}}\mod p)\mod q

v=r

Când sunt verificate, operațiile complexe din punct de vedere computațional sunt două exponențiații , un calcul hash și găsirea elementului invers . $g^{u_{1}}y^{u_{2}}$ $H(x)$ $s^{-1}{\bmod {q)}$

Corectitudinea schemei

Această schemă de semnătură digitală este corectă în măsura în care o persoană care dorește să verifice autenticitatea semnăturii va primi întotdeauna un rezultat pozitiv în caz de autenticitate. Să-l arătăm:

În primul rând, dacă , atunci după Mica Teoremă a lui Fermat rezultă că . Deoarece g >1 și q este prim, atunci g trebuie să aibă ordinea multiplicativă q modulo p . $g=h^{{(p-1)/q}}\mod p$ $g^{q}=h^{{p-1}}=1\mod p$

Pentru a semna un mesaj, calculează

s=k^{{-1}}(H(m)+x\cdot r)\mod {q}.

Prin urmare

k=H(m)\cdot s^{{-1}}+x\cdot r\cdot s^{{-1}}=H(m)\cdot w+x\cdot r\cdot w\mod { q}.

Deoarece g este de ordinul q , obținem

g^{k}=g^{{H(m)\cdot w\mod q}}g^{{x\cdot r\cdot w\mod q}}=g^{{H(m)\cdot w \mod q}}y^{{r\cdot w\mod q}}=g^{{u1}}y^{{u2}}\mod {p}.

În cele din urmă, corectitudinea schemei DSA rezultă din

r=(g^{k}\mod p)\mod q=(g^{{u1}}y^{{u2}}\mod p)\mod q=v.

[5]

Exemplu de lucru

Să dăm un exemplu despre cum funcționează algoritmul pentru numere mici. Lăsați valoarea hash a mesajului nostru . $H=9$

Generarea parametrilor

$H=9_{10}=1001_{2}$
lungime hash , astfel încât să puteți alege $patru$ $q=11_{10}=1011_{2}$
alege pentru că $p=23$ $23-1=22=2*q$
alege $g=2^{2}=4$

Crearea cheilor

alege ca cheie secretă $x=7$
apoi cheia publică $y=g^{x}{\bmod {p}}=4^{7}{\bmod {2}}3=16384{\bmod {2}}3=(712\cdot 23+8) {\bmod {2}}3=8$

Semnătura mesajului

alege $k = 3$
apoi $r=(g^{k}{\bmod {p))}{\bmod {q}}=(4^{3}{\bmod {2}}3){\bmod {1}}1 =7$
$r\neq 0$ , mergi mai departe
$s=k^{-1}(H(m)+x\cdot r){\bmod {q}}=4(9+7\cdot 7){\bmod {1}}1=1$ , unde se are în vedere că $3^{-1}{\bmod {1}}1=4$
$s\neq 0$ , mergi mai departe
semnătura este o pereche de numere $(r,s)=(7,1)$

Verificarea semnăturii

$w=s^{-1}{\bmod {q}}=1^{-1}{\bmod {1}}1=1$
$u_{1}=H(m)\cdot w{\bmod {q}}=9\cdot 1{\bmod {1}}1=9$
$u_{2}=r\cdot w{\bmod {q}}=7\cdot 1{\bmod {1}}1=7$
$v=(g^{u_{1}}\cdot y^{u_{2}}{\bmod {p}}){\bmod {q}}=(4^{9}\cdot 8^ {7}{\bmod {2}}3){\bmod {1}}1=7$
primit, ceea ce înseamnă că semnătura este corectă. $v = r$

Analogii

Algoritmul DSA se bazează pe dificultatea calculării logaritmilor discreti și este o modificare a schemei clasice ElGamal [11] , unde se adaugă hashingul mesajelor, iar toți logaritmii sunt calculati prin , ceea ce face posibilă scurtarea semnăturii în comparație cu analogii. [12] . Pe baza schemei ElGamal, au fost construiți și alți algoritmi, de exemplu, GOST rusesc 34.10-94 , care este acum considerat învechit. A fost înlocuit cu standardul GOST R 34.10-2012 [13] , care utilizează un grup de puncte dintr- o curbă eliptică . $mod~q$

O astfel de modificare, adică trecerea de la grupul multiplicativ modulo un număr prim la grupul de puncte de curbă eliptică există și pentru DSA - ECDSA [14] ( Elliptic Curve Digital Signature Algorithm - digital signature algorithm on elliptic curves) . Este folosit, de exemplu, în criptomoneda bitcoin pentru a confirma tranzacțiile. Această traducere vă permite să reduceți dimensiunea cheilor fără a sacrifica securitatea - în sistemul bitcoin, dimensiunea cheii private este de 256 de biți, iar cheia publică corespunzătoare este de 512 biți.

Un alt algoritm comun cu cheie publică (folosit atât pentru criptare, cât și pentru semnătura digitală), RSA (numit după autorii: Rivest , Shamir , Adleman ), se bazează pe dificultatea factorizării numerelor mari.

Puterea criptografică

Orice atac asupra algoritmului poate fi descris astfel: un atacator primește toți parametrii de semnătură publică și un anumit set de perechi (mesaj, semnătură) și încearcă, folosind acest set, să creeze o semnătură validă pentru un mesaj nou care nu este reprezentat în set. .

Aceste atacuri pot fi împărțite condiționat în două grupuri - în primul rând, un atacator poate încerca să recupereze cheia secretă și apoi are imediat posibilitatea de a semna orice mesaj și, în al doilea rând, poate încerca să creeze o semnătură validă pentru un mesaj nou fără recuperând direct cheia secretă. $X$

Predictibilitatea unui parametru aleatoriu

Distribuția uniformă a parametrului aleatoriu este foarte importantă pentru securitatea sistemului. Dacă sunt cunoscuți mai mulți biți de parametri consecutivi pentru o serie de semnături, atunci cheia secretă poate fi recuperată cu mare probabilitate. [cincisprezece] $k$ $k$

Repetarea parametrului pentru două mesaje duce la o simplă hacking a sistemului. Acest lucru se poate întâmpla atunci când utilizați un generator de numere pseudo-aleatoare prost . Această vulnerabilitate a sistemului PlayStation 3 a permis semnarea oricăror programe în numele Sony . În unele implementări ale sistemului bitcoin pentru Android, un atacator ar putea obține acces la portofel. [16] [17] Ambele exemple au folosit sistemul ECDSA [14] .

Dacă același parametru a fost folosit pentru două mesaje , atunci semnăturile lor vor avea aceleași , dar diferite , să le numim . $m_{1},m_{2}$ $k$ $(r,s)$ $r$ $s$ $s_{1},s_{2)$

Din expresia pentru putem exprima totalul : $s$ $k$

$k=(H(m)+xr)s^{-1}\mod q$ .

Și echivalează comun pentru diferite mesaje: $k$

$(H(m_{1})+xr)s_{1}^{-1}\mod q=(H(m_{2})+xr)s_{2}^{-1}\mod q$

De aici este ușor să exprimați cheia secretă : $X$

$x={\frac {H(m_{1})s_{1}^{-1}-H(m_{2})s_{2}^{-1}}{r(s_{2} ^{-1}-s_{1}^{-1})}}$

Fals existențial

Unii algoritmi de semnătură digitală pot fi atacați de un fals existent (fals existent) . Constă în faptul că pentru o semnătură (fie aleatorie, fie creată după o anumită regulă) este posibil să se creeze un mesaj corect (care, totuși, de obicei nu are sens) folosind doar parametri publici.

Pentru schema DSA , semnătura , în orice caz , este valabilă pentru un mesaj cu hash . $r=g^{e}y\mod p\mod q$ $s=r$ $e$ $H(m)=es$

Acesta este unul dintre motivele pentru hashing mesajul de intrare. Dacă funcția hash este aleasă corect, algoritmul DSA este protejat de acest atac, deoarece inversarea funcției hash criptografice (adică, pentru o constatare dată astfel încât ) este dificilă din punct de vedere computațional. [optsprezece] $k$ $m$ $H(m)=k$

Recuperarea cheii

condiția de corectitudine a semnăturii poate fi rescrisă într-o formă diferită:

$g^{ks}\mod p\mod q=g^{H(m)+xr}\mod p\mod q$

această ecuație este echivalentă (deoarece ordinea multiplicativă a lui g modulo p este egală cu q)

$H(m)\mod q=ks-xr\mod q$

deci putem presupune că, pentru a recupera cheia, atacatorul trebuie să rezolve un sistem de ecuații de forma

$H(m_{i})\mod q=k_{i}s_{i}-xr_{i}\mod q$

dar în acest sistem este necunoscut și atât , ceea ce înseamnă că numărul de necunoscute este cu unul mai mult decât ecuațiile, iar pentru oricare sunt cele care satisfac sistemul. Deoarece q este un număr prim mare, va fi necesar un număr exponențial de perechi (mesaj, semnătură) pentru recuperare. [unu] $X$ $k_i$ $X$ $k_i$ $x\mod q$

Falsificarea semnăturii

Puteți încerca să falsificați o semnătură fără să cunoașteți cheia secretă, adică să încercați să rezolvați ecuația

$r^{s}\mod p\mod q=g^{H(m)}y^{r}\mod p\mod q$

cu privire la și . Pentru fiecare fix , ecuația este echivalentă cu calcularea logaritmului discret. [unu] $r$ $s$ $r$

Sistemul de verificare a implementării algoritmului

Termenii licenței vă permit să implementați algoritmul în software și hardware. NIST a creat DSAVS [19] ( Eng. The Digital Signature Algorithm Validation System - un sistem de verificare a algoritmului de semnătură digitală ). DSAVS constă din mai multe module de testare a conformității care testează fiecare componentă a sistemului independent de celelalte. Componente de implementare testate:

Generarea parametrilor de domeniu
Verificarea setărilor domeniului
Generarea unei perechi de chei public-private
Creați o semnătură
Verificarea semnăturii

Pentru a testa implementarea, dezvoltatorul trebuie să depună o cerere de testare a implementării acesteia la laboratorul CMT ( Cryptographic Module Testing Laboratory ) . [5]

Generarea numerelor prime

Algoritmul DSA necesită două numere prime ( și ), deci este necesar un generator prime sau pseudo -prime . $p$ $q$

Algoritmul Shaw-Taylor [20] este folosit pentru a genera numere prime .

Pseudoprimele sunt generate folosind o funcție hash și testul probabilistic Miller-Rabin este utilizat pentru a testa primalitatea . I se poate adăuga un singur test de primalitate Luke . [5]

Numărul necesar de iterații depinde de lungimea numerelor utilizate și de algoritmul de verificare [5] :

Opțiuni	doar test M-R	Test M-R + test Luke
p: 1024 biți q: 160 de biți probabilitatea de eroare $2^{-80}$	40	p: 3 q:19
p: 2048 biți q: 224 de biți probabilitatea de eroare $2^{-112}$	56	p: 3 q:24
p: 2048 biți q: 256 de biți probabilitatea de eroare $2^{-112}$	56	p: 3 q:27
p: 3072 biți q: 256 de biți probabilitatea de eroare $2^{-128}$	64	p: 2 q:27

Generarea numerelor aleatorii

Algoritmul necesită, de asemenea, un generator de numere aleatoare sau pseudo-aleatoare . Acest generator este necesar pentru a genera o cheie de utilizator privată x , precum și pentru a genera un parametru secret aleatoriu . $k$

Standardul oferă diverse modalități de a genera numere pseudoaleatoare folosind cifruri bloc sau funcții hash. [5] [21]

Note

^ 123 Brevet US 5231668 A.
↑ 123 FIPS 186-1 . _
↑ FIPS 186-2 .
↑ FIPS 186-3 .
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 FIPS 186-4 .
↑ 12 FIPS 180-4 .
↑ FIPS 202 .
↑ Găsirea coliziunilor în SHA-1 complet .
↑ Coliziune Freestart pentru SHA-1 complet .
↑ Publicația specială NIST 800-57 .
↑ Elgamal, 1985 .
↑ C. P. Schnorr. Identificare și semnături eficiente pentru carduri inteligente // Progrese în criptologie - CRYPTO' 89 Proceedings / Gilles Brassard. — New York, NY: Springer, 1990. — P. 239–252 . - ISBN 978-0-387-34805-6 . - doi : 10.1007/0-387-34805-0_22 . Arhivat din original pe 12 aprilie 2022.
↑ GOST R 34.11-2012
↑ 1 2 Algoritmul de semnătură digitală cu curbă eliptică (ECDSA) .
↑ Insecuritatea algoritmului de semnătură digitală cu non-uri parțial cunoscute .
↑ ECDSA - Eșecuri de aplicare și implementare .
↑ Criptografia cu curbă eliptică în practică .
↑ Argumente de securitate pentru semnăturile digitale și semnăturile oarbe .
↑ Sistemul de validare a algoritmului de semnătură digitală .
↑ Generarea de numere prime puternice .
↑ Generarea numerelor aleatorii .

Literatură

Standarde și brevete

FIPS. PUB 186-1 .
FIPS. PUB 186-2 .
FIPS. PUB 186-3 .
FIPS. PUB 186-4 .
FIPS. PUB 180-4 . Arhivat din original pe 26 noiembrie 2016.
FIPS. PUB 202 (engleză) .
FIPS. PUB 202 (engleză) .
David W. Kravitz. Algoritm de semnătură digitală 5231668 A (engleză) .
Publicația specială NIST 800-57 Partea 1 Revizia 4. Recomandare pentru managementul cheilor .
GOST R 34.10-2012. Tehnologia de informație. Protecția criptografică a informațiilor. Procese de formare şi verificare a semnăturii digitale electronice . (Rusă)
Sistemul de validare a algoritmului de semnătură digitală .

Articole

Marc Stevens, Pierre Karpman, Thomas Peyrin. Coliziune Freestart pentru SHA- 1 complet .
Publicația specială NIST 800-90A Recomandare pentru generarea numerelor aleatoare utilizând generatoare de biți aleatorii determinist .
J. Shawe-Taylor. Generarea de numere prime puternice .
Xiaoyun Wang, Yiqun Lisa, Hongbo Yu. Găsirea coliziunilor în SHA-1 complet .
Phong Q. Nguyen, Igor E. Shparlinski. Insecuritatea algoritmului de semnătură digitală cu non-uri parțial cunoscute .
David Pointcheval, Jacques Stern. Argumente de securitate pentru semnăturile digitale și semnăturile oarbe .
Markus Schmid. ECDSA - Eșecuri de aplicare și implementare .
Don Johnson, Alfred Menezes, Scott Vanstone. Algoritmul de semnătură digitală cu curbă eliptică (ECDSA ) .
Elgamal T. Un criptosistem cu cheie publică și o schemă de semnătură bazată pe logaritmi discreti, un criptosistem cu cheie publică și o schemă de semnătură bazată pe logaritmi discreti // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1985. - Vol. 31, Iss. 4. - P. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Joppe W. Bos, J. Alex Halderman, Nadia Heninger, Jonathan Moore, Michael Naehrig, Eric Wustrow. Criptografia cu curbă eliptică în practică .

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP