Digital Signature Algorithm

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 fait partie de la spécification DSS pour Digital Signature Standard adoptée en 1993 (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 Claus-Peter Schnorr (en) 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 fini.

• 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}{\bmod {p}}>1$
• Générer aléatoirement un $x$, avec $0<x<q$
• Calculer $y=g^{x}{\bmod {p}}$
• 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}\mod p)\mod q$
• Si $s1=0$ recommencer avec un autre $s$
• Calculer $s_{2}=(H(m)+s_{1}x)s^{-1}\mod q$, 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}{\bmod {q}}$
• Calculer $u_{1}=H(m)\cdot w{\bmod {q}}$
• Calculer $u_{2}=s_{1}\cdot w{\bmod {q}}$
• Calculer $(v=g^{u_{1}}\cdot y^{u_{2}}{\bmod {p}}){\bmod {q}}$
• 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}{\bmod {p}}$ découle :

$g^{q}\equiv h^{qz}\equiv h^{p-1}\equiv 1{\bmod {p}}$ 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)+xs_{1})\mod {q}.$

Ainsi

${\begin{matrix}s&\equiv &H(m)s_{2}^{-1}+xs_{1}s_{2}^{-1}\\&\equiv &H(m)w+xs_{1}w{\pmod {q}}.\\\end{matrix}}$

Comme g est d'ordre q, on a :

${\begin{matrix}g^{s}&\equiv &g^{{\rm {H}}(m)w}g^{xs_{1}w}\\&\equiv &g^{{\rm {H}}(m)w}y^{s_{1}w}\\&\equiv &g^{u1}y^{u2}{\pmod {p}}.\\\end{matrix}}$

Finalement, on aboutit à la validité de DSA :

$s_{1}=(g^{s}\mod p)\mod q=(g^{u1}y^{u2}\mod p)\mod q=v.$

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Digital Signature Algorithm » (voir la liste des auteurs).

Annexes

Articles connexes

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