Digital Signature Algorithm (zkráceněDSA, doslovně přeloženo zangličtinyalgoritmus digitálního podpisu) je standardamerické vlády prodigitální podpis. DSA byl navržen americkou agenturouNSA,^[1] přestože původně byl připisován americkému institutuNIST, který jej v srpnu1991 určil pro použití vDigital Signature Standard (DSS), specifikovaném veFIPS 186, jenž byl přijat v roce 1993. Malá úprava standardu byla vydána v roce1996 jako FIPS 186-1, standard byl dále rozšířen v roce2000 jako FIPS 186-2, v roce 2009 jako FIPS 186-3^[2] a nakonec v roce 2013 jako FIPS 186-4.^[3] V roce 2024 projektOpenSSH podporu slabého DSA implicitně vypnul^[4] a definitivně bylo DSA odstraněno z kódu v roce 2025.^[5]

DSA jepatentováno pod číslem 5231668^[6] a připsánoDavidovi W. Kravitzovi, bývalému zaměstnanciNárodní bezpečnostní agenturySpojený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ů.^[7]Německý matematikClaus P. Schnorr v té době prohlašoval, že jeho patent naSchnorrův podpis pokrývá i DSA.^[8]

Algoritmus samotný je založen na problému výpočtudiskrétního logaritmu, je podobný algoritmuElGamal.

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ěrkryptografické 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 parametrechL aN, které určují délku klíče. V původní verzi DSS byla volbaL omezena na násobky 64 v rozsahu 512 až 1024 včetně. Doporučení Národního institutu standardů a technologií číslo 800-57^[9] 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éhoN.Federální standard pro práci s informacemi číslo 186-3^[2] doporučuje dvojiceL aN (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 vybereN-bitovéprvočísloq. DélkaN musí být alespoň taková, jako délka výstupu použité hašovací funkce.
• Dále se vybereL-bitové prvočíslop takové, žep-1 je násobekq.
• Nakonec se vybereg jako takové číslo, jehož multiplikativnířádmodulop je právěq. Toho lze dosáhnout dosazováním do vzorceg=h^(p-1)/q modp pro náhodnáh (kde 1<h <p-1), dokud výsledek není různý od jedné. Většina náhodných volebh 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 modp.

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

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

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

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

Především zg =h^(p–1)/q modp plyneg^q ≡h^p-1 ≡ 1 (mod p) podleMalé Fermatovy věty. Protože platíg>1 aq je prvočíslo, musí mítg řádq.

Z výpočtu

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

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

A protožeg má řádq, platí také

Dohromady tedy

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

Digital Signature algorithm je široce využíván, mimo jiné vOpenSSL, vOpenSSH a vGnuPG.

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

• Kryptografické algoritmy
• Kryptografie s veřejným klíčem

• Údržba:Články s dočasně použitou šablonou
• Monitoring:Články přeložené z enwiki
• Monitoring:Autoritní kontrola s 0 identifikátory