Digital signaturalgoritm

Digital Signature Algorithm ( DSA ) är ett kryptosystem med offentlig nyckel och Federal Information Processing Standard för digitala signaturer , baserad på det matematiska konceptet modulär exponentiering och det diskreta logaritmproblemet . DSA är en variant av Schnorr och ElGamal signaturscheman.

National Institute of Standards and Technology (NIST) föreslog DSA för användning i deras Digital Signature Standard (DSS) 1991 och antog den som FIPS 186 1994. Fyra versioner av den ursprungliga specifikationen har släppts. Den senaste specifikationen är: FIPS 186-4 från juli 2013. DSA är patenterat men NIST har gjort detta patent tillgängligt världen över royaltyfritt. Ett utkast till version av specifikationen FIPS 186-5 indikerar att DSA inte längre kommer att godkännas för generering av digitala signaturer, utan kan användas för att verifiera signaturer som genererats före implementeringsdatumet för den standarden.

Översikt

DSA fungerar inom ramen för kryptosystem med publik nyckel och är baserad på de algebraiska egenskaperna hos modulär exponentiering , tillsammans med det diskreta logaritmproblemet, som anses vara beräkningsmässigt svårlöst. Algoritmen använder ett nyckelpar som består av en offentlig nyckel och en privat nyckel. Den privata nyckeln används för att generera en digital signatur för ett meddelande, och en sådan signatur kan verifieras genom att använda undertecknarens motsvarande publika nyckel. Den digitala signaturen ger meddelandeautentisering (mottagaren kan verifiera meddelandets ursprung), integritet (mottagaren kan verifiera att meddelandet inte har ändrats sedan det signerades) och icke-avvisande ( avsändaren kan inte felaktigt hävda att de inte har undertecknade meddelandet).

Historia

1982 begärde den amerikanska regeringen in förslag på en standard för signaturer för offentliga nyckel. I augusti 1991 National Institute of Standards and Technology (NIST) DSA för användning i deras digitala signaturstandard (DSS). Inledningsvis kom det betydande kritik, särskilt från mjukvaruföretag som redan hade investerat ansträngningar i att utveckla programvara för digitala signaturer baserad på RSA-kryptosystemet . Ändå antog NIST DSA som en federal standard (FIPS 186) 1994. Fyra versioner av den ursprungliga specifikationen har släppts: FIPS 186–1 1998, FIPS 186–2 2000, FIPS 186–3 2009 och FIPS 186 –4 2013. Ett utkast till version av standard FIPS 186-5 förbjuder signering med DSA, samtidigt som det tillåter verifiering av signaturer som genererats före implementeringsdatumet av standarden som ett dokument. Den ska ersättas av nyare signatursystem som EdDSA .

DSA omfattas av det amerikanska patentet 5 231 668 , inlämnat 26 juli 1991 och nu upphört att gälla, och tillskrivs David W. Kravitz, en tidigare NSA- anställd. Detta patent gavs till "Amerikas förenta stater som representeras av handelsministern, Washington , DC", och NIST har gjort detta patent tillgängligt världen över royaltyfritt. Claus P. Schnorr hävdar att hans amerikanska patent 4 995 082 (också nu har löpt ut) täckte DSA; detta påstående bestrids.

Drift

DSA-algoritmen involverar fyra operationer: nyckelgenerering (som skapar nyckelparet), nyckeldistribution, signering och signaturverifiering.

1. Nyckelgenerering

Nyckelgenerering har två faser. Den första fasen är ett val av algoritmparametrar som kan delas mellan olika användare av systemet, medan den andra fasen beräknar ett enda nyckelpar för en användare.

Parametergenerering

Välj en godkänd kryptografisk hashfunktion $H$ med utdatalängd $|H|$ bitar. I den ursprungliga DSS $H$ alltid SHA-1 , men de starkare SHA-2- hashfunktionerna är godkända för användning i den aktuella DSS. Om $|H|$ är större än modullängden $N$ , endast de $N$ bitarna längst till vänster i hash-utgången används.
Välj en tangentlängd $L$ . Den ursprungliga DSS begränsade $L$ till att vara en multipel av 64 mellan 512 och 1024 inklusive. NIST 800-57 rekommenderar längder på 2048 (eller 3072) för nycklar med säkerhetslivslängder längre än 2010 (eller 2030).
Välj modullängden $N$ så att $N<L$ och $N\leq |H|$ . FIPS 186-4 anger att $L$ och $N$ ska ha ett av värdena: (1024, 160), (2048, 224), (2048, 256) eller (3072, 256).
Välj ett $N$ -bit primtal $q$ .
Välj ett $L$ -bit primtal $p$ så att $p-1$ är en multipel av $q$ .
Välj ett heltal $h$ slumpmässigt från $\{2\ldots p-2\}$ .
Beräkna $g:=h^{(p-1)/q}\mod p$ . I det sällsynta fallet att $g=1$ försök igen med en annan $h$ . Vanligtvis används ${\displaystyle h=2} .$ Denna modulära exponentiering kan beräknas effektivt även om värdena är stora.

Algoritmparametrarna är ( $p$ , $q$ , ${\displaystyle g} )$ . Dessa kan delas mellan olika användare av systemet.

Nycklar per användare

Givet en uppsättning parametrar, beräknar den andra fasen nyckelparet för en enskild användare:

Välj ett heltal $x$ slumpmässigt från $\{1\ldots q-1\}$ .
Beräkna $y:=g^{x}\mod p$ .

$x$ är den privata nyckeln och $y$ är den publika nyckeln.

2. Nyckelfördelning

Undertecknaren bör publicera den publika nyckeln $y$ . Det vill säga att de ska skicka nyckeln till mottagaren via en pålitlig, men inte nödvändigtvis hemlig, mekanism. Undertecknaren bör hålla den privata nyckeln $x$ hemlig.

3. Signering

Ett meddelande $m$ signeras enligt följande:

Välj ett heltal $k$ slumpmässigt från $\{1\ldots q-1\}$
Beräkna $r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q$ . I det osannolika fallet att $r=0$ , börja om med en annan slumpmässig $k$ .
Beräkna $s:=\left(k^{-1}\left(H(m)+xr\right)\right) {\bmod {\,}}q$ . I det osannolika fallet att $s=0$ , börja om med en annan slumpmässig $k$ .

Signaturen är $\left(r,s\right)$

Beräkningen av $k$ och $r$ motsvarar att skapa en ny per-meddelandenyckel. Den modulära exponentieringen vid beräkning av $r$ är den beräkningsmässigt dyraste delen av signeringsoperationen, men den kan beräknas innan meddelandet är känt. Att beräkna den modulära inversen $k^{-1}{\bmod {\,}}q$ är den näst dyraste delen, och den kan också beräknas innan meddelandet är känt. Den kan beräknas med den utökade euklidiska algoritmen eller med Fermats lilla sats som $k^{q-2}{\bmod {\,}}q$ .

4. Signaturverifiering

Man kan verifiera att en signatur $\left(r,s\right)$ är en giltig signatur för ett meddelande $m$ enligt följande:

Kontrollera att $0<r<q$ och $0<s<q$ .
Beräkna $w:=s^{-1}{\bmod {\,}}q$ .
Beräkna $u_{1}:=H(m)\cdot w\,{\bmod {\,}}q$ .
Beräkna $u_{2}:=r\cdot w\,{\bmod {\,}}q$ .
Beräkna $v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p \right){\bmod {\,}}q$ .
Signaturen är giltig om och endast om $v=r$ .

Algoritmens korrekthet

Signaturschemat är korrekt i den meningen att verifieraren alltid kommer att acceptera äkta signaturer. Detta kan visas på följande sätt:

För det första, eftersom ${\textstyle g=h^{(p-1)/q}~{\text{mod}}~p} ,$ följer det att ${\textstyle g^{q}\equiv h^{p-1}\equiv 1\mod p}$ av Fermats lilla teorem . Eftersom $g>0$ och $q$ är primtal måste $g$ ha ordningen $q$ .

Undertecknaren beräknar

s=k^{-1}(H(m)+xr){\bmod {\,}}q

Således

{\begin{aligned}k&\equiv H(m)s^{-1 }+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}

Eftersom $g$ har ordningen $q$ har vi

{\begin{aligned}g^{k}&\ ekv. g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u_{1}}y^{ u_{2}}{\pmod {p}}\end{aligned}}

Slutligen följer riktigheten av DSA av

{\begin{aligned}r&=(g^{k}{\bmod {\,}} p){\bmod {\,}}q\\&=(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p){\bmod {\,}} q\\&=v\end{aligned}}

Känslighet

Med DSA är entropin, sekretessen och unikheten för det slumpmässiga signaturvärdet $k$ avgörande. Det är så kritiskt att ett brott mot något av dessa tre krav kan avslöja hela den privata nyckeln för en angripare. Att använda samma värde två gånger (även medan ${\displaystyle k} hålls$ hemligt), att använda ett förutsägbart värde, eller läcka till och med några bitar av $k$ i var och en av flera signaturer, räcker för att avslöja den privata nyckeln $x$ .

Det här problemet påverkar både DSA och Elliptic Curve Digital Signature Algorithm ( ECDSA ) – i december 2010 tillkännagav gruppen fail0verflow återställningen av den privata ECDSA- nyckeln som används av Sony för att signera programvara för PlayStation 3 -spelkonsolen. Attacken möjliggjordes eftersom Sony misslyckades med att generera en ny slumpmässig $k$ för varje signatur.

Detta problem kan förhindras genom att härleda $k$ deterministiskt från den privata nyckeln och meddelandehash, enligt beskrivningen av RFC 6979 . Detta säkerställer att $k$ är olika för varje $H(m)$ och oförutsägbar för angripare som inte känner till den privata nyckeln $x$ .

Dessutom kan skadliga implementeringar av DSA och ECDSA skapas där $k$ väljs för att subliminalt läcka information via signaturer. Till exempel kan en privat nyckel offline läcka från en perfekt offlineenhet som bara släppte oskyldiga signaturer.

Genomföranden

Nedan är en lista över kryptografiska bibliotek som ger stöd för DSA:

Se även

externa länkar

FIPS PUB 186-4: Digital Signature Standard (DSS), den fjärde (och nuvarande) revisionen av den officiella DSA-specifikationen.
Rekommendation för nyckelhantering -- Del 1: allmänt , NIST Special Publication 800-57, sid. 62–63