Algoritmus digitálneho podpisu

Algoritmus digitálneho podpisu (DSA) je kryptosystém s verejným kľúčom a federálny štandard spracovania informácií pre digitálne podpisy, založený na matematickom koncepte modulárnej exponencie a probléme diskrétneho logaritmu. DSA je variantom podpisových schém Schnorr a ElGamal.

Národný inštitút pre štandardy a technológie (NIST) navrhol DSA na použitie vo svojom Štandarde Digitálneho Podpisu (DSS) v roku 1991 a v roku 1994 ho prijal ako FIPS 186. Boli vydané štyri revízie pôvodnej špecifikácie. Najnovšia špecifikácia je: FIPS 186-4 z júla 2013. DSA je patentovaný, ale NIST tento patent sprístupnil celosvetovo bez licenčných poplatkov. V návrhu verzie špecifikácie FIPS 186-5 sa uvádza, že DSA už nebude schválená na generovanie digitálnych podpisov, ale môže sa používať na overovanie podpisov vytvorených pred dátumom implementácie tejto normy.

Prehľad

DSA funguje v rámci kryptosystémov s verejným kľúčom a je založený na algebraických vlastnostiach modulárnej exponencie spolu s problémom diskrétneho logaritmu, ktorý sa považuje za výpočtovo ťažko riešiteľný. Algoritmus používa kľúčový pár pozostávajúci z verejného a súkromného kľúča. Súkromný kľúč sa používa na generovanie digitálneho podpisu správy a takýto podpis sa dá overiť pomocou príslušného verejného kľúča podpisovateľa. Digitálny podpis zabezpečuje autentifikáciu správy (príjemca môže overiť pôvod správy), integritu (príjemca môže overiť, že správa nebola od jej podpísania zmenená) a nepopierateľnosť (odosielateľ nemôže nepravdivo tvrdiť, že správu nepodpísal).

História

V roku 1982 vláda USA požiadala o predloženie návrhov na štandard podpisu verejným kľúčom. V auguste 1991 Národný inštitút pre štandardy a technológie (NIST) navrhol DSA na použitie vo svojom štandarde digitálneho podpisu (DSS). Spočiatku sa stretol so značnou kritikou, najmä zo strany softvérových spoločností, ktoré už investovali úsilie do vývoja softvéru na digitálny podpis založeného na kryptosystéme RSA. Napriek tomu NIST v roku 1994 prijal DSA ako federálny štandard (FIPS 186). Boli vydané štyri revízie pôvodnej špecifikácie: FIPS 186-1 v roku 1998, FIPS 186-2 v roku 2000,FIPS 186-3 v roku 2009 a FIPS 186-4 v roku 2013. Návrh verzie normy FIPS 186-5 zakazuje podpisovanie pomocou DSA, pričom umožňuje overovanie podpisov vytvorených pred dátumom implementácie normy. Má byť nahradená novšími podpisovými schémami, ako je EdDSA.

Na DSA sa vzťahuje na U.S. Patent 5 231 668, ktorý bol podaný 26. júla 1991 a ktorého platnosť už vypršala a ktorý sa pripisuje Davidovi W. Kravitzovi, bývalému zamestnancovi NSA. Tento patent bol udelený "Spojeným štátom americkým zastúpeným Ministerstvom obchodu, Washington, D.C." a NIST tento patent sprístupnil celosvetovo bez licenčných poplatkov. Claus P. Schnorr tvrdí, že jeho U.S. Patent 4 995 082 (tiež už neplatný) pokrýva DSA; toto tvrdenie je sporné.

Operácia

Algoritmus DSA zahŕňa štyri operácie: generovanie kľúča (čím sa vytvorí kľúčový pár), distribúciu kľúča, podpisovanie a overenie podpisu.

1. Generovanie kľúčov

Generovanie kľúčov má dve fázy. V prvej fáze sa vyberajú parametre algoritmu, ktoré môžu byť spoločné pre rôznych používateľov systému, zatiaľ čo v druhej fáze sa vypočíta jeden pár kľúčov pre jedného používateľa.

Generovanie parametrov

• Vyberte schválenú kryptografickú hašovaciu funkciu $H$ s výstupnou dĺžkou ${\displaystyle |H|}$ bitov. V pôvodnom DSS bola $H$ vždy SHA-1, ale v súčasnom DSS sú schválené silnejšie hašovacie funkcie SHA-2. Ak je ${\displaystyle |H|}$ väčšia ako dĺžka modula $N$, použije sa len $N$ ľavých bitov výstupu hašovacej funkcie.
• Vyberte dĺžku kľúča $L$. Pôvodný DSS obmedzuje $L$ na násobok 64 v rozsahu 512 až 1024 vrátane. NIST 800-57 odporúča dĺžku 2048 (alebo 3072) pre kľúče s dobou zabezpečenia presahujúcou rok 2010 (alebo 2030).
• Vyberte dĺžku modula $N$ takú, aby ${\displaystyle N<L}$ a ${\displaystyle N\leq |H|}$. FIPS 186-4 špecifikuje, že $L$ a $N$ majú mať jednu z hodnôt: (1024, 160), (2048, 224), (2048, 256) alebo (3072, 256).
• Vyberte si $N$-bitové prvočíslo $q$.
• Vyberte $L$-bitové prvočíslo $p$ také, že ${\displaystyle p-1}$ je násobkom $q$.
• Vyberte celé číslo $h$ náhodne z ${\displaystyle \{2\ldots p-2\}}$.
• Vypočítajte ${\displaystyle g:=h^{(p-1)/q}\mod p}$. V zriedkavom prípade, keď ${\displaystyle g=1}$, skúste to znova s iným $h$. Bežne sa používa ${\displaystyle h=2}$. Táto modulárna exponenciácia sa dá efektívne vypočítať, aj keď sú hodnoty veľké.

Parametre algoritmu sú $({\displaystyle p},{\displaystyle q},{\displaystyle g})$. Tieto môžu byť zdieľané medzi rôznymi používateľmi systému.

Kľúče pre jednotlivých používateľov

Pri danom súbore parametrov sa v druhej fáze vypočíta dvojica kľúčov pre jedného používateľa:

• Náhodne vyberte celé číslo $x$ z ${\displaystyle \{1\ldots q-1\}}$.
• Vypočítajte ${\displaystyle y:=g^{x}\mod p}$.

$x$ je súkromný kľúč a $y$ je verejný kľúč.

2. Distribúcia kľúčov

Podpisovateľ by mal zverejniť verejný kľúč $y$. To znamená, že by mal poslať kľúč príjemcovi prostredníctvom spoľahlivého, ale nie nevyhnutne tajného mechanizmu. Podpisovateľ by mal udržať súkromný kľúč $x$ v tajnosti.

3. Podpisovanie

Správa ${\displaystyle m}$ je podpísaná takto:

• Náhodne vyberte celé číslo ${\displaystyle k}$ z ${\displaystyle \{1\ldots q-1\}}$
• Vypočítajte ${\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}$. V nepravdepodobnom prípade, že ${\displaystyle r=0}$, začnite znova s iným náhodným ${\displaystyle k}$.
• Vypočítajte ${\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}$. V nepravdepodobnom prípade, že ${\displaystyle s=0}$, začnite znova s iným náhodným $k$.

Podpis je $\left(r,s\right)$

Výpočet ${\displaystyle k}$ a $r$ sa rovná vytvoreniu nového kľúča na správu. Modulárna exponenciácia pri výpočte $r$ je výpočtovo najnáročnejšia časť operácie podpisovania, ale môže sa vypočítať skôr, ako je známa správa. Výpočet modulárnej inverzie ${\displaystyle k^{-1}{\bmod {\,}}q}$ je druhou najzložitejšou časťou a tiež sa môže vypočítať skôr, ako je známa správa. Môže sa vypočítať pomocou rozšíreného Euklidovho algoritmu alebo pomocou Fermatovej malej vety ako ${\displaystyle k^{q-2}{\bmod {\,}}q}k^{q-2}{\bmod {\,}}q$.

4. Overovanie podpisov

Možno overiť, že podpis (r,s) je platný podpis pre správu m takto:

• Overte, že $0<r<q$ a $0<s<q$.
• Vypočítajte ${\displaystyle w:=s^{-1}{\bmod {\,}}q}$.
• Vypočítajte ${\displaystyle u_{1}:=H(m)\cdot w\,{\bmod {\,}}q}$.
• Vypočítajte ${\displaystyle u_{2}:=r\cdot w\,{\bmod {\,}}q}$.
• Vypočítajte${\displaystyle v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q}$.
• Signatúra je platná vtedy a len vtedy, ak $v=r$.

Správnosť algoritmu

Podpisová schéma je správna v tom zmysle, že overovateľ vždy akceptuje pravé podpisy. To sa dá dokázať takto:

Po prvé, keďže ${\textstyle g=h^{(p-1)/q}~{\text{mod}}~p}$, vyplýva, že ${\textstyle g^{q}\equiv h^{p-1}\equiv 1\mod p}$ podľa Fermatovej malej vety. Keďže $g>0$ a $q$ je prvočíslo, $g$ musí byť rádu $q$ .

Podpisovateľ vypočíta

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

Preto

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

Keďže $g$ je rádu $q$ my máme

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

Nakoniec, správnosť DSA vyplýva z

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

Citlivosť

Pri DSA sú rozhodujúce entropia, utajenie a jedinečnosť náhodnej hodnoty podpisu k. Je taká kritická, že porušenie ktorejkoľvek z týchto troch požiadaviek môže útočníkovi odhaliť celý súkromný kľúč. Použitie tej istej hodnoty dvakrát (aj pri zachovaní tajnosti k), použitie predvídateľnej hodnoty alebo únik aj niekoľkých bitov k v každom z niekoľkých podpisov stačí na odhalenie súkromného kľúča x.

Tento problém sa týka algoritmu DSA aj algoritmu ECDSA (Elliptic Curve Digital Signature Algorithm) - v decembri 2010 skupina, ktorá si hovorí fail0verflow, oznámila obnovenie súkromného kľúča ECDSA, ktorý používala spoločnosť Sony na podpisovanie softvéru pre hernú konzolu PlayStation 3. Útok bol možný, pretože spoločnosť Sony nedokázala pre každý podpis vygenerovať nový náhodný k.

Tomuto problému sa dá predísť deterministickým odvodením k zo súkromného kľúča a hashu správy, ako to opisuje RFC 6979. Tým sa zabezpečí, že k je pre každý H(m) iný a nepredvídateľný pre útočníkov, ktorí nepoznajú súkromný kľúč x.

Okrem toho je možné vytvoriť škodlivé implementácie DSA a ECDSA, v ktorých je zvolený k s cieľom podprahového úniku informácií prostredníctvom podpisov. Napríklad offline súkromný kľúč by mohol uniknúť z dokonalého offline zariadenia, ktoré by vydalo len nevinne vyzerajúce podpisy.

Implementácie

Nižšie je uvedený zoznam kryptografických knižníc, ktoré poskytujú podporu pre DSA:

• Botan
• Bouncy Castle
• cryptlib
• Crypto++
• libgcrypt
• Nettle
• OpenSSL
• wolfCrypt
• GnuTLS

Pozri aj

• Modulárna aritmetika
• RSA (cryptosystem)
• ECDSA
• Asymetrická šifra
• Šifrovanie disku

Zdroj

Tento článok je čiastočný alebo úplný preklad článku Digital Signature Algorithm na anglickej Wikipédii.