DSA

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 12 september 2016; kontroller kräver 76 redigeringar .

DSA, Digital Signatur Algorithm
Skapare	NIST
Skapad	1991
publiceras	1998
Nyckelstorlek	stängd: 160-256 bitar, öppen: 1024-3072 bitar
Signaturstorlek	två nummer på 160-256 bitar

DSA ( Digital Signature Algorithm - digital signature algorithm ) - en kryptografisk algoritm som använder en privat nyckel (från ett nyckelpar: <public; private>) för att skapa en elektronisk signatur , men inte för kryptering (till skillnad från RSA och ElGamal-schemat ) . Signaturen skapas i hemlighet (privat nyckel) men kan verifieras offentligt (offentlig nyckel). Det betyder att endast ett ämne kan skapa en meddelandesignatur, men vem som helst kan verifiera att den är korrekt. Algoritmen är baserad på beräkningskomplexiteten för att ta logaritmer i ändliga fält .

Algoritmen föreslogs av National Institute of Standards and Technology ( USA ) i augusti 1991 och är patenterad [1] (patentförfattare - David W. Kravitz), NIST gjorde detta patent tillgängligt för användning utan royalties . DSA är en del av DSS ( Digital Signature Standard), först publicerad den 15 december 1998 (dokument FIPS-186 [2] ( Federal Information Processing Standards ) . Standarden har uppdaterats flera gånger [3] [4] , den senaste versionen är FIPS-186-4 [5] . (Juli 2013).

Beskrivning av algoritmen

DSA inkluderar två algoritmer (S, V): för att skapa en meddelandesignatur (S) och för att verifiera den (V).

Båda algoritmerna beräknar först meddelandets hash med hjälp av en kryptografisk hashfunktion . Algoritm S använder hash och hemlig nyckel för att skapa signaturen, algoritm V använder meddelandehash, signatur och publik nyckel för att verifiera signaturen.

Det är värt att betona att det inte är meddelandet (av godtycklig längd) som faktiskt är signerat, utan dess hash (160 - 256 bitar), därför är kollisioner oundvikliga och en signatur är generellt sett giltig för flera meddelanden med samma hash . Därför är valet av en tillräckligt "bra" hashfunktion mycket viktigt för hela systemet som helhet. Den första versionen av standarden använde hashfunktionen SHA-1 [6] [2] ( Secure Hash Algorithm - säker hashalgoritm) , i den senaste versionen kan du även använda valfri algoritm i SHA-2- familjen [6] [5 ] . I augusti 2015 publicerades FIPS-202 [7] som beskriver den nya SHA-3- hashfunktionen . Men idag ingår det inte i DSS-standarden [5] .

Systemet kräver en korrespondensbas mellan författarens verkliga detaljer (det kan vara antingen en individ eller en organisation) och offentliga nycklar , såväl som alla nödvändiga parametrar för det digitala signaturschemat (hashfunktion, primtal ). Till exempel kan en certifikatutfärdare fungera som en sådan bas .

Alternativ för digital signaturschema

För att bygga ett digitalt signatursystem måste du utföra följande steg:

Val av kryptografisk hashfunktion H(x).
Att välja ett primtal q vars dimension N i bitar är samma som dimensionen i bitar av hash-värdena H(x).
Att välja ett primtal p så att (p-1) är delbart med q . Bitlängden p betecknas med L .
Att välja ett tal g ( ) så att dess multiplikationsordning modulo p är lika med q . För att beräkna det kan du använda formeln , där h är ett godtyckligt tal så att . I de flesta fall uppfyller värdet h = 2 detta krav. [5] $g\neq 1$ $g=h^{{(p-1)/q}}\mod sid$ $h\in(1;p-1)$ $g\neq 1$

Som nämnts ovan är den primära parametern för det digitala signaturschemat den kryptografiska hashfunktionen som används för att omvandla meddelandetexten till ett tal för vilket signaturen beräknas. En viktig egenskap hos denna funktion är bitlängden för utdatasekvensen, betecknad N nedan . I den första versionen av DSS -standarden rekommenderas SHA-1- funktionen [2] och därför är bitlängden på det signerade numret 160 bitar. Nu är SHA-1 inte längre tillräckligt säker [8] [9] . Standarden specificerar följande möjliga värdepar för talen L och N :

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

Hash-funktioner i SHA-2- familjen rekommenderas under denna standard . Amerikanska statliga organisationer måste använda ett av de tre första alternativen, CA:er måste använda ett par som är lika med eller större än det par som används av abonnenter [5] . Systemdesignern kan välja vilken giltig hashfunktion som helst. Därför kommer ytterligare uppmärksamhet inte att fokuseras på användningen av en viss hashfunktion.

Styrkan hos ett DSA-baserat kryptosystem överstiger inte styrkan hos hashfunktionen som används och styrkan hos paret (L,N), vars styrka inte är större än styrkan för vart och ett av talen separat. Det är också viktigt att överväga hur länge systemet måste vara säkert. För närvarande rekommenderas en längd på 2048 (3072) bitar för system som måste vara beständiga fram till 2010 ( 2030 ). [5] [10]

Offentliga och privata nycklar

Den hemliga nyckeln är ett nummer $x\in(0,q)$
Den publika nyckeln beräknas med hjälp av formeln $y=g^{x}\mod sid$

De publika parametrarna är siffror (p, q, g, y) . Det finns bara en privat parameter - talet x . I det här fallet kan siffrorna (p, q, g) vara gemensamma för en grupp användare, och siffrorna x och y är privata respektive publika nycklar för en viss användare. Vid signering av ett meddelande används hemliga nummer x och k och numret k måste väljas slumpmässigt (i praktiken pseudoslumpmässigt) vid beräkning av signaturen för varje nästa meddelande.

Eftersom (p, q, g) kan användas för flera användare, delas i praktiken användare ofta in enligt vissa kriterier i grupper med samma (p, q, g) . Därför kallas dessa parametrar för domänparametrar. [5]

Meddelandesignatur

Meddelandesignaturen utförs enligt följande algoritm [5] :

Att välja ett slumpmässigt tal $k\in(0,q)$
beräkning $r=(g^{k}\mod p)\mod q$
Att välja ett annat k if $r=0$
beräkning $s=k^{{-1}}(H(m)+x\cdot r)\mod q$
Att välja ett annat k if $s=0$
Signaturen är ett par med total längd $(r,s)$ $2N$

Beräkningskomplexa operationer är exponentieringsmodulo (beräkning ), för vilken det finns snabba algoritmer , hashberäkning , där komplexiteten beror på den valda hashalgoritmen och storleken på inmatningsmeddelandet, och att hitta det inversa elementet med hjälp av till exempel den utökade euklidiska algoritm eller Fermats lilla sats i form . $g^{k}{\bmod {p}}$ $H(x)$ $k^{-1}{\bmod {q))$ $k^{-1}{\bmod {q}}=k^{q-2}{\bmod {q}}$

Signaturverifiering

Signaturverifiering utförs enligt algoritmen [5] :

1 Beräkning 2 Beräkning 3 Beräkning 4 Beräkning 5 Signaturen är korrekt om

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 är markerat är beräkningskomplexa operationer två exponentieringar , en hashberäkning och att hitta det inversa elementet . $g^{u_{1}}y^{u_{2}}$ $H(x)$ $s^{-1}{\bmod {q))$

Schema korrekthet

Detta digitala signaturschema är korrekt i den mån att en person som vill verifiera signaturens äkthet alltid kommer att få ett positivt resultat i händelse av äkthet. Låt oss visa det:

Först, om , sedan av Fermats lilla sats följer det att . Eftersom g >1 och q är primtal måste g ha multiplikationsordningen q modulo p . $g=h^{{(p-1)/q}}\mod sid$ $g^{q}=h^{{p-1}}=1\mod sid$

För att signera ett meddelande, räknar det ut

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

Därför

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

Eftersom g är av ordningen 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}.

Slutligen följer riktigheten av DSA-schemat av

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

[5]

Arbetsexempel

Låt oss ge ett exempel på hur algoritmen fungerar för små tal. Låt hashvärdet av vårt budskap . $H=9$

Parametergenerering

$H=9_{10}=1001_{2}$
hashlängd , så du kan välja $fyra$ ${\displaystyle q=11_{10}=1011_{2))$
välja eftersom $p=23$ $23-1=22=2*q$
välja $g=2^{2}=4$

Skapa nycklar

välj som hemlig nyckel $x=7$
sedan den publika nyckeln $y=g^{x}{\bmod {p}}=4^{7}{\bmod {2}}3=16384{\bmod {2}}3=(712\cdot 23+8) {\bmod {2}}3=8$

Meddelandesignatur

välja $k = 3$
sedan $r=(g^{k}{\bmod {p))){\bmod {q}}=(4^{3}{\bmod {2}}3){\bmod {1}}1 =7$
$r\neq 0$ , gå vidare
$s=k^{-1}(H(m)+x\cdot r){\bmod {q}}=4(9+7\cdot 7){\bmod {1}}1=1$ , där det beaktas att $3^{-1}{\bmod {1}}1=4$
$s\neq 0$ , gå vidare
signaturen är ett par siffror $(r,s)=(7,1)$

Signaturverifiering

$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$
mottagen, vilket betyder att signaturen är korrekt. $v = r$

Analoger

DSA-algoritmen är baserad på svårigheten att beräkna diskreta logaritmer och är en modifiering av det klassiska ElGamal- schemat [11] , där meddelandehashning läggs till, och alla logaritmer beräknas av , vilket gör det möjligt att göra signaturen kortare jämfört med analoger [12] . Baserat på ElGamal-schemat byggdes också andra algoritmer, till exempel den ryska GOST 34.10-94 , som nu anses vara föråldrad. Den ersattes av standarden GOST R 34.10-2012 [13] , som använder en grupp av punkter i en elliptisk kurva . $mod~q$

En sådan modifiering, dvs. övergången från den multiplikativa gruppen modulo ett primtal till gruppen av elliptiska kurvpunkter finns också för DSA - ECDSA [14] ( Elliptic Curve Digital Signature Algorithm - digital signaturalgoritm på elliptiska kurvor) . Den används till exempel i bitcoin -krypteringsvalutan för att bekräfta transaktioner. Denna översättning låter dig minska storleken på nycklarna utan att offra säkerheten - i bitcoin-systemet är storleken på den privata nyckeln 256 bitar, och motsvarande publika nyckel är 512 bitar.

En annan vanlig publik nyckelalgoritm (används för både kryptering och digital signatur), RSA (uppkallad efter författarna: Rivest , Shamir , Adleman ), bygger på svårigheten att faktorisera stora siffror.

Kryptografisk styrka

Varje attack på algoritmen kan beskrivas på följande sätt: en angripare tar emot alla publika signaturparametrar och en viss uppsättning par (meddelande, signatur) och försöker, med denna uppsättning, skapa en giltig signatur för ett nytt meddelande som inte representeras i uppsättningen .

Dessa attacker kan villkorligt delas in i två grupper - för det första kan en angripare försöka återställa den hemliga nyckeln , och sedan får han omedelbart möjlighet att signera vilket meddelande som helst, och för det andra kan han försöka skapa en giltig signatur för ett nytt meddelande utan att återställer den hemliga nyckeln direkt. $x$

Förutsägbarhet för en slumpmässig parameter

Den enhetliga fördelningen av den slumpmässiga parametern är mycket viktig för systemets säkerhet. Om flera på varandra följande parameterbitar är kända för en serie signaturer kan den hemliga nyckeln återställas med hög sannolikhet. [femton] $k$ $k$

Att upprepa parametern för två meddelanden leder till en enkel hackning av systemet. Detta kan hända när du använder en dålig pseudo-slumptalsgenerator . Denna sårbarhet i PlayStation 3- systemet gjorde att alla program kunde signeras på uppdrag av Sony . I vissa implementeringar av bitcoin-systemet för Android kan en angripare få tillgång till plånboken. [16] [17] Båda exemplen använde ECDSA [14] -systemet .

Om samma parameter användes för två meddelanden kommer deras signaturer att ha samma men olika , låt oss kalla dem . $m_{1},m_{2}$ $k$ $(r,s)$ $r$ $s$ ${\displaystyle s_{1},s_{2))$

Från uttrycket för kan vi uttrycka summan : $s$ $k$

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

Och likställ gemensamt för olika meddelanden: $k$

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

Härifrån är det lätt att uttrycka den hemliga nyckeln : $x$

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

Existentiell förfalskning

Vissa digitala signaturalgoritmer kan attackeras av en befintlig förfalskning (Existentiell förfalskning) . Det ligger i det faktum att för en signatur (antingen slumpmässig överhuvudtaget eller skapad enligt någon regel) är det möjligt att skapa ett korrekt meddelande (vilket dock vanligtvis inte är vettigt) med enbart offentliga parametrar.

För DSA-schemat är signaturen i alla fall giltig för ett meddelande med en hash . $r=g^{e}y\mod p\mod q$ $s=r$ $e$ $H(m)=es$

Detta är en av anledningarna till att hasha inmatningsmeddelandet. Om hashfunktionen väljs korrekt, skyddas DSA-algoritmen från denna attack, eftersom inversionen av den kryptografiska hashfunktionen (dvs. för ett givet fynd så att ) är beräkningsmässigt svårt. [arton] $k$ $m$ $H(m)=k$

Nyckelåterställning

signaturens korrekthetsvillkor kan skrivas om i en annan form:

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

denna ekvation är ekvivalent (eftersom multiplikationsordningen för g modulo p är lika med q)

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

så vi kan anta att för att återställa nyckeln måste angriparen lösa ett system av ekvationer av formen

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

men i detta system är okänt och det är allt , vilket betyder att antalet okända är en mer än ekvationerna, och för alla finns det de som uppfyller systemet. Eftersom q är ett stort primtal, kommer ett exponentiellt antal par (meddelande, signatur) att krävas för återställning. [ett] $x$ $k_i$ $x$ $k_i$ $x\mod q$

Signaturförfalskning

Du kan försöka förfalska en signatur utan att känna till den hemliga nyckeln, det vill säga försöka lösa ekvationen

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

med hänsyn till och . För varje fix är ekvationen ekvivalent med att beräkna den diskreta logaritmen. [ett] $r$ $s$ $r$

Verifieringssystem för algoritmimplementering

Licensvillkoren tillåter dig att implementera algoritmen i mjukvara och hårdvara. NIST skapade DSAVS [19] ( Eng. The Digital Signature Algorithm Validation System - ett system för att kontrollera den digitala signaturalgoritmen ). DSAVS består av flera efterlevnadstestmoduler som testar varje komponent i systemet oberoende av de andra. Testade implementeringskomponenter:

Generering av domänparametrar
Kontrollerar domäninställningar
Generering av ett offentligt-privat nyckelpar
Skapa en signatur
Signaturverifiering

För att testa implementeringen måste utvecklaren skicka in en ansökan om att testa dess implementering till CMT-laboratoriet ( Cryptographic Module Testing Laboratory ) . [5]

Generering av primtal

DSA-algoritmen kräver två primtal ( och ), så en primtals- eller pseudoprimgenerator behövs . $sid$ $q$

Shaw-Taylor- algoritmen [20] används för att generera primtal .

Pseudoprimer genereras med hjälp av en hashfunktion och Miller-Rabins probabilistiska test används för att testa primalitet . Ett enda Luke -primalitetstest kan läggas till det . [5]

Det antal iterationer som krävs beror på längden på de använda siffrorna och på verifieringsalgoritmen [5] :

alternativ	endast M-R test	M-R test + Luke test
p: 1024 bitar q: 160 bitar felsannolikhet $2^{-80}$	40	p: 3 q:19
p: 2048 bitar q: 224 bitar felsannolikhet $2^{-112}$	56	p: 3 q:24
p: 2048 bitar q: 256 bitar felsannolikhet $2^{-112}$	56	p: 3 q:27
p: 3072 bitar q: 256 bitar felsannolikhet $2^{-128}$	64	p: 2 q:27

Generering av slumptal

Algoritmen kräver också en slump- eller pseudoslumptalsgenerator . Denna generator behövs för att generera en privat användarnyckel x , såväl som för att generera en hemlig slumpmässig parameter . $k$

Standarden erbjuder olika sätt att generera pseudoslumptal med hjälp av blockchiffer eller hashfunktioner. [5] [21]

Anteckningar

↑ 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 .
↑ Hitta kollisioner i den fullständiga SHA-1 .
↑ Fristartskollision för full SHA-1 .
↑ NIST specialpublikation 800-57 .
↑ Elgamal, 1985 .
↑ C. P. Schnorr. Effektiv identifiering och signaturer för smarta kort // Framsteg inom 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 . Arkiverad från originalet den 12 april 2022.
↑ GOST R 34.11-2012
↑ 1 2 Den elliptiska kurvan digital signaturalgoritm (ECDSA) .
↑ Osäkerheten i den digitala signaturalgoritmen med delvis kända nonces .
↑ ECDSA - Tillämpnings- och implementeringsfel .
↑ Elliptisk kurvkryptering i praktiken .
↑ Säkerhetsargument för digitala signaturer och blinda signaturer .
↑ Valideringssystemet för digital signaturalgoritm .
↑ Genererar starka primtal .
↑ Generering av slumpmässiga nummer .

Litteratur

Standarder och patent

FIPS. PUB 186-1 .
FIPS. PUB 186-2 .
FIPS. PUB 186-3 .
FIPS. PUB 186-4 .
FIPS. PUB 180-4 . Arkiverad från originalet den 26 november 2016.
FIPS. PUB 202 (engelska) .
FIPS. PUB 202 (engelska) .
David W. Kravitz. Digital signaturalgoritm 5231668 A (engelska) .
NIST Special Publication 800-57 Del 1 Revision 4. Rekommendation för nyckelhantering .
GOST R 34.10-2012. Informationsteknologi. Kryptografiskt skydd av information. Processer för bildande och verifiering av elektronisk digital signatur . (ryska)
Valideringssystemet för digital signaturalgoritm .

Artiklar

Marc Stevens, Pierre Karpman, Thomas Peyrin. Fristartskollision för full SHA- 1 .
NIST Special Publication 800-90A rekommendation för generering av slumptal med hjälp av deterministiska slumpmässiga bitgeneratorer .
J. Shawe-Taylor. Genererar starka primtal .
Xiaoyun Wang, Yiqun Lisa, Hongbo Yu. Hitta kollisioner i Full SHA-1 .
Phong Q. Nguyen, Igor E. Shparlinski. Osäkerheten i den digitala signaturalgoritmen med delvis kända nonces .
David Pointcheval, Jacques Stern. Säkerhetsargument för digitala signaturer och blinda signaturer .
Markus Schmid. ECDSA - Application and Implementation Failures .
Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA ) .
Elgamal T. Ett kryptosystem med offentlig nyckel och ett signaturschema baserat på diskreta logaritmer, ett kryptosystem med offentlig nyckel och ett signaturschema baserat på diskreta logaritmer // IEEE Trans . inf. Theory / 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. Elliptisk kurvkryptering i praktiken .

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort