Přeskočit na obsah

Digital Signature Algorithm

Z Wikipedie, otevřené encyklopedie

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íčů

[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[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=gx mod p.

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)+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

[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

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

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

Dohromady tedy

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

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

  1. a b (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