Digital Signature Algorithm

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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,[1] jenž byl přijat v roce 1993. Malá úprava standardu byla vydána v roce 1996 jako FIPS 186-1,[2] a standard byl dále rozšířen v roce 2000 jako FIPS 186-2[3] a opět v roce 2009 jako FIPS 186-3.[4]

DSA je patentováno pod číslem 5231668[5] 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ů.[6] Německý matematik Claus P. Schnorr prohlašuje, že jeho patent DSA také pokrývá.[7]

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

Vytváření klíčů[editovat | editovat zdroj]

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[8] 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[4] doporučuje dvojice L a N (1024,160), (2048,224), (2048,256) a (3072,256).
  • 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.

Všechny výše zmíněné hodnoty 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 x v rozsahu 0<x<q.
  • Pak se spočítá y=gx mod p.
  • Veřejný klíč je pak dán jako čtveřice (p,q,g,y), soukromý klíč je dán jako x.

Podepisování[editovat | editovat zdroj]

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=(gk mod p) mod q
  • spočítá se s=(k-1(H(z)+x×r)) 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[editovat | editovat zdroj]

  • pokud neplatí 0< r <q a 0< s <q pak je podpis automaticky zamítnut.
  • jinak se spočítá w = (s)-1 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 = ((gu1*yu2) mod p) mod q
  • Podpis platí, pokud platí v = r

Správnost algoritmu[editovat | editovat zdroj]

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 gqhp-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

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

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


\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é


\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

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

Užití[editovat | editovat zdroj]

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

Reference[editovat | editovat zdroj]

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

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