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\leq L\leq 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}\mod p>1$.
4. Escolhe $x$ de forma aleatória, onde $1<x<q-1$.
5. Calcula $y=g^{x}\mod p$.

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}\mod p)\mod q$.
3. Calcula $s=k^{-1}(H(m)+r\cdot x)\mod q$, 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}\mod q$.
2. Calcula $u_{1}=H(m)\cdot w\mod q$.
3. Calcula $u_{2}=r\cdot w\mod q$.
4. Calcula $v=[gu_{1}\cdot yu_{2}\mod p]\mod q$.
5. A assinatura é válida se $v=r$.

Demostração do Algoritmo

De $g=h^{z}\mod p$ segue $g^{q}\equiv h^{qz}\equiv h^{p-1}\equiv 1\mod p$ 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 {SHA-1} (m)+xr)\mod q.$

Então $k\equiv \mathrm {SHA-1} (m)s^{-1}+xrs^{-1}\equiv \mathrm {SHA-1} (m)w+xrw\mod {q}.$

Já que $g$ tem ordem $q$, $g^{k}\equiv g^{\mathrm {SHA-1} (m)w}g^{xrw}\equiv g^{\mathrm {SHA-1} (m)w}y^{rw}\equiv g^{u_{1}}y^{u_{2}}\mod p.$

Finalmente, $r=(g^{k}\mod p)\mod q=(g^{u_{1}}y^{u_{2}}\mod p)\mod q=v.$