Elliptic curve digital signature algorithm

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

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 ANSI X9.62-1998, Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA).

Algorithme

Soit une courbe de formule $y^{2}=x^{3}+ax+b$ c'est une courbe elliptique sur un corps d'entiers fini modulo p avec p un nombre premier et un point G de la courbe. L'ordre de G est n, le plus petit entier tel que nG donne $O$ le point à l'infini de la courbe et élément neutre du groupe commutatif sur les points de la courbe.

Préparation des clés

• Choisir un entier s entre $1$ et $p-1$ qui sera la clé privée.
• 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

• Choisir de manière aléatoire un nombre k entre 1 et n-1
  • voir Annexe B5 de FIPS 186-4 pour les méthodes recommandées de génération de ce nombre.
  • Sony lors de la sécurisation de la PS3 n'a pas suffisamment pris de soin lors du choix de ce nombre ce qui a permis la recuperation de la clé privée
  • EdDSA utilise une méthode déterministe pour calculer ce nonce cryptographique
  • Pour la signature des transactions de cryptomonnaies certaines implementations utlisent un calcul de type HMAC pour obtenir k
• Calculer $(i,~j)=k~G$
• Calculer $x=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 ou SHA-512, ethereum utilise Keccak-256, une variante de SHA-3)
• Si $y=0$, aller à la première étape
• La signature est la paire (x, y).

Vérification

• 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=i~{\bmod {~}}n$.

Démonstration

$\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é

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

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

Annexes

Articles connexes

• EdDSA, autre signature utilisant une courbe elliptique et basée sur Twisted Edwards curve (en)
• Curve25519, basée sur edDSA et protégée contre les générateurs de nombres pseudo-aléatoires défaillants

Liens externes

• « ECDSA, technologie clé de bitcoin », 20160315110426 (archivé sur Internet Archive).