Elliptic curve digital signature algorithm

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Introduction[modifier | modifier le code]

L’algorithme a été proposé en 1992 par Scott Vanstone, en réponse à un appel d'offre pour les signatures numériques du NIST (National Institute of Standards and Technology). Vanstone fonda la société Certicom en 1985, et son entreprise détient la plupart des brevets des algorithmes à base de courbes elliptiques. Les avantages de ECDSA sur DSA et RSA sont des longueurs de clés plus courtes et des opérations de signature et de chiffrement plus rapides.

ECDSA est défini par le standard X9.62-1998, Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA).

Algorithme[modifier | modifier le code]

Soit un élément G d'une courbe elliptique d'ordre n avec n un nombre premier plus grand que 2160. La courbe est également définie par deux éléments a et b qui sont des éléments d'un corps fini de cardinalité q. Soit le message m à signer.

Préparation des clés[modifier | modifier le code]

  • Choisir un entier s entre 1 et n-1.
  • Calculer Q= sG en utilisant l'élément de la courbe elliptique.
  • La clé publique est Q et la clé privée est s.

Signature[modifier | modifier le code]

  • Choisir de manière aléatoire un nombre k entre 1 et n-1
  • Calculer (i,~j) = k~G
  • Calculer x = integer(i)~\bmod~n ; si x = 0, aller à la première étape
  • Calculer y= k^{-1}(H(m) + sx)~\bmod~n où H(m) est le résultat d'un hachage cryptographique sur le message m à signer, souvent SHA-1 (le NIST et l'ANSSI conseillent de ne plus utiliser SHA-1 mais SHA-256 voir SHA-512)
  • Si y = 0, aller à la première étape
  • La signature est la paire (x, y).

Vérification[modifier | modifier le code]

  • Vérifier que Q est différent de O (le point à l'infini) et que Q appartient bien à la courbe elliptique
  • Vérifier que nQ donne O
  • Contrôler que x et y sont bien entre 1 et n-1
  • Calculer (i,j) = (H(m)y^{-1}~\bmod~n)G + (xy^{-1}~\bmod~n)Q
  • Vérifier que x = integer(i)~\bmod~n.

Démonstration[modifier | modifier le code]

\left (H(m)y^{-1}~\bmod~n \right )~G + \Big ( xy^{-1}~\bmod~n\Big )~Q = \left ( H(m)y^{-1}~\bmod~n\right )G + \Big (xy^{-1}~\bmod~n\Big )s~G = \left ( (H(m)  + sx)y^{-1}\right )~\bmod~n~G = \left ( \left (H(m)  + sx\right )k(H(m) + sx)^{-1}\right )~\bmod~n~G = \left (k~\bmod~n\right )~G = k~G = (i,~j)

Donc si x = i ~\bmod~n, la signature est vérifiée.

Sécurité[modifier | modifier le code]

Puisque tous les algorithmes connus pour résoudre le problème du logarithme discret sur les courbes elliptiques sont en O(\sqrt{n}) (Baby-step giant-step, L'algorithme de rho Pollard), la taille du corps doit donc être approximativement deux fois plus grande que le paramètre de sécurité voulu. Pour un degré de sécurité de 128-bits (AES-128, RSA-3072), on prendra une courbe sur un corps \mathbb{F}_q, où q \approx 2^{256}.

Intégration[modifier | modifier le code]

En pratique l'ECDSA repose souvent sur des courbes recommandées par des organisations comme la NIST ou Certicom.

La NIST recommande par exemple quinze courbes elliptiques différentes sur 10 corps différents. Cinq courbes sont recommandées sur cinq corps finis d'ordre p premier \mathbb{F}_{p}, nommées P-192, P-224, P-256, P-384, P-521, dix courbes sur cinq corps finis de la forme \mathbb{F}_{2^m} [1].


Références[modifier | modifier le code]

  1. FIPS PUB 186-3, Digital Signature Standard (DSS)

Liens externes[modifier | modifier le code]