Digital Signature Algorithm

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é.

Leur sécurité repose sur la difficulté du problème du logarithme discret dans un groupe fini^[1].

• 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}$ .

• 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})}$ 

• 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}}$ 

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.}$ 

• [Guillot 2013] Philippe. Guillot, La Cryptologie : L'Art des codes secrets, EDP Sciences, 2013, 196 p. (ISBN 978-2-7598-0995-0 et 2759809951, OCLC 854569776, lire en ligne).

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

•   Portail de la cryptologie