Worldlex Wiki En cryptographie , l' algorithme de signature numérique à courbe elliptique ( ECDSA ) propose une variante de l' algorithme de signature numérique (DSA) qui utilise la cryptographie à courbe elliptique .
Tailles des clés et des signatures
Comme pour la cryptographie à courbe elliptique en général, la taille en bits de la clé privée censée être nécessaire pour ECDSA est environ deux fois supérieure à la taille du niveau de sécurité , en bits. Par exemple, à un niveau de sécurité de 80 bits (ce qui signifie qu'un attaquant a besoin d'un maximum d'environ opérations pour trouver la clé privée), la taille d'une clé privée ECDSA serait de 160 bits. En revanche, la taille de la signature est la même pour DSA et ECDSA : environ bits, où est l'exposant dans la formule , soit environ 320 bits pour un niveau de sécurité de 80 bits, ce qui équivaut à opérations.
Algorithme de génération de signature
Supposons qu'Alice veuille envoyer un message signé à Bob . Au départ, ils doivent se mettre d'accord sur les paramètres de la courbe . En plus du corps et de l'équation de la courbe, nous avons besoin de , un point de base d'ordre premier sur la courbe ; est l'ordre multiplicatif du point .
| Paramètre | |
|---|---|
| COURBE | le champ de courbes elliptiques et l'équation utilisée |
| G | point de base de la courbe elliptique, un point sur la courbe qui génère un sous-groupe de grand ordre premier n |
| n | ordre entier de G , signifie que , où est l'élément identité. |
| la clé privée (choisie au hasard) | |
| la clé publique (calculée par courbe elliptique) | |
| m | le message à envoyer L'ordre du point de base doit être premier . En effet, on suppose que tout élément non nul de l' anneau est inversible, donc que doit être un corps . Cela implique que doit être premier (cf. identité de Bézout ). Alice crée une paire de clés, composée d'un entier de clé privée , sélectionné aléatoirement dans l'intervalle ; et d'un point de courbe de clé publique . Nous utilisons pour désigner la multiplication d'un point de courbe elliptique par un scalaire . Pour qu'Alice signe un message , elle suit ces étapes :
Comme le note la norme, il n'est pas seulement nécessaire que le mot de passe soit secret, mais il est également crucial de sélectionner des valeurs différentes pour différentes signatures. Sinon, l'équation de l'étape 6 peut être résolue pour , la clé privée : étant donné deux signatures et , en utilisant la même inconnue pour différents messages connus et , un attaquant peut calculer et , et puisque (toutes les opérations dans ce paragraphe sont effectuées modulo ) l'attaquant peut trouver . Puisque , l'attaquant peut maintenant calculer la clé privée . Cette erreur d'implémentation a été utilisée, par exemple, pour extraire la clé de signature utilisée pour la console de jeu PlayStation 3. Une autre façon dont la signature ECDSA peut divulguer des clés privées est lorsqu'elle est générée par un générateur de nombres aléatoires défectueux . Une telle défaillance dans la génération de nombres aléatoires a entraîné la perte de fonds des utilisateurs d'Android Bitcoin Wallet en août 2013. Pour garantir que chaque message est unique, on peut contourner complètement la génération de nombres aléatoires et générer des signatures déterministes en dérivant à la fois du message et de la clé privée. Algorithme de vérification de signaturePour que Bob puisse authentifier la signature d'Alice sur un message , il doit disposer d'une copie de sa clé publique curve point . Bob peut vérifier qu'il s'agit d'un curve point valide comme suit :
Après cela, Bob suit ces étapes :
Notez qu'une implémentation efficace ne calculerait l'inverse qu'une seule fois. De plus, en utilisant l'astuce de Shamir, une somme de deux multiplications scalaires peut être calculée plus rapidement que deux multiplications scalaires effectuées indépendamment. Exactitude de l'algorithmeIl n'est pas immédiatement évident de comprendre pourquoi la vérification fonctionne correctement. Pour comprendre pourquoi, notons C le point de la courbe calculé à l'étape 5 de la vérification, D'après la définition de la clé publique comme , Étant donné que la multiplication scalaire de la courbe elliptique se répartit sur l'addition, En élargissant la définition de et à partir de l'étape de vérification 4, Recueillir le terme commun , En élargissant la définition de s à partir de l'étape de signature 6, Étant donné que l'inverse d'un inverse est l'élément d'origine et que le produit de l'inverse d'un élément et de l'élément est l'identité, il nous reste D'après la définition de r , il s'agit de l'étape de vérification 6. Cela montre seulement qu'un message correctement signé sera vérifié correctement ; d'autres propriétés telles que les messages incorrectement signés qui ne sont pas vérifiés correctement et la résistance aux attaques cryptanalytiques sont nécessaires pour un algorithme de signature sécurisé. Récupération de clé publiqueÉtant donné un message m et la signature d'Alice sur ce message, Bob peut (potentiellement) récupérer la clé publique d'Alice :
Notez qu'une signature invalide ou une signature provenant d'un autre message entraînera la récupération d'une clé publique incorrecte. L'algorithme de récupération ne peut être utilisé pour vérifier la validité d'une signature que si la clé publique du signataire (ou son hachage) est connue au préalable. Exactitude de l'algorithme de récupérationCommencez par la définition de l'étape de récupération 6, D'après la définition de l'étape de signature 4, Étant donné que la multiplication scalaire de la courbe elliptique se répartit sur l'addition, Élargissement de la définition de et à partir de l'étape de récupération 5, En élargissant la définition de s à partir de l'étape de signature 6, Étant donné que le produit de l'inverse d'un élément et de l'élément est l'identité, il nous reste Les premier et deuxième termes s'annulent, D'après la définition de , il s'agit de la clé publique d'Alice. Cela montre qu'un message correctement signé récupérera la clé publique correcte, à condition que des informations supplémentaires aient été partagées pour calculer de manière unique le point de courbe à partir de la valeur de signature r . SécuritéEn décembre 2010, un groupe se faisant appeler fail0verflow a annoncé la récupération de la clé privée ECDSA utilisée par Sony pour signer des logiciels pour la console de jeu PlayStation 3. Cependant, cette attaque n'a fonctionné que parce que Sony n'a pas correctement implémenté l'algorithme, car il était statique au lieu d'être aléatoire. Comme indiqué dans la section Algorithme de génération de signature ci-dessus, cela rend l'algorithme entier inutilisable. Le 29 mars 2011, deux chercheurs ont publié un article de l'IACR démontrant qu'il est possible de récupérer une clé privée TLS d'un serveur utilisant OpenSSL qui s'authentifie avec Elliptic Curves DSA sur un champ binaire via une attaque temporelle . La vulnérabilité a été corrigée dans OpenSSL 1.0.0e. En août 2013, il a été révélé que des bugs dans certaines implémentations de la classe Java SecureRandom généraient parfois des collisions dans la valeur. Cela a permis aux pirates de récupérer des clés privées leur donnant le même contrôle sur les transactions Bitcoin que les propriétaires de clés légitimes, en utilisant le même exploit qui a été utilisé pour révéler la clé de signature PS3 sur certaines implémentations d'applications Android , qui utilisent Java et s'appuient sur ECDSA pour authentifier les transactions. Ce problème peut être évité par une génération déterministe de k, comme décrit par la RFC 6979. PréoccupationsQuelques inquiétudes exprimées à propos de l’ECDSA :
ImplémentationsVous trouverez ci-dessous une liste de bibliothèques cryptographiques prenant en charge ECDSA : |