Digital Signature Algorithm

Digital Signature Algorithm (zkráceně DSA, doslovně přeloženo z angličtiny algoritmus digitálního podpisu) je standard americké vlády pro digitální podpis. Byl navržen americkým institutem NIST v srpnu 1991 pro použití v jejich Digital Signature Standard (DSS), specifikovaném ve FIPS 186, jenž byl přijat v roce 1993. Malá úprava standardu byla vydána v roce 1996 jako FIPS 186-1, a standard byl dále rozšířen v roce 2000 jako FIPS 186-2, v roce 2009 jako FIPS 186-3.^[1] a nakonec v roce 2013 jako FIPS 186-4.^[2]

DSA je patentováno pod číslem 5231668^[3] a připsáno Davidovi W. Kravitzovi, bývalému zaměstnanci Národní bezpečnostní agentury Spojených států amerických. Národní institut standardů a technologie tento patent dal celosvětové veřejnosti k volnému užívaní bez poplatků.^[4] Německý matematik Claus P. Schnorr v té době prohlašoval, že jeho patent na Schnorrův podpis pokrývá i DSA.^[5]

Algoritmus samotný je založen na problému výpočtu diskrétního logaritmu, je podobný algoritmu ElGamal.

Vytváření klíčů

Vytváření klíčů má dvě fáze. Ve fázi první se vyberou parametry algoritmu, které mohou být sdíleny více různými uživateli systému.

• Především se provede výběr kryptografické hašovací funkce. V původní DSS byla jako hašovací funkce povinně SHA-1, ale v současných verzích je povolena též SHA-2.
• Dále se rozhodne o parametrech L a N, které určují délku klíče. V původní verzi DSS byla volba L omezena na násobky 64 v rozsahu 512 až 1024 včetně. Doporučení Národního institutu standardů a technologií číslo 800-57^[6] doporučuje délku 2048 (respektive 3072) pro klíče, u kterých se předpokládá používání po roce 2010 (respektive 2030), při použití adekvátně velkého N. Federální standard pro práci s informacemi číslo 186-3^[1] doporučuje dvojice L a N (1024,160), (2048,224), (2048,256) a (3072,256). Znamená to tedy, že ve standardu NIST je původní grupa (například 1024 bitů) omezena na podgrupu (síly 160 bitů).
• Dále se vybere N-bitové prvočíslo q. Délka N musí být alespoň taková, jako délka výstupu použité hašovací funkce.
• Dále se vybere L-bitové prvočíslo p takové, že p-1 je násobek q.
• Nakonec se vybere g jako takové číslo, jehož multiplikativní řád modulo p je právě q. Toho lze dosáhnout dosazováním do vzorce g=h^(p-1)/q mod p pro náhodná h (kde 1< h < p-1), dokud výsledek není různý od jedné. Většina náhodných voleb h uspěje, nejčastěji se používá h=2.

Parametry (p,q,g) mohou být sdíleny více uživateli a nejsou tajné. Následuje vytvoření samotných klíčů.

• Nejdříve se náhodně vybere soukromý klíč x v rozsahu 0<x<q.
• Pak se spočítá veřejný klíč y - y=g^x mod p.

Podepisování

Při označení hašovací funkce písmenem H a zprávy písmenem z probíhá podepisování takto:

• pro danou zprávu se vybere náhodná hodnota k v rozsahu 0<k<q
• spočítá se r=(g^k mod p) mod q
• spočítá se s=(k⁻¹(H(z)+xr)) mod q
• v nepříliš pravděpodobném případě, že je r=0 nebo s=0 se výpočet opakuje od začátku
• jinak je podpisem dvojice (r,s)

Ověřování podpisu

• pokud neplatí 0< r <q a 0< s <q pak je podpis automaticky zamítnut.
• jinak se spočítá w = (s)⁻¹ mod q
• dále se spočítá u1 = (H(z)*w) mod q
• dále se spočítá u2 = (r*w) mod q
• nakonec se spočítá v = ((g^u1*y^u2) mod p) mod q
• Podpis platí, pokud platí v = r

Správnost algoritmu

Ukázat, že správně vytvořený podpis bude jako takový rozeznán, je možné následovně:

Především z g = h^(p–1)/q mod p plyne g^q ≡ h^p-1 ≡ 1 (mod p) podle Malé Fermatovy věty. Protože platí g>1 a q je prvočíslo, musí mít g řád q.

Z výpočtu

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

učiněného během podepisování plyne

${\displaystyle {\begin{matrix}k&\equiv &H(z)s^{-1}+xrs^{-1}\\&\equiv &H(z)w+xrw{\pmod {q}}.\\\end{matrix}}}$

A protože g má řád q, platí také

${\displaystyle {\begin{matrix}g^{k}&\equiv &g^{H(z)w}g^{xrw}\\&\equiv &g^{H(z)w}y^{rw}\\&\equiv &g^{u1}y^{u2}{\pmod {p}}.\\\end{matrix}}}$

Dohromady tedy

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

Užití

Digital Signature algorithm je široce využíván, mimo jiné v OpenSSL, v OpenSSH a v GnuPG.

Reference

V tomto článku byl použit překlad textu z článku Digital Signature Algorithm na anglické Wikipedii.

1. (anglicky) FIPS 186-3
2. (anglicky) FIPS 186-4
3. (anglicky) patent 5231668 na google.com
4. (anglicky) zpráva v emailové konferenci GnuPG
5. (anglicky) patent 4995082 na google.com
6. (anglicky) NIST Special publication 800-57: Recommendation for Key Management