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 ${\displaystyle (x,y)}$:

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

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

Assinatura

Pra assinar à mensagem ${\displaystyle m}$ por pela firma ${\displaystyle (x,y)}$:

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

Si ${\displaystyle r}$ ou ${\displaystyle s}$ é zero, repete!

Verificação

1. Calcula ${\displaystyle w=s^{-1}\mod q}$.
2. Calcula ${\displaystyle u_{1}=H(m)\cdot w\mod q}$.
3. Calcula ${\displaystyle u_{2}=r\cdot w\mod q}$.
4. Calcula ${\displaystyle v=[gu_{1}\cdot yu_{2}\mod p]\mod q}$.
5. A assinatura é válida se ${\displaystyle v=r}$.

Demonstração do Algoritmo

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

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

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

Já que ${\displaystyle g}$ tem ordem ${\displaystyle q}$, ${\displaystyle 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, ${\displaystyle r=(g^{k}\mod p)\mod q=(g^{u_{1}}y^{u_{2}}\mod p)\mod q=v.}$