DSA

DSA (Digital Signature Algorithm, en español Algoritmo de Firma digital) es un estándar del Gobierno Federal de los Estados Unidos de América o FIPS para firmas digitales. Fue un Algoritmo propuesto por el Instituto Nacional de Normas y Tecnología de los Estados Unidos para su uso en su Estándar de Firma Digital (DSS), especificado en el FIPS 186. DSA se hizo público el 30 de agosto de 1991.

Es un algoritmo puramente asimétrico, junto con RSA. Este algoritmo como su nombre lo indica, sirve para firmar (autenticar), pero no para cifrar información. Una desventaja de este algoritmo es que requiere mucho más tiempo de cómputo que RSA.

• Elegir un número primo p de L bits, donde 512 ≤ L ≤ 1024 y L es divisible por 64.
• Elegir un número primo q de 160 bits, tal que p−1 = qz, donde z es algún número natural.
• Elegir h, donde 1 < h < p − 1 tal que g = h^z(mod p) > 1.
• Elegir x de forma aleatoria, donde 1 < x < q-1.
• Calcular y = g^x(mod p).

Los datos públicos son p, q, g e y. x es la clave privada.

• Elegir un número aleatorio k, donde 1 < k < q.
• Calcular r = (g^k mod p)mod q.
• Calcular s = k^-1(H(m)+r*x) mod q, donde H(m) es la función hashd SHA-1 aplicada al mensaje m.
• La firma es el par (r, s).

Si r o s es cero, se repite el procedimiento.

• 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 firma es válida si v = r.

El esquema de la firma está correcto en el sentido que el verificador aceptará siempre firmas genuinas. Esto puede ser demostrado como sigue:

De g = h z ( mod p ) {\displaystyle g=h^{z}{\pmod {p}}} sigue g q ≡ h q z ≡ h p − 1 ≡ 1 ( mod p ) {\displaystyle g^{q}\equiv h^{qz}\equiv h^{p-1}\equiv 1{\pmod {p}}} por Pequeño teorema de Fermat. Ya que g>1 y q es primo sigue que g tiene orden q.

El firmante computa

s = k − 1 ( SHA-1 ( m ) + x r ) mod q . {\displaystyle s=k^{-1}({\mbox{SHA-1}}(m)+xr)\mod {q}.}

Entonces

k ≡ SHA-1 ( m ) s − 1 + x r s − 1 ≡ SHA-1 ( m ) w + x r w ( mod q ) . {\displaystyle {\begin{matrix}k&\equiv &{\mbox{SHA-1}}(m)s^{-1}+xrs^{-1}\\&\equiv &{\mbox{SHA-1}}(m)w+xrw{\pmod {q}}.\\\end{matrix}}}

Ya que g tiene orden q tenemos que

g k ≡ g S H A − 1 ( m ) w g x r w ≡ g S H A − 1 ( m ) w y r w ≡ g u 1 y u 2 ( mod p ) . {\displaystyle {\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}}}

Finalmente, la correctitud de DSA surge de

r = ( g k mod p ) mod q = ( g u 1 y u 2 mod p ) mod q = v . {\displaystyle r=(g^{k}\mod p)\mod q=(g^{u1}y^{u2}\mod p)\mod q=v.}

• RSA

• FIPS-186, la primera versión de la especificación DSA oficial (en inglés).