Digital Signature Algorithm

Pour les articles homonymes, voir DSA.

Cet article ne cite pas suffisamment ses sources (mars 2016).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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

Signature

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

Vérification

• Rejeter la signature si ${\displaystyle 0<s_{1}<q}$ ou ${\displaystyle 0<s_{2}<q}$ n'est pas vérifié
• Calculer ${\displaystyle w=s_{2}^{-1}{\bmod {q}}}$
• Calculer ${\displaystyle u_{1}=H(m)\cdot w{\bmod {q}}}$
• Calculer ${\displaystyle u_{2}=s_{1}\cdot w{\bmod {q}}}$
• Calculer ${\displaystyle v=(g^{u_{1}}\cdot y^{u_{2}}{\bmod {p}}){\bmod {q}}}$
• La signature est valide si ${\displaystyle 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 ${\displaystyle p-1=qz}$ et ${\displaystyle g=h^{z}{\bmod {p}}}$ découle :

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

Celui qui procède à la signature obtient :

${\displaystyle s_{2}=s^{-1}(H(m)+xs_{1})\mod {q}.}$

Ainsi

${\displaystyle {\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 :

${\displaystyle {\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 :

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

Notes et références

Annexes