DSA

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. september 2016; kontroller kræver 76 redigeringer .

DSA, digital signaturalgoritme
Skaber	NIST
Oprettet	1991
offentliggjort	1998
Nøglestørrelse	lukket: 160-256 bit, åben: 1024-3072 bit
Signaturstørrelse	to tal på 160-256 bit

DSA ( Digital Signature Algorithm - digital signature algorithm ) - en kryptografisk algoritme , der bruger en privat nøgle (fra et nøglepar: <offentlig; privat>) til at skabe en elektronisk signatur , men ikke til kryptering (i modsætning til RSA og ElGamal-ordningen ). Signaturen oprettes hemmeligt (privat nøgle), men kan verificeres offentligt (offentlig nøgle). Det betyder, at kun ét emne kan oprette en meddelelsessignatur, men enhver kan bekræfte, at den er korrekt. Algoritmen er baseret på den beregningsmæssige kompleksitet ved at tage logaritmer i endelige felter .

Algoritmen blev foreslået af National Institute of Standards and Technology ( USA ) i august 1991 og er patenteret [1] (patentforfatter - David W. Kravitz), NIST gjorde dette patent tilgængeligt til brug uden royalties . DSA er en del af DSS ( Digital Signature Standard), som først blev offentliggjort den 15. december 1998 (dokument FIPS-186 [2] ( Federal Information Processing Standards ) . Standarden er blevet opdateret flere gange [3] [4] , den seneste version er FIPS-186-4 [5] . (juli 2013).

Beskrivelse af algoritmen

DSA omfatter to algoritmer (S, V): at oprette en meddelelsessignatur (S) og at verificere den (V).

Begge algoritmer beregner først meddelelsens hash ved hjælp af en kryptografisk hashfunktion . Algoritme S bruger hash og hemmelig nøgle til at skabe signaturen, algoritme V bruger meddelelseshash, signatur og offentlige nøgle til at bekræfte signaturen.

Det er værd at understrege, at det ikke er meddelelsen (af vilkårlig længde), der faktisk er signeret, men dens hash (160 - 256 bit), derfor er kollisioner uundgåelige , og en signatur er generelt gyldig for flere meddelelser med samme hash . Derfor er valget af en tilstrækkelig "god" hashfunktion meget vigtig for hele systemet som helhed. Den første version af standarden brugte SHA-1 [6] [2] hash-funktionen ( Secure Hash Algorithm - sikker hashing-algoritme) , i den seneste version kan du også bruge enhver algoritme i SHA-2- familien [6] [5 ] . I august 2015 blev FIPS-202 [7] offentliggjort, der beskriver den nye SHA-3 hash-funktion . Men i dag er det ikke inkluderet i DSS-standarden [5] .

Systemet kræver en korrespondancebase mellem forfatterens reelle detaljer (det kan enten være en enkeltperson eller en organisation) og offentlige nøgler , samt alle de nødvendige parametre i den digitale signaturordning (hash-funktion, primtal ). For eksempel kan en certifikatmyndighed fungere som en sådan base .

Indstillinger for digital signaturskema

For at bygge et digitalt signatursystem skal du udføre følgende trin:

Valg af kryptografisk hashfunktion H(x).
Valg af et primtal q , hvis dimension N i bit er den samme som dimensionen i bit af hashværdierne H(x).
At vælge et primtal p således, at (p-1) er deleligt med q . Bitlængden p er angivet med L .
At vælge et tal g ( ) således, at dets multiplikative rækkefølge modulo p er lig med q . For at beregne det, kan du bruge formlen , hvor h er et vilkårligt tal , således at . I de fleste tilfælde opfylder værdien h = 2 dette krav. [5] $g\neq 1$ $g=h^{{(p-1)/q}}\mod s$ $h\in(1;p-1)$ $g\neq 1$

Som nævnt ovenfor er den primære parameter i det digitale signaturskema den kryptografiske hashfunktion, der bruges til at konvertere meddelelsesteksten til et tal , som signaturen beregnes for. En vigtig egenskab ved denne funktion er bitlængden af outputsekvensen, angivet N nedenfor . I den første version af DSS -standarden anbefales SHA-1- funktionen [2] og derfor er bitlængden af det signerede nummer 160 bit. Nu er SHA-1 ikke længere sikker nok [8] [9] . Standarden specificerer følgende mulige værdipar for tallene L og N :

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

Hash-funktioner i SHA-2- familien anbefales under denne standard . Amerikanske regeringsorganisationer skal bruge en af de første tre muligheder, CA'er skal bruge et par, der er lig med eller større end det par, der bruges af abonnenter [5] . Systemdesigneren kan vælge enhver gyldig hashfunktion. Der vil derfor ikke blive fokuseret yderligere på brugen af en bestemt hashfunktion.

Styrken af et DSA-baseret kryptosystem overstiger ikke styrken af den anvendte hashfunktion og styrken af parret (L,N), hvis styrke ikke er større end styrken af hvert af tallene separat. Det er også vigtigt at overveje, hvor længe systemet skal forblive sikkert. I øjeblikket anbefales en længde på 2048 (3072) bit for systemer, der skal være vedvarende indtil 2010 ( 2030 ). [5] [10]

Offentlige og private nøgler

Den hemmelige nøgle er et tal $x\in(0,q)$
Den offentlige nøgle beregnes ved hjælp af formlen $y=g^{x}\mod s$

De offentlige parametre er tal (p, q, g, y) . Der er kun én privat parameter - tallet x . I dette tilfælde kan tallene (p, q, g) være fælles for en gruppe brugere, og tallene x og y er henholdsvis en bestemt brugers private og offentlige nøgler. Ved underskrift af en meddelelse anvendes hemmelige numre x og k , og tallet k skal vælges tilfældigt (i praksis pseudo-tilfældigt) ved beregning af signaturen for hver næste meddelelse.

Da (p, q, g) kan bruges til flere brugere, opdeles brugerne i praksis ofte efter nogle kriterier i grupper med det samme (p, q, g) . Derfor kaldes disse parametre for domæneparametre. [5]

Meddelelsessignatur

Meddelelsessignaturen udføres i henhold til følgende algoritme [5] :

At vælge et tilfældigt tal $k\in(0,q)$
beregning $r=(g^{k}\mod p)\mod q$
At vælge en anden k if $r=0$
beregning $s=k^{{-1}}(H(m)+x\cdot r)\mod q$
At vælge en anden k if $s=0$
Signaturen er et par af total længde $(r,s)$ $2N$

Beregningsmæssigt komplekse operationer er eksponentieringsmodulo (beregning ), hvortil der er hurtige algoritmer , hash-beregning , hvor kompleksiteten afhænger af den valgte hashing-algoritme og størrelsen af inputmeddelelsen, og at finde det inverse element ved hjælp af f.eks. den udvidede euklidiske algoritme eller Fermats lille sætning i form . $g^{k}{\bmod {p}}$ $H(x)$ $k^{-1}{\bmod {q))$ $k^{-1}{\bmod {q}}=k^{q-2}{\bmod {q}}$

Signaturbekræftelse

Signaturverifikation udføres i henhold til algoritmen [5] :

1 Beregning 2 Beregning 3 Beregning 4 Beregning 5 Signaturen er korrekt, hvis

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

Når det er markeret, er beregningsmæssigt komplekse operationer to eksponentieringer , en hash-beregning og at finde det inverse element . $g^{u_{1}}y^{u_{2}}$ $H(x)$ $s^{-1}{\bmod {q))$

Skema korrekthed

Denne digitale signaturordning er korrekt i det omfang, en person, der ønsker at verificere signaturens ægthed, altid vil få et positivt resultat i tilfælde af ægthed. Lad os vise det:

For det første, hvis , så af Fermats lille sætning følger det, at . Da g >1 og q er primtal, så skal g have den multiplikative orden q modulo p . $g=h^{{(p-1)/q}}\mod s$ $g^{q}=h^{{p-1}}=1\mod s$

For at underskrive en besked, beregner den

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

Derfor

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

Da g er af orden q , får vi

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}.

Endelig følger rigtigheden af DSA-skemaet af

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

[5]

Arbejdseksempel

Lad os give et eksempel på, hvordan algoritmen fungerer for små tal. Lad hashværdien af vores budskab . $H=9$

Parametergenerering

$H=9_{10}=1001_{2}$
hash længde , så du kan vælge $fire$ $q=11_{10}=1011_{2}$
vælge fordi $p=23$ $23-1=22=2*q$
vælge $g=2^{2}=4$

Oprettelse af nøgler

vælge som hemmelig nøgle $x=7$
derefter den offentlige nøgle $y=g^{x}{\bmod {p}}=4^{7}{\bmod {2}}3=16384{\bmod {2}}3=(712\cdot 23+8) {\bmod {2}}3=8$

Meddelelsessignatur

vælge $k = 3$
derefter $r=(g^{k}{\bmod {p))){\bmod {q}}=(4^{3}{\bmod {2}}3){\bmod {1}}1 =7$
$r\neq 0$ , kom videre
$s=k^{-1}(H(m)+x\cdot r){\bmod {q}}=4(9+7\cdot 7){\bmod {1}}1=1$ , hvor der tages hensyn til at $3^{-1}{\bmod {1}}1=4$
$s\neq 0$ , kom videre
signaturen er et par tal $(r,s)=(7,1)$

Signaturbekræftelse

$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$
modtaget, hvilket betyder, at signaturen er korrekt. $v = r$

Analoger

DSA-algoritmen er baseret på vanskeligheden ved at beregne diskrete logaritmer og er en modifikation af det klassiske ElGamal- skema [11] , hvor meddelelseshashing tilføjes, og alle logaritmer beregnes af , hvilket gør det muligt at gøre signaturen kortere i forhold til analoger. [12] . Baseret på ElGamal-ordningen blev der også bygget andre algoritmer, for eksempel den russiske GOST 34.10-94 , som nu anses for at være forældet. Den blev erstattet af standarden GOST R 34.10-2012 [13] , som bruger en gruppe af punkter i en elliptisk kurve . $mod~q$

En sådan modifikation, dvs. overgangen fra den multiplikative gruppe modulo et primtal til gruppen af elliptiske kurvepunkter findes også for DSA - ECDSA [14] ( Elliptic Curve Digital Signature Algorithm - digital signaturalgoritme på elliptiske kurver) . Det bruges for eksempel i bitcoin-kryptovalutaen til at bekræfte transaktioner. Denne oversættelse giver dig mulighed for at reducere størrelsen på nøglerne uden at ofre sikkerheden - i bitcoin-systemet er størrelsen på den private nøgle 256 bit, og den tilsvarende offentlige nøgle er 512 bit.

En anden almindelig offentlig nøglealgoritme (brugt til både kryptering og digital signatur), RSA (opkaldt efter forfatterne: Rivest , Shamir , Adleman ), er baseret på vanskeligheden ved at faktorisere store tal.

Kryptografisk styrke

Ethvert angreb på algoritmen kan beskrives som følger: en angriber modtager alle offentlige signaturparametre og et bestemt sæt par (meddelelse, signatur) og forsøger ved hjælp af dette sæt at oprette en gyldig signatur for en ny besked, der ikke er repræsenteret i sættet .

Disse angreb kan betinget opdeles i to grupper - for det første kan en angriber forsøge at gendanne den hemmelige nøgle , og så får han straks mulighed for at underskrive enhver besked, og for det andet kan han forsøge at oprette en gyldig signatur til en ny besked uden at direkte gendannelse af den hemmelige nøgle. $x$

Forudsigelighed af en tilfældig parameter

Den ensartede fordeling af den tilfældige parameter er meget vigtig for systemets sikkerhed. Hvis flere på hinanden følgende parameterbit er kendt for en række signaturer, kan den hemmelige nøgle gendannes med stor sandsynlighed. [femten] $k$ $k$

Gentagelse af parameteren for to meddelelser fører til en simpel hacking af systemet. Dette kan ske, når du bruger en dårlig pseudo-tilfældig talgenerator . Denne sårbarhed i PlayStation 3 -systemet gjorde det muligt at signere alle programmer på vegne af Sony . I nogle implementeringer af bitcoin-systemet til Android kan en angriber få adgang til tegnebogen. [16] [17] Begge eksempler brugte ECDSA [14] -systemet .

Hvis den samme parameter blev brugt til to beskeder , så vil deres signaturer have den samme , men forskellige , lad os kalde dem . $m_{1},m_{2}$ $k$ $(r,s)$ $r$ $s$ ${\displaystyle s_{1},s_{2))$

Fra udtrykket for kan vi udtrykke totalen : $s$ $k$

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

Og lig med fælles for forskellige beskeder: $k$

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

Herfra er det nemt at udtrykke den hemmelige nøgle : $x$

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

Eksistentiel forfalskning

Nogle digitale signaturalgoritmer kan angribes af en eksisterende forfalskning (Eksistentiel forfalskning) . Det ligger i, at det for en signatur (enten overhovedet tilfældig eller oprettet efter en eller anden regel) er muligt at oprette en korrekt besked (som dog normalt ikke giver mening) kun ved brug af offentlige parametre.

For DSA-skemaet er signaturen under alle omstændigheder gyldig for en meddelelse med en hash . $r=g^{e}y\mod p\mod q$ $s=r$ $e$ $H(m)=es$

Dette er en af grundene til hash af inputmeddelelsen. Hvis hash-funktionen er valgt korrekt, er DSA-algoritmen beskyttet mod dette angreb, fordi inversionen af den kryptografiske hash-funktion (dvs. for en given konstatering således at ) er beregningsmæssigt vanskelig. [atten] $k$ $m$ $H(m)=k$

Nøglegendannelse

signaturkorrekthedsbetingelsen kan omskrives i en anden form:

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

denne ligning er ækvivalent (fordi den multiplikative rækkefølge af g modulo p er lig med q)

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

så vi kan antage, at for at gendanne nøglen skal angriberen løse et system af ligninger af formen

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

men i dette system er ukendt , og det er alt , hvilket betyder, at antallet af ukendte er én mere end ligningerne, og for enhver er der dem , der opfylder systemet. Da q er et stort primtal, vil et eksponentielt antal par (meddelelse, signatur) være påkrævet til gendannelse. [en] $x$ $k_i$ $x$ $k_i$ $x\mod q$

Signaturforfalskning

Du kan prøve at forfalske en signatur uden at kende den hemmelige nøgle, det vil sige prøve at løse ligningen

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

med hensyn til og . For hver fast , svarer ligningen til at beregne den diskrete logaritme. [en] $r$ $s$ $r$

Algorithm Implementation Verification System

Licensvilkårene giver dig mulighed for at implementere algoritmen i software og hardware. NIST skabte DSAVS [19] ( Eng. The Digital Signature Algorithm Validation System - et system til kontrol af den digitale signaturalgoritme ). DSAVS består af flere compliance test moduler, der tester hver komponent i systemet uafhængigt af de andre. Testede implementeringskomponenter:

Generering af domæneparametre
Kontrollerer domæneindstillinger
Generering af et offentligt-privat nøglepar
Opret en signatur
Signaturbekræftelse

For at teste implementeringen skal udvikleren indsende en ansøgning om test af implementeringen til CMT-laboratoriet ( Cryptographic Module Testing Laboratory ) . [5]

Generering af primtal

DSA-algoritmen kræver to primtal ( og ), så en prime- eller pseudo -prime-generator er nødvendig . $s$ $q$

Shaw-Taylor- algoritmen [20] bruges til at generere primtal .

Pseudoprimer genereres ved hjælp af en hash-funktion, og Miller-Rabins probabilistiske test bruges til at teste for primalitet . En enkelt Luke -primalitetstest kan føjes til den . [5]

Det nødvendige antal iterationer afhænger af længden af de anvendte numre og af verifikationsalgoritmen [5] :

muligheder	kun M-R test	M-R test + Luke test
p: 1024 bit q: 160 bit fejlsandsynlighed $2^{-80}$	40	p: 3 q:19
p: 2048 bit q: 224 bit fejlsandsynlighed $2^{-112}$	56	p: 3 q:24
p: 2048 bit q: 256 bit fejlsandsynlighed $2^{-112}$	56	p: 3 q:27
p: 3072 bit q: 256 bit fejlsandsynlighed $2^{-128}$	64	p: 2 q:27

Generering af tilfældige tal

Algoritmen kræver også en tilfældig eller pseudo-tilfældig talgenerator. Denne generator er nødvendig for at generere en privat brugernøgle x , samt til at generere en hemmelig tilfældig parameter . $k$

Standarden tilbyder forskellige måder at generere pseudo-tilfældige tal ved hjælp af blokcifre eller hash-funktioner. [5] [21]

Noter

↑ 123 patent 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 .
↑ Find kollisioner i den fulde SHA-1 .
↑ Fristartskollision for fuld SHA-1 .
↑ NIST Special Publication 800-57 .
↑ Elgamal, 1985 .
↑ C. P. Schnorr. Effektiv identifikation og signaturer til chipkort // Fremskridt inden for kryptologi - CRYPTO' 89 Proceedings / Gilles Brassard. — New York, NY: Springer, 1990. — S. 239–252 . - ISBN 978-0-387-34805-6 . - doi : 10.1007/0-387-34805-0_22 . Arkiveret fra originalen den 12. april 2022.
↑ GOST R 34.11-2012
↑ 1 2 The Elliptic Curve Digital Signature Algorithm (ECDSA) .
↑ Usikkerheden ved den digitale signaturalgoritme med delvist kendte noncer .
↑ ECDSA - Anvendelses- og implementeringsfejl .
↑ Elliptisk kurvekryptering i praksis .
↑ Sikkerhedsargumenter for digitale signaturer og blinde signaturer .
↑ Valideringssystemet for digital signaturalgoritme .
↑ Generering af stærke primtal .
↑ Generering af tilfældige tal .

Litteratur

Standarder og patenter

FIPS. PUB 186-1 .
FIPS. PUB 186-2 .
FIPS. PUB 186-3 .
FIPS. PUB 186-4 .
FIPS. PUB 180-4 . Arkiveret fra originalen den 26. november 2016.
FIPS. PUB 202 (engelsk) .
FIPS. PUB 202 (engelsk) .
David W. Kravitz. Digital signaturalgoritme 5231668 A (engelsk) .
NIST Special Publication 800-57 Part 1 Revision 4. Recommendation for Key Management .
GOST R 34.10-2012. Informationsteknologi. Kryptografisk beskyttelse af information. Processer for dannelse og verifikation af elektronisk digital signatur . (Russisk)
Valideringssystemet for digital signaturalgoritme .

Artikler

Marc Stevens, Pierre Karpman, Thomas Peyrin. Fristartskollision for fuld SHA- 1 .
NIST Special Publication 800-90A anbefaling for generering af tilfældige tal ved brug af deterministiske tilfældige bitgeneratorer .
J. Shawe-Taylor. Generer stærke primtal .
Xiaoyun Wang, Yiqun Lisa, Hongbo Yu. Find kollisioner i den fulde SHA-1 .
Phong Q. Nguyen, Igor E. Shparlinski. Usikkerheden ved den digitale signaturalgoritme med delvist kendte nonces .
David Pointcheval, Jacques Stern. Sikkerhedsargumenter for digitale signaturer og blinde signaturer .
Markus Schmid. ECDSA - Anvendelses- og implementeringsfejl .
Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA ) .
Elgamal T. Et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer, et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1985. - Vol. 31, Iss. 4. - S. 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. Elliptisk kurvekryptering i praksis .

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort