Elliptic curve digital signature algorithm

{{#ifeq:||Un article de Ziki, l'encyclopédie libre.|Une page de Ziki, l'encyclopédie libre.}}
Révision datée du 10 mars 2023 à 19:16 par >TorkMattar
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)

Modèle:Langue du titre Modèle:Lang (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'offres pour les signatures numériques du National Institute of Standards and Technology (NIST). 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)<ref>draft ANSI X9.62-1998</ref>.

Algorithme

Soit une courbe de formule <math>y^2 = x^3 + ax + b</math>. 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 (appelé point de base). L'ordre de G est n, le plus petit entier tel que nG donne <math>O</math> le point à l'infini de la courbe et élément neutre du groupe commutatif sur les points de la courbe. Pour que tous les entiers entre 1 et n-1 soient inversibles modulo n, il est impératif que l'anneau <math>\mathbb{Z}/n\mathbb{Z}</math> soit un corps, et donc que n soit un nombre premier (c'est une conséquence du théorème de Bézout). Ainsi, dans ce qui suit, la notation <math>k^{-1} \text{ mod } n</math> lorsque <math>k</math> est un entier entre 1 et n-1 désigne l'inverse de <math>k</math> dans le corps <math>\mathbb{Z}/n\mathbb{Z}</math>.

Préparation des clés

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

Signature

Comme indiqué dans les normes, il est crucial que, non seulement <math>k</math> soit secret (sinon on peut trouver <math>s</math> à partir de la signature et <math>y= k^{-1}(H(m) + sx)</math>), mais aussi de choisir un <math>k</math> différent à chaque signature (en tirant <math>k</math> 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 <math>(x, y)</math> et <math>(x, y')</math>, utilisant le même <math>k</math> pour deux messages <math>m</math> et <math>m'</math>, et comme <math>y - y' = k^{-1}(H(m) - H(m'))</math> (mod <math>n</math>), on trouve <math>k = \frac{H(m) - H(m')}{y - y'}</math> et donc <math>s</math> en utilisant <math>y= k^{-1}(H(m) + sx)</math>.

Vérification

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

Démonstration

<math>\left (H(m)y^{-1}~\bmod~n \right )~G + \Big ( xy^{-1}~\bmod~n\Big )~Q</math>

<math>= \left ( H(m)y^{-1}~\bmod~n\right )G + \Big (xy^{-1}~\bmod~n\Big )s~G</math>

<math>= \left ( (H(m) + sx)y^{-1}\right )~\bmod~n~G</math>

<math>= \left ( \left (H(m) + sx\right )k(H(m) + sx)^{-1}\right )~\bmod~n~G</math>

<math>= \left (k~\bmod~n\right )~G</math> <math>= k~G</math> <math>= (i,~j)</math>

Donc si <math>x = i ~\bmod~n</math>, 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 <math>O(\sqrt{n})</math> (baby-step giant-step, 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 <math>\mathbb{F}_q</math>, où <math>q \approx 2^{256}</math>.

Intégration

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

Le NIST recommande par exemple quinze courbes elliptiques différentes sur dix corps différents. Cinq courbes sont recommandées sur cinq corps finis d'ordre p premier <math>\mathbb{F}_{p}</math>, nommées P-192, P-224, P-256, P-384, P-521, dix courbes sur cinq corps finis de la forme <math>\mathbb{F}_{2^m}</math> <ref>FIPS PUB 186-4, Digital Signature Standard (DSS)</ref>.

L'ANSSI recommande l'utilisation de la courbe FRP256v1, dont les paramètres ont été publiés au Journal Officiel<ref>Avis relatif aux paramètres de courbes elliptiques définis par l’État français, Journal officiel n°241 du 16/10/2011.</ref> en 2011, et les courbes P-256, P-384, P-521, B-283, B-409 et B-571 définies dans le FIPS 186-2<ref>Référentiel Général de Sécurité, Annexe B1, "Mécanismes cryptographiques Règles et recommandations concernant le choix et le dimensionnement des mécanismes cryptographiques".</ref>.

Notes et références

Modèle:Références

Annexes

Articles connexes

Liens externes

Modèle:Palette Bitcoin Modèle:Portail

Récupérée de « https://wiki.trucsazeb.re:443/index.php?title=Elliptic_curve_digital_signature_algorithm&oldid=80674 »