Jedná se o standard pro digitální podpisy dokumentů. Podepsaný dokument má tu výhodu, že je jednoznačně určený, pro daný podpis existuje právě jeden dokument, který má daný podpis (respektive je extrémně početně náročné najít další takový, z hlediska časového je to téměř nemožné). Jedná se o algoritmus standardu DSS (Digital Signature Standard), pochází z roku 1991, poslední modifikace je z roku 2013. Autorem je americký institut NIST (National Institute of Standards and Technology).
Algoritmus využívá hašovací funkce H (anglicky Hash function). O významu hašovacích funkcí pojednává samostatná kapitola, stručně se jedná o jednosměrné zobrazení, tj. takové, že lze ze vzoru rychle vypočítat obraz (hodnota hašovací funkce), ale najít pro určitou hodnotu vzor, který ji vygeneroval, je extrémně časově náročné. Algoritmus DSA konkrétně využívá hašovací funkce SHA-2.
Nejdříve je nutné vygenerovat klíče, následně je vysvětlen algoritmus podepisování a ověřování podpisu.
Vybereme vhodnou kryptografickou hašovací funkci H, typicky SHA-2.
Určí se parametry L a N, které mají význam délky používaných klíčů. Doporučuje se N=256 a L=2048.
Vygeneruje se N-bitové prvočíslo q a dále L-bitové prvočíslo p takové, že (p-1) je celočíselný násobek čísla q.
Vybere se přirozené číslo g. To se provede tak, že zvolíme náhodné přirozené číslo h takové, že (h(p-1)/q mod p) je různé od jedné. Pokud je výraz skutečně různý od jedné, pak g=(h(p-1)/q mod p), jinak se zvolí jiné h a proces se opakuje (obvykle vše funguje již pro h=2). Říkáme, že multiplikativní řád g modulo p je číslo q.
Vybere se náhodné celé číslo x, 0 < x < q a vypočte se hodnota y=gx mod p.
Veřejný klíč je čtveřice (p, q, g, y), privátní klíč je x.
Máme kryptografickou hašovací funkci H (viz samostatná kapitola či stručně výše) a dokument k podpisu (zpráva, matematicky nějaké přirozené číslo) m, pak:
Vybereme náhodné celé číslo k, 0 < k < q.
spočte se hodnota r=(gk mod p) mod q.
spočte se hodnota s=(k-1(H(m) + xr)) mod q.
Podpisem je dvojce (r,s), pokud je různá od nuly, jinak se algoritmus opakuje pro jinou hodnotu k.
Vstupem algoritmu je dvojce (r,s), kde 0 < r, s < q (pokud není splněno, je podpis hned odmítnut). Pro ověření se provádí následující kroky:
Spočítá se w = (s)-1 mod q, tj. multiplikativní inverze mod q.
Vypočte se u1 = (H(m)w) mod q.
Vypočte se u2 = (rw) mod q.
Vypočte se v = ((gu1 yu2) mod p) mod q.
Pokud je hodnota v rovna r, podpis platí, jinak nikoli.
Exponent něco-1 výše vždy značí multiplikativní inverzi příslušející určitému modulu.
Naprogramujte algoritmus realizující DSA.