Algoritmo de assinatura digital - Digital Signature Algorithm

O Digital Signature Algorithm ( DSA ) é um padrão federal de processamento de informações para assinaturas digitais , baseado no conceito matemático de exponenciação modular e no problema de logaritmo discreto . O DSA é uma variante dos esquemas de assinatura Schnorr e ElGamal .

O Instituto Nacional de Padrões e Tecnologia (NIST) propôs o DSA para uso em seu Padrão de Assinatura Digital (DSS) em 1991 e o adotou como FIPS 186 em 1994. Quatro revisões da especificação inicial foram lançadas. A especificação mais recente é FIPS 186-4 de julho de 2013. O DSA é patenteado, mas o NIST tornou essa patente disponível em todo o mundo sem royalties . Uma versão preliminar da especificação FIPS 186-5 indica que o DSA não será mais aprovado para geração de assinatura digital, mas pode ser usado para verificar assinaturas geradas antes da data de implementação desse padrão.

Visão geral

O algoritmo DSA funciona na estrutura de criptosistemas de chave pública e é baseado nas propriedades algébricas de exponenciação modular , juntamente com o problema do logaritmo discreto , que é considerado computacionalmente intratável. O algoritmo usa um par de chaves que consiste em uma chave pública e uma chave privada. A chave privada é usada para gerar uma assinatura digital para uma mensagem, e tal assinatura pode ser verificada usando a chave pública correspondente do assinante. A assinatura digital fornece autenticação de mensagem (o destinatário pode verificar a origem da mensagem), integridade (o destinatário pode verificar se a mensagem não foi modificada desde que foi assinada) e não repúdio (o remetente não pode alegar falsamente que não assinou a mensagem).

História

Em 1982, o governo dos Estados Unidos solicitou propostas para um padrão de assinatura de chave pública. Em agosto de 1991, o Instituto Nacional de Padrões e Tecnologia (NIST) propôs o DSA para uso em seu Padrão de Assinatura Digital (DSS). Inicialmente, houve críticas significativas, especialmente de empresas de software que já haviam investido esforços no desenvolvimento de software de assinatura digital baseado no criptossistema RSA . No entanto, o NIST adotou o DSA como um padrão federal (FIPS 186) em 1994. Quatro revisões da especificação inicial foram lançadas: FIPS 186–1 em 1998, FIPS 186–2 em 2000, FIPS 186–3 em 2009 e FIPS 186 –4 em 2013. Uma versão preliminar do padrão FIPS 186-5 proíbe a assinatura com DSA, enquanto permite a verificação das assinaturas geradas antes da data de implementação do padrão como um documento. Deve ser substituído por esquemas de assinatura mais recentes, como EdDSA .

O DSA está coberto pela Patente dos EUA 5.231.668 , depositada em 26 de julho de 1991 e agora expirada, e atribuída a David W. Kravitz, um ex - funcionário da NSA . Esta patente foi concedida aos "Estados Unidos da América representados pelo Secretário de Comércio , Washington, DC", e o NIST tornou esta patente disponível em todo o mundo sem royalties. Claus P. Schnorr afirma que sua patente US 4.995.082 (também agora expirada) cobria DSA; esta reivindicação é disputada.

Operação

O algoritmo DSA envolve quatro operações: geração de chave (que cria o par de chaves), distribuição de chave, assinatura e verificação de assinatura.

Geração de chave

A geração de chaves tem duas fases. A primeira fase é uma escolha de parâmetros de algoritmo que podem ser compartilhados entre diferentes usuários do sistema, enquanto a segunda fase calcula um único par de chaves para um usuário.

Geração de parâmetros

Escolha uma função de hash criptográfica aprovada com bits de comprimento de saída . No DSS original, sempre foi SHA-1 , mas as funções hash SHA-2 mais fortes são aprovadas para uso no DSS atual. Se for maior que o comprimento do módulo , apenas os bits mais à esquerda da saída de hash são usados. ${\ displaystyle H}$ ${\ displaystyle | H |}$ ${\ displaystyle H}$ ${\ displaystyle | H |}$ ${\ displaystyle N}$ ${\ displaystyle N}$
Escolha um comprimento de chave . O DSS original restrito a ser um múltiplo de 64 entre 512 e 1024 inclusive. O NIST 800-57 recomenda comprimentos de 2.048 (ou 3.072) para chaves com durações de segurança estendendo-se além de 2010 (ou 2030). ${\ displaystyle L}$ ${\ displaystyle L}$
Escolha o comprimento do módulo de modo que e . FIPS 186-4 especifica e deve ter um dos valores: (1024, 160), (2048, 224), (2048, 256) ou (3072, 256). ${\ displaystyle N}$ ${\ displaystyle N <L}$ ${\ displaystyle N \ leq | H |}$ ${\ displaystyle L}$ ${\ displaystyle N}$
Escolha um -bit primo . ${\ displaystyle N}$ ${\ displaystyle q}$
Escolha um -bit primo de modo que - 1 seja um múltiplo de . ${\ displaystyle L}$ ${\ displaystyle p}$ ${\ displaystyle p}$ ${\ displaystyle q}$
Escolha um número inteiro aleatoriamente . ${\ displaystyle h}$ ${\ displaystyle \ {2 \ ldots p-2 \}}$
Compute . No caso raro de tentar novamente com um diferente . Normalmente é usado. Essa exponenciação modular pode ser calculada de forma eficiente, mesmo se os valores forem grandes. ${\ displaystyle g: = h ^ {(p-1) / q} \ mod p}$ ${\ displaystyle g = 1}$ ${\ displaystyle h}$ ${\ displaystyle h = 2}$

Os parâmetros do algoritmo estão ( , , ). Eles podem ser compartilhados entre diferentes usuários do sistema. ${\ displaystyle p}$ ${\ displaystyle q}$ ${\ displaystyle g}$

Chaves por usuário

Dado um conjunto de parâmetros, a segunda fase calcula o par de chaves para um único usuário:

Escolha um número inteiro aleatoriamente . ${\ displaystyle x}$ ${\ displaystyle \ {1 \ ldots q-1 \}}$
Compute . ${\ displaystyle y: = g ^ {x} \ mod p}$

${\ displaystyle x}$ é a chave privada e é a chave pública. ${\ displaystyle y}$

Distribuição de chaves

O signatário deve publicar a chave pública . Ou seja, eles devem enviar a chave ao receptor por meio de um mecanismo confiável, mas não necessariamente secreto. O signatário deve manter a chave privada em segredo. ${\ displaystyle y}$ ${\ displaystyle x}$

Assinando

Uma mensagem é assinada da seguinte forma: ${\ displaystyle m}$

Escolha um número inteiro aleatoriamente de ${\ displaystyle k}$ ${\ displaystyle \ {1 \ ldots q-1 \}}$
Compute . No caso improvável disso , comece novamente com um aleatório diferente . ${\ displaystyle r: = \ left (g ^ {k} {\ bmod {\,}} p \ right) {\ bmod {\,}} q}$ ${\ displaystyle r = 0}$ ${\ displaystyle k}$
Compute . No caso improvável disso , comece novamente com um aleatório diferente . ${\ displaystyle s: = \ left (k ^ {- 1} \ left (H (m) + xr \ right) \ right) {\ bmod {\,}} q}$ ${\ displaystyle s = 0}$ ${\ displaystyle k}$

A assinatura é ${\ displaystyle \ left (r, s \ right)}$

O cálculo de e equivale à criação de uma nova chave por mensagem. A exponenciação modular na computação é a parte computacionalmente mais cara da operação de assinatura, mas pode ser calculada antes que a mensagem seja conhecida. O cálculo do inverso modular é a segunda parte mais cara e também pode ser calculado antes que a mensagem seja conhecida. Pode ser calculado usando o algoritmo Euclidiano estendido ou usando o pequeno teorema de Fermat como . ${\ displaystyle k}$ ${\ displaystyle r}$ ${\ displaystyle r}$ ${\ displaystyle k ^ {- 1} {\ bmod {\,}} q}$ ${\ displaystyle k ^ {q-2} {\ bmod {\,}} q}$

Verificando uma assinatura

Pode-se verificar se uma assinatura é uma assinatura válida para uma mensagem da seguinte maneira: ${\ displaystyle \ left (r, s \ right)}$ ${\ displaystyle m}$

Verifique isso e . ${\ displaystyle 0 <r <q}$ ${\ displaystyle 0 <s <q}$
Compute . ${\ displaystyle w: = s ^ {- 1} {\ bmod {\,}} q}$
Compute . ${\ displaystyle u_ {1}: = H (m) \ cdot w \, {\ bmod {\,}} q}$
Compute . ${\ displaystyle u_ {2}: = r \ cdot w \, {\ bmod {\,}} q}$
Compute . ${\ displaystyle v: = \ left (g ^ {u_ {1}} y ^ {u_ {2}} {\ bmod {\,}} p \ right) {\ bmod {\,}} q}$
A assinatura é válida se e somente se . ${\ displaystyle v = r}$

Exatidão do algoritmo

O esquema de assinatura está correto no sentido de que o verificador sempre aceitará assinaturas genuínas. Isso pode ser demonstrado do seguinte modo:

Em primeiro lugar, desde então , segue-se pelo pequeno teorema de Fermat . Uma vez que e é primo, deve haver ordem . ${\ textstyle g = h ^ {(p-1) / q} ~ {\ text {mod}} ~ p}$ ${\ textstyle g ^ {q} \ equiv h ^ {p-1} \ equiv 1 \ mod p}$ ${\ displaystyle g> 0}$ ${\ displaystyle q}$ ${\ displaystyle g}$ ${\ displaystyle q}$

O signatário calcula

{\ displaystyle s = k ^ {- 1} (H (m) + xr) {\ bmod {\,}} q}

Desse modo

{\ displaystyle {\ begin {alinhados} k & \ equiv H (m) s ^ {- 1} + xrs ^ {- 1} \\ & \ equiv H (m) w + xrw {\ pmod {q}} \ end {alinhado}}}

Como tem ordem , temos ${\ displaystyle g}$ ${\ displaystyle q}$

{\ displaystyle {\ begin {alinhado} g ^ {k} & \ equiv g ^ {H (m) w} g ^ {xrw} \\ & \ equiv g ^ {H (m) w} y ^ {rw} \\ & \ equiv g ^ {u_ {1}} y ^ {u_ {2}} {\ pmod {p}} \ end {alinhado}}}

Finalmente, a correção do DSA segue de

{\ displaystyle {\ begin {alinhados} r & = (g ^ {k} {\ bmod {\,}} p) {\ bmod {\,}} q \\ & = (g ^ {u_ {1}} y ^ {u_ {2}} {\ bmod {\,}} p) {\ bmod {\,}} q \\ & = v \ end {alinhado}}}

Sensibilidade

Com o DSA, a entropia, o sigilo e a exclusividade do valor da assinatura aleatória são essenciais. É tão importante que a violação de qualquer um desses três requisitos pode revelar toda a chave privada a um invasor. Usar o mesmo valor duas vezes (mesmo mantendo segredo), usar um valor previsível ou vazar até mesmo alguns bits de cada uma das várias assinaturas é o suficiente para revelar a chave privada . ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle x}$

Este problema afeta o DSA e o ECDSA - em dezembro de 2010, um grupo que se autodenomina fail0verflow anunciou a recuperação da chave privada ECDSA usada pela Sony para assinar software para o console de jogos PlayStation 3 . O ataque foi possível porque a Sony não conseguiu gerar um novo aleatório para cada assinatura. ${\ displaystyle k}$

Esse problema pode ser evitado derivando deterministicamente da chave privada e do hash da mensagem, conforme descrito pela RFC 6979 . Isso garante que seja diferente para cada um e imprevisível para invasores que não conhecem a chave privada . ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle H (m)}$ ${\ displaystyle x}$

Além disso, implementações maliciosas de DSA e ECDSA podem ser criadas onde for escolhido para vazar informações subliminarmente por meio de assinaturas. Por exemplo, uma chave privada offline pode vazar de um dispositivo offline perfeito que apenas libera assinaturas aparentemente inocentes. ${\ displaystyle k}$

Implementações

Abaixo está uma lista de bibliotecas criptográficas que fornecem suporte para DSA:

Veja também

Referências

links externos

FIPS PUB 186-4: Digital Signature Standard (DSS) , a quarta (e atual) revisão da especificação oficial do DSA.
Recomendação para Gerenciamento de Chaves - Parte 1: geral , NIST Special Publication 800-57, p. 62-63

Languages

In other projects