Elliptic curve digital signature algorithm

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

• Choisir de manière aléatoire un nombre k entre 1 et n-1
  • voir Annexe B5 de FIPS 186-4[2] 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 de retrouver la clé privée[3] - [4]
  • EdDSA utilise une méthode déterministe pour calculer ce nonce cryptographique
  • Pour la signature des transactions de cryptomonnaies, certaines implémentations[5] utilisent un calcul de type HMAC pour obtenir k
• Calculer ${\displaystyle (i,~j)=k~G}$
• Calculer ${\displaystyle x=i~{\bmod {~}}n}$ ; si ${\displaystyle x=0}$, aller à la première étape
• Calculer ${\displaystyle 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 ${\displaystyle y=0}$, aller à la première étape
• La signature est la paire (x, y).

Comme indiqué dans les normes, il est crucial que, non seulement ${\displaystyle k}$ soit secret (sinon on peut trouver ${\displaystyle s}$ à partir de la signature et ${\displaystyle y=k^{-1}(H(m)+sx)}$), mais aussi de choisir un ${\displaystyle k}$ différent à chaque signature (en tirant ${\displaystyle k}$ au hasard, la probabilité de tomber sur un nombre déjà utilisé est du même ordre que de trouver la clé privée par hasard) car sinon, on peut trouver la clé privée : avec deux signatures ${\displaystyle (x,y)}$ et ${\displaystyle (x,y')}$, utilisant le même ${\displaystyle k}$ pour deux messages ${\displaystyle m}$ et ${\displaystyle m'}$, et comme ${\displaystyle y-y'=k^{-1}(H(m)-H(m'))}$ (mod ${\displaystyle n}$), on trouve ${\displaystyle k={\frac {H(m)-H(m')}{y-y'}}}$ et donc ${\displaystyle s}$ en utilisant ${\displaystyle y=k^{-1}(H(m)+sx)}$.

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

${\displaystyle \left(H(m)y^{-1}~{\bmod {~}}n\right)~G+{\Big (}xy^{-1}~{\bmod {~}}n{\Big )}~Q}$

${\displaystyle =\left(H(m)y^{-1}~{\bmod {~}}n\right)G+{\Big (}xy^{-1}~{\bmod {~}}n{\Big )}s~G}$

${\displaystyle =\left((H(m)+sx)y^{-1}\right)~{\bmod {~}}n~G}$

${\displaystyle =\left(\left(H(m)+sx\right)k(H(m)+sx)^{-1}\right)~{\bmod {~}}n~G}$

${\displaystyle =\left(k~{\bmod {~}}n\right)~G}$ ${\displaystyle =k~G}$ ${\displaystyle =(i,~j)}$

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

• EdDSA, autre signature utilisant une courbe elliptique et basée sur la courbe d'Edwards tordue
• Curve25519, basée sur edDSA et protégée contre les générateurs de nombres pseudo-aléatoires défaillants

• « ECDSA, technologie clé de bitcoin » (version du 15 mars 2016 sur Internet Archive).