DSA

• 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 hash SHA-1 aplicada al mensaje m.
• La firma es el par (r, s).

Si r o s es cero, se vuelve a repetir 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 ${\displaystyle g=h^{z}{\pmod {p}}}$ sigue ${\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

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

Entonces

${\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

${\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

${\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).