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

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

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

Assinatura

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

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

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

Verificação

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

Demostração do Algoritmo

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

O firmador computa s = k − 1 ( S H A − 1 ( m ) + x r ) mod q . {\displaystyle s=k^{-1}(\mathrm {SHA-1} (m)+xr)\mod q.}

Então k ≡ S H A − 1 ( m ) s − 1 + x r s − 1 ≡ S H A − 1 ( m ) w + x r w mod q . {\displaystyle k\equiv \mathrm {SHA-1} (m)s^{-1}+xrs^{-1}\equiv \mathrm {SHA-1} (m)w+xrw\mod {q}.}

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