DSA

DSA (acrònim de Digital Signature Algorithm, en català Algorisme de Signatura digital) és un estàndard del Govern Federal dels Estats Units d'Amèrica o FIPS per a signatures digitals. Va ser un Algorisme proposat per l'Institut Nacional de Normes i Tecnologia dels Estats Units a l'agost de 1991 per a l'ús en el seu Digital Signature Standard (DSS), en català Estàndard de Signatura Digital, especificat en el FIPS 186 el 1993. Hi ha hagut quatre revisions des del seu llançament: FIPS 186-1 el 1996, FIPS 186-2 el 2000, FIPS 186-3 el 2009, i FIPS 186-4 el 2013.

Aquest algorisme com el seu nom ho indica, serveix per signar i no per xifrar informació. Un desavantatge d'aquest algorisme és que requereix molt més temps de còmput que RSA.

Generació de claus

La generació de claus té dues fases La primera fase és una opció de paràmetres de l'algorisme que poden ser compartits entre els diferents usuaris del sistema, mentre que la segona fase calcula claus públiques i privades per a un sol usuari.

Primera fase, generació de paràmetres

• Triar un nombre primer p de L bits, on 512 ≤ L ≤ 1024 i L és divisible per 64.
• Triar un nombre primer q de 160 bits, tal que p−1 = qz, on z és algun nombre natural.
• Triar h, on 1 < h < p − 1 tal que g = h^z(mod p) > 1.

Segona fase, generar les claus pels usuaris

• Triar x de forma aleatòria, on 1 < x < q-1.
• Calcular y = g^x(mod p).

Les dades públiques són p, q, g i y. x és la clau privada.

Signatura

• Triar un nombre aleatori k, on 1 < k < q.
• Calcular r = (g^k mod p)mod q.
• Calcular s = k^-1(H(m)+r*x) mod q, on H(m) és la funció hash SHA-1 aplicada al missatge m.
• La signatura és el parell (r, s).

Si r o s és zero, es torna a repetir el procediment.

Verificació

• Calcular w = (s)^-1(mod q).
• Calcular u1 = H(m)*w(mod q).
• Calcular u2 = r*w(mod q).
• Calcular v = [g^u1*y^u2mod p] mod q.
• La signatura és vàlida si v = r.

Demostració de l'algorisme

L'esquema de la signatura està correcte en el sentit que el verificador acceptarà sempre signatures genuïnes. Això pot ser demostrat com segueix:

De $g=h^{z}{\pmod {p}}$ segueix $g^{q}\equiv h^{qz}\equiv h^{p-1}\equiv 1{\pmod {p}}$ pel Petit teorema de Fermat.

Ja que g > 1 i q és primer, segueix que g té ordre q.

El signant calcula: $s=k^{-1}({\mbox{SHA-1}}(m)+xr)\mod {q}.$

Llavors: ${\begin{matrix}k&\equiv &{\mbox{SHA-1}}(m)s^{-1}+xrs^{-1}\\&\equiv &{\mbox{SHA-1}}(m)w+xrw{\pmod {q}}.\\\end{matrix}}$

Ja que g té ordre q s'ha de

${\begin{matrix}g^{k}&\equiv &g^{{\rm {SHA-1}}(m)w}g^{xrw}\\&\equiv &g^{{\rm {SHA-1}}(m)w}y^{rw}\\&\equiv &g^{u1}y^{u2}{\pmod {p}}.\\\end{matrix}}$

Finalment, la correctitud de DSA sorgeix de

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

Vegeu també

• RSA
• Clau
• Signatura digital
• Criptografia de corba el·líptica

Enllaços externs

• FIPS PUB 186-4: Digital Signature Standard (DSS), la versió actual, la quarta, de l'especificació oficial de l'algorisme DSA. (anglès)
• Recommendation for Key Management -- Part 1: general, NIST Special Publication 800-57, p. 62–63 (anglès)
• FIPS-186, la primera versió de l'especificació DSA oficial. (anglès)