Digital Signature Standard

O Padrão de assinatura digital (DSS) é o padrão que usa o algoritmo de assinatura digital (DSA) para seu algoritmo de assinatura e SHA-1 como algoritmo de hash de mensagens. O DSA é uma codificação de chave pública usada apenas para gerar assinaturas digitais e não pode ser usada para criptografia de dados.

A assinatura DSA baseia-se na assinatura do ElGamal, mas é computacionalmente mais econômica porque trabalha com um grupo menor de potências do corpo finito.

Geração da firma

Para gerar a firma $(x,y)$:

1. Escolhe um número primo $p$ de $L$ bits, onde $512\le L\le 1024$ e $L$ é divisível por $64$.
2. Escolhe um número primo $q$ de $160$ bits, tal que $p-1=qz$, onde $z$ é algum número natural.
3. Escolhe $h$, onde $1<h<p-1$ tal que $g=h^{z}modp>1$.
4. Escolhe $x$ de forma aleatória, onde $1<x<q-1$.
5. Calcula $y=g^{x}modp$.

Os dados públicos são $p$, $q$, $g$ e $y$. A firma, a chave privada, é $x$.

Assinatura

Pra assinar à mensagem $m$ por pela firma $(x,y)$:

1. Escolhe um número aleatório $k$, onde $1<k<q$.
2. Calcula $r=(g^{k}modp)modq$.
3. Calcula $s=k^{-1}(H(m)+r\cdot x)modq$, onde $H(m)$ é a função hash SHA-1 aplicada à mensagem $m$.
4. A assinatura é o par $(r,s)$.

Si $r$ ou $s$ é zero, repete!

Verificação

1. Calcula $w=s^{-1}modq$.
2. Calcula $u_1=H(m)\cdot wmodq$.
3. Calcula $u_2=r\cdot wmodq$.
4. Calcula $v=[g{u}_1\cdot y{u}_{2}modp]modq$.
5. A assinatura é válida se $v=r$.

Demostração do Algoritmo

De $g=h^{z}modp$ segue $g^q\equiv h^{qz}\equiv h^{p-1}\equiv 1modp$ pelo Pequeno Teorema de Fermat. Já que $g>1$ e $q$ é primo segue que $g$ tem ordem $q$.

O firmador computa $s=k^{-1}(\mathrm{S}\mathrm{H}\mathrm{A}\mathrm{-}\mathrm{1}(m)+xr)modq.$

Então $k\equiv \mathrm{S}\mathrm{H}\mathrm{A}\mathrm{-}\mathrm{1}(m)s^{-1}+xr{s}^{-1}\equiv \mathrm{S}\mathrm{H}\mathrm{A}\mathrm{-}\mathrm{1}(m)w+xrwmodq.$

Já que $g$ tem ordem $q$, $g^k\equiv g^{\mathrm{S}\mathrm{H}\mathrm{A}\mathrm{-}\mathrm{1}(m)w}{g}^{xrw}\equiv g^{\mathrm{S}\mathrm{H}\mathrm{A}\mathrm{-}\mathrm{1}(m)w}{y}^{rw}\equiv g^{u_1}{y}^{u_2}modp.$

Finalmente, $r=(g^{k}modp)modq=(g^{u_1}{y}^{u_2}modp)modq=v.$