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.

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

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

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.

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.

• Vyberte schválenú kryptografickú hašovaciu funkciu ${\displaystyle H}$ s výstupnou dĺžkou ${\displaystyle {\displaystyle |H|}}$ bitov. V pôvodnom DSS bola ${\displaystyle H}$ vždy SHA-1, ale v súčasnom DSS sú schválené silnejšie hašovacie funkcie SHA-2. Ak je ${\displaystyle {\displaystyle |H|}}$ väčšia ako dĺžka modula ${\displaystyle N}$, použije sa len ${\displaystyle N}$ ľavých bitov výstupu hašovacej funkcie.
• Vyberte dĺžku kľúča ${\displaystyle L}$. Pôvodný DSS obmedzuje ${\displaystyle 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 ${\displaystyle N}$ takú, aby ${\displaystyle {\displaystyle N<L}}$ a ${\displaystyle {\displaystyle N\leq |H|}}$. FIPS 186-4 špecifikuje, že ${\displaystyle L}$ a ${\displaystyle N}$ majú mať jednu z hodnôt: (1024, 160), (2048, 224), (2048, 256) alebo (3072, 256).
• Vyberte si ${\displaystyle N}$-bitové prvočíslo ${\displaystyle q}$.
• Vyberte ${\displaystyle L}$-bitové prvočíslo ${\displaystyle p}$ také, že ${\displaystyle {\displaystyle p-1}}$ je násobkom ${\displaystyle q}$.
• Vyberte celé číslo ${\displaystyle h}$ náhodne z ${\displaystyle {\displaystyle \{2\ldots p-2\}}}$.
• Vypočítajte ${\displaystyle {\displaystyle g:=h^{(p-1)/q}\mod p}}$. V zriedkavom prípade, keď ${\displaystyle {\displaystyle g=1}}$, skúste to znova s iným ${\displaystyle h}$. Bežne sa používa ${\displaystyle {\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 ({\displaystyle p},{\displaystyle q},{\displaystyle g})}$. Tieto môžu byť zdieľané medzi rôznymi používateľmi systému.

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 ${\displaystyle x}$ z ${\displaystyle {\displaystyle \{1\ldots q-1\}}}$.
• Vypočítajte ${\displaystyle {\displaystyle y:=g^{x}\mod p}}$.

${\displaystyle x}$ je súkromný kľúč a ${\displaystyle y}$ je verejný kľúč.

Podpisovateľ by mal zverejniť verejný kľúč ${\displaystyle 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ľúč ${\displaystyle x}$ v tajnosti.

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

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

Podpis je ${\displaystyle \left(r,s\right)}$

Výpočet ${\displaystyle {\displaystyle k}}$ a ${\displaystyle r}$ sa rovná vytvoreniu nového kľúča na správu. Modulárna exponenciácia pri výpočte ${\displaystyle r}$Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.