Digital Signature Algorithm

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.

Sommaire

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 un nombre premier p de Lec 512 ≤ L ≤ 1024, et L est divisible par 64
  • Choisir un nombre premier q de 160 bits, de telle façon que p − 1 = qz, avec z un entier
  • Choisir h, avec 1 < h < p − 1 de manière à ce que g = hz mod p > 1
  • Générer aléatoirement un x, avec 0 < x < q
  • Calculer y = gx mod p
  • La clé publique est (p, q, g, y). La clé privée est x

Signature

  • Choisir un nombre aléatoire s, 1 < s < q
  • Calculer s1 = (gs mod p) mod q
  • Calculer s2 = (H(m) + s1*x)s-1 mod q, où H(m) est le résultat d'un hachage cryptographique, par exemple avec SHA-1, sur le message m
  • La signature est (s1,s2)

Vérification

  • Rejeter la signature si 0<s1<q ou 0<s2<q n'est pas vérifié
  • Calculer w = (s2)-1 (mod q)
  • Calculer u1 = H(m)*w (mod q)
  • Calculer u2 = s1*w (mod q)
  • Calculer v = [gu1*yu2 mod p] mod q
  • La signature est valide si v = s1

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 g = hz mod p découle :

gqhqzhp-1 ≡ 1 (mod 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 effectue par exemple ceci (avec SHA-1) :

s=k^{-1}(\mbox{SHA-1}(m)+xr) \mod{q}.

Ainsi


\begin{matrix}
k & \equiv & \mbox{SHA-1}(m)s^{-1}+xrs^{-1}\\
  & \equiv & \mbox{SHA-1}(m)w + xrw \pmod{q}.\\
\end{matrix}

Comme g a un ordre q, on a :


\begin{matrix}
g^k & \equiv & g^{{\rm SHA-1}(m)w}g^{xrw}\\
    & \equiv & g^{{\rm SHA-1}(m)w}y^{rw}\\
    & \equiv & g^{u1}y^{u2} \pmod{p}.\\
\end{matrix}

Finalement, on aboutit à la validité de DSA :

r=(g^k \mod p) \mod q = (g^{u1}y^{u2} \mod p) \mod q = v.

Voir aussi



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Digital Signature Algorithm de Wikipédia en français (auteurs)

Нужна курсовая?

Regardez d'autres dictionnaires:

  • Digital Signature Algorithm — The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature… …   Wikipedia

  • Digital Signature Algorithm — Der Digital Signature Algorithm (DSA) ist ein Standard der US Regierung für Digitale Signaturen. Er wurde vom National Institute of Standards and Technology (NIST) im August 1991 für die Verwendung in deren Digital Signature Standard (DSS)… …   Deutsch Wikipedia

  • DIGITAL SIGNATURE ALGORITHM — (DSA) схема цифровой подписи, разработанная NIST на основе алгоритма Эль Гамаля (также известна как Digital Signature Standard, DSS). Использует тот же тип ключей, что и алгоритм Диффи Хельмана, работает быстрее RSA …   Словарь электронного бизнеса

  • Elliptic Curve Digital Signature Algorithm — (ECDSA) est un algorithme de signature numérique. C est une variante du standard DSA qui à la différence de l algorithme d origine utilise la cryptographie sur les courbes elliptiques. Les avantages de ECDSA sur DSA et RSA sont des longueurs de… …   Wikipédia en Français

  • Elliptic curve digital signature algorithm — (ECDSA) est un algorithme de signature numérique à clé publique, variante de DSA il fait appel à la cryptographie sur les courbes elliptiques. Sommaire 1 Introduction 2 Algorithme 2.1 Préparation des clé …   Wikipédia en Français

  • Digital Signature Algorithm — …   Википедия

  • Digital Signature Standard — Der Digital Signature Algorithm (DSA) ist ein Standard der US Regierung für Digitale Signaturen. Er wurde vom National Institute of Standards and Technology (NIST) im August 1991 für die Verwendung in deren Digital Signature Standard (DSS)… …   Deutsch Wikipedia

  • Digital Signature Standard — DSS, Digital Signature Standard Создатель: NIST Создан: август 1991 Опубликован: 19 мая 1994 Размер ключа: 512 1024 бит Размер подписи: два числа по 160 бит DSS (Digital Signature Standard)  американский стандарт, описывающий Digital Si …   Википедия

  • Digital signature — This article is about secure cryptographic signatures. For simple signatures in digital form, see Electronic signature. A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital… …   Wikipedia

  • Digital signature forgery — In a cryptographic digital signature or MAC system, digital signature forgery is the ability to create a pair consisting of a message m and a signature (or MAC) σ that is valid for m, where m has not been signed in the past by the legitimate… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”