Assinatura e Certificação Digital - DSA

... ainda dentro de Criptografia Assimétrica ...

O DSA que está para Digital Signature Algorithm ou no português Algoritmo de Assinatura Digital é o sistema padrão para assinaturas digitais do governo americano, e foi proposto em agosto de 1991 pelo NIST o instituto nacional para definição de padrões e tecnologia do governo. O DSA é um algoritmo que se encontra no contexto da criptografia assimétrica fazendo parte naturalmente da infra-estrutura de chaves públicas, porém o algoritmo foi desenvolvido com o único objetivo de ser um padrão para assinaturas digitais, por isto o seu nome. O DSA é protegido pela patente americana 5.231.668 e é atribuído a um funcionário da NSA de nome David W. Kravitz, porém a patente é livre de royalty, ou seja, pode ser utilizada livremente sem necessidade de licença.

            A geração das chaves criptográficas é divido em duas fases; na primeira devem ser definidos os parâmetros do algoritmo que podem ser compartilhados entre diferentes usuários do sistema criptográfico, como segue;

1 – Um dos parâmetros é a escolha de uma função de hash criptográfico sendo definido como a função “H”, por exemplo o SHA-1 ou o utilizado atualmente o SHA-2.

2 – Definir o tamanho das chaves “L” e “N”, observando que o tamanho destas chaves pode definir a força da criptografia. O valor de “L” deve ser um múltiplo de 64 entre 512 e 1024 (inclusive) sendo recomendando chaves de comprimento entre 2048 e 3072 dígitos, e por conseguinte o valor de “N” também deve ser grande. Mais especificamente os valores serão pares como; 1024 e 160, 2048 e 224, 2048 e 256, 3072 e 256 para “L” e “N” respectivamente.

3 – Definir um valor para “q” que seja um primo de N-bit, para tal, o valor de N deverá ser menor ou igual ao tamanho da saída do função de hash criptográfico.

4 – Definir um valor L-bit primo e módulo de “p”, de maneira que p-1 seja múltiplo de “q”.

5 – Definir um valor para “g”, um número do qual deve ser multiplicativo e a ordem módulo de “p” deve ser igual a “q”. Isto pode ser obtido pela expressão “g=h(p-1)/q mod p” para um valor de “h” arbitrário, de maneira que “h” seja maior que 1 e menor que p-1, e tentar novamente se o valor obtido para “h” for igual a 1. A maioria das escolhas de “h” irá levar a um valor válido para “g”; o que normalmente 2 será um valor válido para “h”.

Vale notar que os valores de “p”, “q” e “g” podem ser compartilhados entre os diferentes usuários do sistema de criptografia.

            A segunda fase é a computação das chaves privadas e públicas para um determinado usuário, de maneira que para computação destas chaves deve ser seguido os seguintes passos;

1 – Definir um valor de “x” por um método randômico, onde “x” deverá ser maior que 0 e menor que “q”.

2 – Calcular o valor de “y” que obedeça a expressão y=g^x mod p.

3 – A chave pública é então a formação de “p”, “q”, “g” e “y”, e a chave privada é “x”.

            Existem algoritmos eficientes para a computação de exponenciação modular h^a mod p, e g^x mod p, tal como a exponenciação ao quadrado.

            Para assinar uma mensagem, devemos assumir “H” como uma função de hash criptográfica e “m” a mensagem a ser criptografada, então os seguintes passos devem ser seguidos;

1 – Definir para “k” um número randômico onde “k” deve ser maior que 0 (zero) e menor que “q”;

2 – Calcular um valor para “r” de maneira a obedecer a expressão “r=(g^k mod p) mod q”;

3 – Calcular o valor de “s” que respeite a expressão “s=(k-1 (H(m) + r*x)) mod q;

4 – Recalcular a assinatura se por acaso o valor de “r” ou “s” for igual a 0 (zero);

5 – A assinatura é então composta por (r, s);

A extensão do algoritmo de Euclidean pode ser utilizado para computar o inverso modular “k^-1 mod q”.

            A verificação de uma assinatura             é composta pelos seguintes passos;

1 – Rejeitar a assinatura se as expressões 0 < r < q ou 0 < s < q não forem satisfeitas.

2 – Calcular o valor de “w” de maneira a atender a expressão w = (s)^-1 mod q;

3 – Calcular o valor de “u1” de maneira a atender a expressão u1 = (H(m)*w) mod q;

4 – Calcular o valor de “u2” que obedece a expressão u2 = (r*w) mod q;

5 – Calcular o valor de “v” que obedece a expressão v=((gu1*yu2) mod p) mod q;

6 – A assinatura só é válida se o valor de “v” for igual ao valor de “r”.