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çuModifier

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

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

  • Choisir des longueurs   et   avec   divisible par 64. Ces longueurs définissent directement le niveau de sécurité de la clef. NIST 800-57 recommande de choisir   et   pour une sécurité équivalente à 128 bit.
  • Choisir un nombre premier   de longueur  .
  • Choisir un nombre premier   de longueur  , de telle façon que  , avec   un entier
  • Choisir  , avec   de manière que  
  • Générer aléatoirement un  , avec  
  • Calculer  
  • La clé publique est  . La clé privée est  .

SignatureModifier

  • Choisir un nombre aléatoire   tel que  
  • Calculer  
  • Si   recommencer avec un autre  
  • Calculer  , où   est le résultat d'un hachage cryptographique, par exemple avec SHA-256, sur le message  
  • Si   recommencer avec un autre  
  • La signature est  

VérificationModifier

  • Rejeter la signature si   ou   n'est pas vérifié
  • Calculer  
  • Calculer  
  • Calculer  
  • Calculer  
  • La signature est valide si  

Validité de l'algorithmeModifier

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   et   découle :

  selon le petit théorème de Fermat. Puisque   et   est premier, il s'ensuit que   a un ordre égal à  .

Celui qui procède à la signature obtient :

 

Ainsi

 

Comme g est d'ordre q, on a :

 

Finalement, on aboutit à la validité de DSA :

 

Notes et référencesModifier

(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).
  1. Guillot, Philippe., La cryptologie : l'art des codes secrets, EDP Sciences, , 196 p. (ISBN 978-2-7598-0995-0 et 2759809951, OCLC 854569776, lire en ligne), p. 60

AnnexesModifier

Articles connexesModifier