Digital Signature Algorithm

Modèle:Voir homonymes Modèle:À sourcer Le Digital Signature Algorithm, plus connu sous le sigle DSA, est un algorithme de signature numérique standardisé par le NIST aux États-Unis, du temps où le RSA était encore breveté. Cet algorithme faisait partie de la spécification DSS pour Modèle:Lien adoptée en 1993 avant d'être retiré en 2023 (FIPS 186). Une révision mineure a été publiée en 1996 (FIPS 186-1) et le standard a été amélioré en 2002 dans FIPS 186-2. Il est couvert par le brevet n° 5 231 668 aux USA (26 juin 1991) attribué à David Kravitz, ancien employé de la NSA, et il peut être utilisé gratuitement.

Aperçu

Le DSA est similaire à un autre type de signature développée par Modèle:Lien en 1989. Il a aussi des points communs avec la signature ElGamal. Le processus se fait en trois étapes :

• génération des clés ;
• signature du document ;
• vérification du document signé.

Générations des clés

Leur sécurité repose sur la difficulté du problème du logarithme discret dans un groupe finiModèle:Sfn.

• Choisir des longueurs $L$ et $N$ avec $L$ divisible par 64. Ces longueurs définissent directement le niveau de sécurité de la clef. NIST 800-57 recommande de choisir $L=3072$ et $N=256$ pour une sécurité équivalente à 128 bit.
• Choisir un nombre premier $p$ de longueur $L$.
• Choisir un nombre premier $q$ de longueur $N$, de telle façon que $p-1=qz$, avec $z$ un entier.
• Choisir $h$, avec $1<h<p-1$ de manière que $g=h^{z}modp>1$.
• Générer aléatoirement un $x$, avec $0<x<q$.
• Calculer $y=g^{x}modp$.
• La clé publique est $(p,q,g,y)$. La clé privée est $x$.

Signature

• Choisir un nombre aléatoire $s$ tel que $1<s<q$
• Calculer $s_1=(g^{s}modp)modq$
• Si $s1=0$ recommencer avec un autre $s$
• Calculer $s_2=(H(m)+s_{1}x)s^{-1}modq$, où $H(m)$ est le résultat d'un hachage cryptographique, par exemple avec SHA-256, sur le message $m$
• Si $s2=0$ recommencer avec un autre $s$
• La signature est $(s_1,s_2)$

Vérification

• Rejeter la signature si $0<s_1<q$ ou $0<s_2<q$ n'est pas vérifié
• Calculer $w=s_2^{-1}modq$
• Calculer $u_1=H(m)\cdot wmodq$
• Calculer $u_2=s_1\cdot wmodq$
• Calculer $v=(g^{u_1}\cdot y^{u_2}modp)modq$
• La signature est valide si $v=s_1$

Validité de l'algorithme

Ce principe de signature est correct dans le sens où le vérificateur acceptera toujours des signatures authentiques. Ceci peut être démontré comme suit avec un exemple pratique :

À partir de $p-1=qz$ et $g=h^{z}modp$ découle :

$g^q\equiv h^{qz}\equiv h^{p-1}\equiv 1modp$ selon le petit théorème de Fermat. Puisque $g>1$ et $q$ est premier, il s'ensuit que $g$ a un ordre égal à $q$.

Celui qui procède à la signature obtient :

$s_2=s^{-1}(H(m)+x{s}_1)modq.$

Ainsi

$\begin{array}{ccc}s& \equiv & H(m)s_2^{-1}+x{s}_1{s}_2^{-1}\\ & \equiv & H(m)w+x{s}_{1}w(\mathrm{mod}q).\end{array}$

Comme g est d'ordre q, on a :

$\begin{array}{ccc}{g}^s& \equiv & g^{\mathrm{H}(m)w}{g}^{x{s}_{1}w}\\ & \equiv & g^{\mathrm{H}(m)w}{y}^{s_{1}w}\\ & \equiv & g^{u1}{y}^{u2}(\mathrm{mod}p).\end{array}$

Finalement, on aboutit à la validité de DSA :

$s_1=(g^{s}modp)modq=(g^{u1}{y}^{u2}modp)modq=v.$

Annexes

Bibliographie

• Modèle:Ouvrage.

Articles connexes

• Rivest Shamir Adleman
• Signature numérique
• Cryptographie asymétrique
• Elliptic curve digital signature algorithm