• Loïc Morel

Les signatures numériques - extrait ebook Bitcoin Démocratisé 1.



Sommaire :



Ce premier tome est en quelque sorte préparatoire pour la suite de la série d’ebooks. Nous allons y étudier les différents algorithmes liés à la cryptographie qui interviennent au sein du protocole Bitcoin. L’objectif sera de vulgariser et d’entrer dans le détail, mais promis, je ne vais pas vous faire un cours de mathématiques pures. Il y en aura un petit peu, puisqu’elles sont à la base de la cryptographie, mais le but sera que quiconque puisse comprendre l’idée derrière chaque mécanisme.


Toute la sécurité inhérente à Bitcoin est basée sur cette cryptographie. On la retrouve à tous les étages du protocole. La cryptographie est dans les wallets, dans les blocs, dans la communication… Elle est omniprésente dans Bitcoin. Comprendre comment elle fonctionne, et pourquoi elle est utilisée dans le protocole, représente selon moi un premier pas indispensable pour étudier par la suite les rouages techniques de Bitcoin.


Mais finalement, c’est quoi la cryptographie ?


Etymologiquement, le mot “cryptographie” vient des mots en grec ancien “kruptos” qui veut dire “caché”, et “graphein” qui veut dire “écriture”. La cryptographie est donc initialement la science de cacher un message.


On la classe parmi les sciences de la cryptologie qui englobent également l’authentification, la non-répudiation ou encore la cryptanalyse. Aujourd’hui, on confond souvent ces deux termes en un seul. Ainsi, selon le NIST (National Institute of Standards and Technology), la cryptographie moderne est une discipline qui incarne les principes, les moyens et les méthodes de transformation des données afin de masquer leur contenu sémantique, d'empêcher leur utilisation non autorisée ou d'empêcher leur modification non détectée.


Il est intéressant de remarquer que cette discipline existe au moins depuis l’antiquité avec notamment le chiffre de César, une méthode de chiffrement d’un message par simple décalage de lettres.


Dans le protocole Bitcoin, les deux principales applications de la cryptographie sont les fonctions de hachage et les signatures numériques. Voyons ensemble ce en quoi elles consistent.


 

Si vous ne comprenez pas certains mots techniques utilisés dans cet article, nous avons rédigé un glossaire permettant de définir tous ces termes. Retrouvez le en cliquant ici : https://www.pandul.fr/post/glossaire-s%C3%A9rie-d-ebooks-bitcoin-d%C3%A9mocratis%C3%A9


Cet article reprend exclusivement la deuxième partie de l'ebook Bitcoin Démocratisé 1. Cette partie a été légèrement modifiée par rapport à l'ouvrage original afin de l'adapter au format du blog. Pour accéder à la première partie portant sur les fonctions de hachage, cliquez ici : https://www.pandul.fr/ressources


Cet ouvrage est mis à disposition selon les termes de la Licence Creative Commons : Attribution - Partage dans les Mêmes Conditions 4.0 International (CC BY-SA 4.0), à l'exception des logos de Pandul seuls qui demeurent la propriété intellectuelle de l'Ei Loïc Morel.


Pour en savoir plus, cliquez ici :

https://creativecommons.org/licenses/by-sa/4.0/


Merci à l’ensemble des personnes qui m’ont apporté leur aide, leurs conseils d’experts et leurs encouragements sur l'ouvrage original :

Merci également à tous ceux qui m’ont apporté leur aide sur ce projet mais qui ont préféré rester anonymes.

 



Introduction aux signatures numériques.


La deuxième application de la cryptographie dans Bitcoin regroupe les algorithmes de signatures numériques. Voyons ensemble en quoi cela consiste et comment cela fonctionne.


Le mot “portefeuille” (wallet) dans Bitcoin a été assez mal choisi selon moi. En effet, ce que l’on appelle “portefeuille” Bitcoin est un logiciel qui ne conserve pas directement vos bitcoins, contrairement à un portefeuille classique qui permet de conserver des pièces.


Pour rappel, “Bitcoin” avec un “B” majuscule désigne le système de paiement électronique pair à pair, le protocole ou le réseau. “bitcoin” avec un “b” minuscule désigne l’unité de compte de ce système.

Les bitcoins sont simplement des unités de compte natives du réseau de paiement homographe. Cette unité de compte est représentée par des UTXO (Unspent Transaction Output), qui sont des sorties de transactions pas encore dépensées. Si ces sorties ne sont pas dépensées, cela veut dire par déduction qu’elles appartiennent à un utilisateur. Les UTXO sont en quelque sorte des fractions de bitcoins, d’une taille variable, appartenant à un utilisateur.


Le protocole Bitcoin est distribué, il fonctionne sans autorité centrale. On ne peut donc pas faire comme sur les livres de comptes bancaires où les euros qui vous appartiennent sont simplement associés à votre identité personnelle. Sur le réseau Bitcoin, on associe la propriété des UTXO à une clé publique, elle-même liée mathématiquement à une clé privée.


Comme leurs noms l’indiquent, la clé publique est connue de tous et la clé privée est uniquement connue par le propriétaire des fonds.


Pour pouvoir dépenser les bitcoins associés à une clé publique, un utilisateur va devoir remplir des conditions de dépenses qui avaient été créées lors de la transaction précédente. Généralement, la condition de dépense consiste à prouver au reste du réseau que l’utilisateur est bien le propriétaire légitime de la clé publique associée à l’UTXO qu’il souhaite dépenser.


Il va donc devoir établir une preuve irréfutable qu’il connaît la clé privée associée à cette clé publique, sans pour autant dévoiler ladite clé privée au reste du réseau.

Pour ce faire, un utilisateur qui initie une transaction doit établir une signature numérique à l’aide de sa clé privée sur la transaction en question. La signature pourra être vérifiée par les autres parties prenantes au réseau. Si elle est valide, cela veut dire que l’utilisateur qui initie la transaction est bien le propriétaire de la clé privée, et donc qu’il est bien le propriétaire des bitcoins qu’il souhaite dépenser. Les autres utilisateurs pourront alors exécuter la transaction.


En conséquence, un utilisateur qui possède des bitcoins sur une clé publique doit trouver un moyen de stocker de manière sécurisée ce qui permet de débloquer ses fonds : la clé privée. Un portefeuille Bitcoin est un dispositif qui va vous permettre de conserver facilement toutes vos clés sans que d’autres personnes n’y aient accès. Cela ressemble donc plus à un porte-clés qu’à un portefeuille.


Le lien mathématique évoqué précédemment entre une clé publique et une clé privée, et la possibilité de réaliser une signature pour prouver la possession d’une clé privée sans la dévoiler, sont rendus possible par un algorithme de signature numérique.


Dans le protocole Bitcoin on utilise deux algorithmes de signature : ECDSA (Elliptic Curve Digital Signature Algorithm. En français : Algorithme de signature digitale sur courbe elliptique) et le Protocole de Schnorr (Le nom du protocole de Schnorr vient de son inventeur Claus-Peter Schnorr).


ECDSA est le protocole de signature numérique utilisé dans Bitcoin depuis ses débuts. Schnorr est tout nouveau dans Bitcoin, puisqu’il a été introduit en Novembre 2021 avec la mise à jour Taproot.


Ces deux algorithmes sont assez similaires dans leurs mécanismes. Ils sont tous deux basés sur la cryptographie sur les courbes elliptiques. La différence majeure entre ces deux protocoles réside dans la structure de la signature.


Étant donné leurs similitudes techniques, nous allons ici étudier simplement l'algorithme de signature ECDSA. La majorité des concepts évoqués pourront également être vérifiés sur le protocole de Schnorr.





La courbe elliptique.


La cryptographie sur les courbes elliptiques est un ensemble d’algorithmes qui utilisent une courbe elliptique pour ses différentes propriétés mathématiques et géométriques dans un objectif cryptographique, et dont la sécurité se base sur la difficulté du calcul du logarithme discret. Les courbes elliptiques sont notamment utilisées pour réaliser des échanges de clés, du chiffrement asymétrique, ou encore pour réaliser des signatures numériques.


Une des propriétés importantes de ces courbes est qu’elles sont toujours symétriques. Ainsi, toute droite non verticale coupant 2 points sur une courbe elliptique coupera toujours la courbe en un troisième point. Aussi, toute ligne non verticale et tangente à la courbe en un point coupera toujours la courbe en un deuxième point unique. Ces propriétés nous seront utiles pour la suite.


Voici une représentation d’une courbe elliptique :



Courbe elliptique sur le corps des réels


Toute courbe elliptique est définie par l’équation : y² = x^3 + ax + b.


Pour utiliser ECDSA, il faudra donc choisir les paramètres de la courbe elliptique, c'est-à-dire les valeurs de a et de b dans l’équation de cette courbe.


Il existe ainsi différents standards de courbes elliptiques réputées cryptographiquement sûres. La plus connue est la courbe secp256r1, définie et conseillée par le NIST.


Malgré cela, Satoshi Nakamoto, l'inventeur de Bitcoin, a choisi de ne pas utiliser cette courbe. La raison de ce choix est inconnue, mais certains pensent qu’il a préféré trouver une alternative car les paramètres de cette courbe contiennent potentiellement une backdoor. À la place, le protocole Bitcoin utilise le standard secp256k1. SEC désigne “Standards for Efficient Cryptography”. P256 désigne le fait que la courbe est définie sur un corps ℤpp est un nombre premier de 256 bits. K désigne le nom de son inventeur Neal Koblitz et 1 désigne la première version.


Secp256k1 est une courbe définie par les paramètres a=0 et b=7. Son équation est donc : y² = x^3 + 7.


Sa représentation graphique sur le corps des réels ressemblera à cela :




Courbe elliptique secp256k1


En réalité, nous ne travaillerons pas sur le corps des réels mais sur le corps ℤp qui est un corps fini d’entiers positifs modulo p, où p est un nombre premier.


Un nombre premier est simplement un entier naturel qui n’admet que deux diviseurs entiers et positifs : 1 et lui-même. Par exemple : le chiffre 7 est un nombre premier puisqu’il ne peut être divisé que par deux entiers naturels : 1 et 7. En revanche, le chiffre 8 n’est pas un nombre premier étant donné qu’il peut être divisé par 1, 2, 4 et 8, il n’admet donc pas que deux diviseurs entiers et positifs mais quatre diviseurs, ce qui l'exclut du groupe des nombres premiers.

La définition de ce corps fini d’ordre premier va nous permettre de travailler exclusivement à partir d’entiers compris dans un rang fini. Dans Bitcoin, ce rang est de 256 bits soit 2^256.


2^256 n’est pas un nombre premier, ECDSA utilise donc un nombre premier inférieur et relativement proche de ce nombre. La représentation hexadécimale de ce nombre premier est :

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

En format décimal (base 10), nous aurons :

p = 2^256 - 2^32 - 977

Notons que ce n’est pas le nombre premier le plus proche existant. Il a été choisi pour différents facteurs.


L’équation de notre courbe elliptique sera donc en réalité :

= (x^3 + 7) mod (2^256 - 2^32 - 977)


Étant donné que cette courbe est définie sur le corps ℤp, elle ne ressemblera plus vraiment à une courbe mais plutôt à un nuage de points.


Par exemple, voici à quoi ressemble la courbe utilisée dans Bitcoin pour p = 17 :


Courbe elliptique modulo 17
Crédit : https://www.graui.de/ Dr. Sascha Grau.


Ici, j’ai intentionnellement limité le corps à modulo 17, mais il faut imaginer que celui utilisé dans Bitcoin est infiniment plus grand.


On utilise un corps fini d’entiers positifs afin d’assurer la précision de la courbe. En effet, les courbes elliptiques sur le corps des réels sont imprécises. Si l’on effectue de nombreux ajouts de points, les erreurs d’arrondis vont s’accumuler à chaque étape et le résultat final n’aura aucun sens et sera difficilement reproductible. L’utilisation exclusive d’entiers positifs permet d’assurer une précision parfaite des ajouts de points et donc une reproductibilité du calcul.


L’utilisation de ce corps fini d’ordre premier est régie par les mêmes mathématiques que l’utilisation d’une courbe sur le corps des réels. Dans un souci de simplification, je vais donc continuer la vulgarisation sur une courbe définie sur des nombres réels.


Néanmoins, vous pouvez garder à l’esprit que cette courbe est en réalité un nuage de points comme sur le schéma ci-dessus, mais infiniment plus grand.





La clé privée.


Comme vu précédemment, l'algorithme ECDSA est basé sur un couple clé privée / clé publique qui sont liées mathématiquement. La clé privée est simplement un nombre pseudo-aléatoire. Dans le cas de Bitcoin, ce nombre est d’un taille de 256 bits.


Un nombre pseudo-aléatoire est un nombre qui dispose de propriétés s’approchant des propriétés idéales d’un nombre aléatoire.

Le nombre de possibilités pour une clé privée Bitcoin est donc théoriquement de 2^256 possibilités.


En réalité, il existe seulement n points sur notre courbe elliptique. Nous verrons plus tard à quoi correspond ce nombre, mais retenez simplement qu’une clé privée valide est un nombre de 256 bits compris entre 1 et n-1, en sachant que n est un nombre relativement plus petit que 2^256. Il existe donc certains nombres de 256 bits qui ne sont pas valides pour devenir clé privée dans Bitcoin.


Si la génération du nombre pseudo-aléatoire mène à une clé privée entre n et 2^256, celle-ci est considérée comme invalide et il faudra de nouveau réaliser la génération aléatoire.


Le nombre de possibilités pour une clé privée Bitcoin est donc presque de 1,158 * 10^77. C’est un nombre tellement grand que si vous choisissez une clé privée aléatoirement, il est statistiquement presque impossible de tomber sur la clé privée d’un autre utilisateur. Pour vous donner un ordre de grandeur, il y a presque autant de clés privées possibles dans Bitcoin que d’atomes dans l’univers observable.


Comme nous le verrons dans le tome 2 de la série Bitcoin Démocratisé, aujourd’hui, la majorité des clés privées dans Bitcoin ne sont pas générées aléatoirement mais sont le résultat d’une dérivation déterministe depuis une phrase mnémonique, elle-même pseudo-aléatoire. Cette information ne change rien pour ECDSA, mais elle permet de recentrer ma vulgarisation sur Bitcoin.


Pour la suite de la vulgarisation, la clé privée est appelée “k” minuscule.





La clé publique.


La clé publique est un nombre de 512 bits qui est généré à partir de la clé privée. Ce nombre est un point sur la courbe elliptique que nous nommons “K” majuscule.


⇨ 512 bits est la taille de la charge utile de la clé publique, c’est-à-dire les valeurs concaténées du x et du y indiquant le point sur la courbe elliptique. Si l’on ajoute le préfixe, une clé publique dispose alors d’une taille de 520 bits.
Comme nous le verrons dans le tome 2, une clé publique de 512 bits peut être compressée en un nombre de 264 bits conservant pourtant les mêmes informations. C’est ce que l’on appelle une clé publique compressée.

Pour calculer K nous allons utiliser l’addition et le doublement de points sur les courbes elliptiques (je vous explique ce concept dans la partie suivante) tel que : K = k G, où k est la clé privée et G est le point générateur également parfois appelé point d’origine. C’est un point sur la courbe elliptique, connu par toutes les parties prenantes, utilisé pour calculer l’intégralité des clés publiques de l'algorithme.


Le fait que ce point G soit commun à toutes les clés publiques Bitcoin nous permet d’être sûr qu’une même clé privée nous donnera toujours la même clé publique.


Point générateur de la courbe


La principale caractéristique de l'addition et du doublement de points sur les courbes elliptiques est qu’ils ne sont pas réversibles. Ce sont des “trapdoor functions”.


En conséquence, il est très facile de calculer une clé publique en sachant sa clé privée et le point générateur, mais il est impossible de calculer une clé privée et sachant sa clé publique et le point générateur.


Faire ce calcul inverse reviendrait à devoir déterminer le logarithme discret, un calcul aussi difficile que de tenter une attaque par brute force (en essayant une à une toutes les combinaisons possibles).


Même les calculateurs les plus puissants actuels sont pour le moment très loin d’être en capacité de réaliser un tel calcul.

Fonction à sens unique




Addition et doublement de points.


La notion d’addition sur les courbes elliptiques est définie tel que l’addition d’un point M sur une courbe elliptique à un autre point L sur la même courbe donnera un point U, de telle sorte que si l’on trace une droite entre M et L, elle viendra couper la courbe elliptique en un troisième point O qui est l’opposé de U.


Nous aurons donc :

  • M + L = U


On peut le représenter graphiquement avec la courbe ci-dessous :

Addition sur les courbes elliptiques


Maintenant si nous voulons ajouter un même point à lui même, c'est-à-dire réaliser un doublement de point, cela reviendrait à tracer la tangente à la courbe en ce point, et à récupérer l’opposé du point d’intersection entre la tangente et la courbe elliptique.


Graphiquement, cela donnerait cela :

Doublement de point sur les courbes elliptiques



Dans cet exemple pour calculer le point J tel que J = G + G, nous avons simplement tracé la tangente à la courbe elliptique en le point G (droite orange). Cette tangente coupe une nouvelle fois la courbe elliptique en un point appelé ici -J. L’opposé de ce point nous donne notre résultat J.


Maintenant que nous savons faire l’addition sur les courbes elliptiques et le doublement à partir d’un point générateur (G), nous pouvons également réaliser le produit scalaire sur les courbes elliptiques. La produit scalaire d’un point par n revient à ajouter ce point à lui-même n fois.


Si nous reprenons notre exemple, calculer G + G revient à calculer 2G. Nous pouvons renommer nos points en conséquence :

Doublement de point sur les courbes elliptiques


Nous pouvons ainsi continuer et calculer 4G en traçant la tangente de la courbe elliptique en 2G et en prenant le point opposé par rapport à l’axe des abscisses. On a alors effectué un doublement du point 2G :

2 doublements sur la courbe elliptique


Si l’on souhaite par exemple calculer le point 3G, nous devons d’abord calculer le point 2G en doublant le point G, puis nous additionnons G et 2G.


Graphiquement cela représenterait cela :

Doublement et addition de points sur la courbe elliptique


Pour additionner G et 2G il suffit de tracer la droite reliant ces deux points (droite orange), de récupérer le point unique -3G à l’intersection entre cette droite et la courbe elliptique, et de déterminer 3G tel que l’opposé à -3G.


Nous aurons donc :

  • G + G = 2G

  • 2G + G = 3G





Fonction à sens unique.


Grâce à ces schémas nous pouvons comprendre facilement pourquoi la dérivation d’une clé publique en sachant la clé privée est très facile, mais l’inverse est impossible.


Reprenons notre exemple. Imaginons que nous ayons tiré un nombre aléatoire pour déterminer notre nouvelle clé privée et que ce nombre soit 4. Nous avons donc k = 4.


Pour calculer la clé publique associée à notre clé privée, nous réalisons l’opération K = k G. Dans notre exemple, cela donne K = 4 G = 4G.


Graphiquement, cela ressemble à cela :

Dérivation clé publique sur la courbe elliptique


Nous avons donc pu facilement calculer la clé publique K en sachant k et G.


Maintenant, si je vous donne uniquement la clé publique K, vous serez incapable de déterminer la valeur de la clé privée k.


Graphiquement, cela donnerait cela :

Fonction a sens unique


En étudiant uniquement cette courbe, vous serez dans l’incapacité de calculer k, c'est-à-dire le nombre de fois que l’on a doublé G pour trouver K. Vous pourrez trouver -K, le premier opposé du point K, mais vous serez ensuite dans l’incapacité de déterminer d’où vient la tangente qui coupe la courbe elliptique en ce point -K.


C’est en partie grâce à ce principe qu’il est impossible de déterminer une clé privée Bitcoin en connaissant uniquement sa clé publique.


Évidemment, dans cet exemple, vous pourriez calculer K par tâtonnement en partant de G étant donné que j’ai intentionnellement choisi une clé privée k très petite égale à 4. Il faut imaginer qu’en réalité ce calcul est infaisable car la clé privée est un nombre avec infiniment plus de possibilités (presque 2^256).


C’est sur ce principe qu’est basé la sécurité de l’algorithme ECDSA.





Signature numérique.


Maintenant que nous savons dériver une clé publique à partir d’une clé privée, nous pouvons déjà recevoir des bitcoins en utilisant cette paire de clé comme condition de dépense. Mais comment les dépenser ?


Pour dépenser des bitcoins il va falloir prouver au réseau que vous en êtes bien le propriétaire légitime. Il va donc falloir prouver mathématiquement au réseau que vous êtes en possession de la clé privée associée, sans pour autant la dévoiler.


C’est à ce moment-là qu'intervient la signature numérique, une preuve irréfutable que vous êtes bien en possession de la clé privée associée à la clé publique que vous revendiquez.


Pour réaliser une signature numérique il faut premièrement que tous les participants au réseau connaissent les paramètres de la courbe elliptique utilisée. Dans le cas de Bitcoin, les paramètres de secp256k1 sont :


  • Le champ fini p défini par

p = 2^256 - 2^32 - 977 
= 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

p est un nombre premier très grand légèrement inférieur à 2^256.


  • La courbe y² = x^3 + ax + b sur p définie par :

a = 0
b = 7

  • Le point générateur ou point à l’origine G :

G = 0x02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

Ce nombre est la forme compressée qui donne uniquement l’abscisse du point G. Le préfixe 02 au départ permet de déterminer laquelle des 2 valeurs ayant cette abscisse x est à utiliser comme point générateur.


  • L’ordre n de G (le nombre de points existants) et le cofacteur h :

n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

n est un nombre très grand légèrement inférieur à p.

h = 1

h est le cofacteur ou le nombre de sous-groupes. Je ne vais pas développer ce que cela représente car c’est assez complexe, et car dans le cas de Bitcoin nous n’avons pas besoin de le prendre en compte étant donné qu’il est égal à 1.



Toutes ces informations sont publiques et connues de tous les participants. Grâce à elles, les utilisateurs sont en capacité de réaliser une signature comme cela :


Imaginons qu’Alice souhaite envoyer des bitcoins à Bob. Imaginons également que Eve est un acteur malveillant qui souhaite voler ces bitcoins.


Comme vu précédemment, Alice a déterminé une paire de clés. La clé privée (k minuscule) est un nombre aléatoire de 256 bits compris entre 1 et n - 1 et la clé publique (K majuscule) est un point sur la courbe calculé à partir de k et de G tel que : K = k G.


Alice a déjà reçu des bitcoins. Ils sont bloqués sur sa paire de clés et demandent de produire une signature numérique à l’aide de la clé privée pour remplir leurs conditions de dépense. Alice souhaite désormais les envoyer à Bob.


L’information K est donc désormais connue par tous les utilisateurs, mais l’information k ne l’est pas. Seule Alice dispose de l'information k.


Pour pouvoir débloquer les bitcoins associés à sa clé publique K, et donc envoyer les bitcoins à Bob, Alice va devoir fournir une signature à l’aide de sa clé privée k. L’objectif est que ni Bob, ni Eve, ni tout autre participant au réseau ne puissent calculer la valeur de k.



Pour vous expliquer la construction et la vérification d’une signature ECDSA, je vais d’abord vous donner les formules exactes, puis je vais vulgariser ce que ces formules complexes veulent dire. L’important n’est pas tant de comprendre les mathématiques qui régissent cela, mais plutôt de comprendre pourquoi ce mécanisme fonctionne.


La signature S d’Alice est partagée en deux parties que nous nommons S1 et S2 tels que S1 et S2 concaténés donnent S, la signature numérique.



- S1 :


Pour trouver S1 il va falloir générer un nombre pseudo-aléatoire que nous nommerons v. Ce nombre doit être un nonce strictement inférieur à n. C’est-à-dire que ce nombre doit être différent pour chaque nouvelle signature, sans quoi il sera possible pour Eve de calculer la clé privée et de voler les bitcoins associés.


Nonce (Number only used once) : Nombre déterminé de façon arbitraire, généralement pseudo-aléatoire, destiné à être utilisé une seule fois puis changé.

Alice utilise ensuite le produit scalaire sur les courbes elliptiques pour déterminer V, un point sur la courbe tel que V = v G.


L'abscisse x de ce point V modulo n est la valeur de S1 recherchée :

V = v G = (x,y)
S1 = x mod n


- S2 :


Pour trouver S2 Alice commence par réaliser un hash de sa transaction Bitcoin non signée. Ce hash est nommé H(Tx), la transaction en elle-même étant nommée Tx.


Maintenant, Alice peut calculer S2 en utilisant l’équation suivante :

S2 = v^-1 ( H(Tx) + k * S1 ) mod n




Vérification de la signature.


Alice envoie donc sa transaction Bitcoin avec sa signature S (S1 || S2) au réseau. Matérialisés par les nœuds, les autres utilisateurs du réseau vont la vérifier.


Si la signature est valide, alors la transaction d’Alice pourra être incluse dans un bloc afin d’être confirmée, et les bitcoins changeront de conditions de dépenses en dépendant dorénavant de la paire de clés de Bob.


Imaginons que Bob vérifie la transaction d’Alice, de la même manière que tous les autres utilisateurs la vérifieront.


Bob dispose des paramètres de la courbe secp256k1 : p, a, b, G et n. Il dispose également des informations fournies par Alice, à savoir : Tx, S1, S2 et K.


Il va commencer par calculer le hash de la transaction Tx. Il disposera alors de H(Tx).


Pour vérifier la signature il va calculer un point P( i , j ) tel que :


P = (S2^-1 * H(Tx) mod n) * G + (S2^-1 * S1 mod n) * K

Bob détermine ensuite l’abscisse de ce point P que l’on nommera i.


Si i mod n = S1, alors la signature est valide.


Ces calculs sont sympathiques, mais on a du mal à comprendre comment la vérification est possible. Je vous propose donc une vulgarisation de ce mécanisme afin de rendre sa compréhension moins complexe.





Vulgarisation.


Imaginons qu’Alice souhaite prouver à Bob qu’elle connaît un nombre secret k (la clé privée) sans pour autant lui révéler ce nombre. De plus, Alice et Bob communiquent via un réseau public surveillé par Eve, une attaquante qui souhaite subtiliser le secret k.


Rappelons que :

  • La clé privée k n’est connue que par Alice. C’est un nombre pseudo-aléatoire.

  • La clé publique K est connue par Alice, par Bob et par Eve.

  • K est déterminé par k et G (le point générateur) tel que : K = k G.


En raison de l’utilisation du produit scalaire sur les courbes elliptiques expliqué précédemment, et de sa caractéristique d’irréversibilité, Bob et Eve ne peuvent pas déterminer k en ayant uniquement connaissance de K et de G.



Voici alors comment fonctionne le mécanisme :

  • Alice va déterminer un nouveau nombre secret aléatoire v. Elle va ensuite additionner v et k. La somme de ces deux nombres secrets est t tel que : t = v + k.

Il est important que v reste secret, sinon k pourra être calculé par soustraction.

  • Alice calcule ensuite un point sur la courbe elliptique nommé V tel que : V = v G. Elle va donc ajouter G à lui-même v fois pour avoir le point V.

Ce point V va permettre de révéler juste assez d’informations sur v sans pour autant le dévoiler.

  • Alice envoie à Bob t et V.

On passe ensuite à la vérification de Bob.

  • Bob additionne la clé publique K avec V, tel que T = K + V.

  • Bob calcule ensuite un point T’ tel que T’ = t G en utilisant le produit scalaire sur les courbes elliptiques.

Si T = T’ alors Bob a la preuve qu’Alice connaît bien la valeur de k, et donc qu’Alice est bien en possession de la clé privée donnant accès aux bitcoins revendiqués.



En réalité, il existe une faille dans cet exemple de construction d’une signature que je viens de vous décrire. Cette faille pourrait être exploitée par Eve, l’actrice malveillante du réseau, pour essayer de subtiliser les bitcoins d’Alice. Puisque Eve sait que Bob additionnera K avec V pour trouver le point T, elle peut créer une fausse valeur de k et calculer un faux K. Eve va ensuite soustraire K du vrai point V qu’elle aura elle-même déterminé. Elle aura alors un nouveau point V malicieux. La nouvelle valeur du V malicieux sera alors Vm = V - K. Le pauvre Bob qui va se faire berner ne pourra pas différencier le Vm malicieux du V légitime. Il interprètera donc Vm comme étant V.


Lors de la vérification il procédera donc comme précédemment :

  • T = K + Vm. En sachant que Vm = V - K alors T = K + V - K.

  • Les K s’annulent.

  • T = V

Eve pourrait alors déterminer t = v. Lors de la vérification de la deuxième partie, Bob aura donc :

t = v T = v G 
T = t  G = v  G 
T = T

La signature serait donc considérée comme valide par Bob et les autres vérificateurs qui débloqueraient alors les bitcoins d’Alice en la faveur d’Eve, alors même que cette dernière n’a pas eu accès à la clé privée légitime.


Pour résoudre cette faille, l'algorithme ECDSA inclut un hash de la transaction dans le calcul de la signature. La fonction de hachage permet ici de s’assurer que le multiplicateur utilisé dispose des mêmes propriétés qu’un nombre pseudo-aléatoire, sans devoir faire confiance à l'émetteur pour le caractère aléatoire de ce dernier.



Voici donc comment il est possible de prouver au réseau Bitcoin que vous êtes bien le propriétaire d’un UTXO, sans pour autant rendre publique l’information qui permet de le débloquer.



Conclusion Bitcoin Démocratisé 1.


Nous avons pu découvrir en détail le fonctionnement, les caractéristiques et l’utilisation des fonctions de hachage et des signatures numériques.


Certains concepts sont assez complexes à comprendre et ne sont pas forcément tous nécessaires pour appréhender le fonctionnement technique de Bitcoin. J’ai souhaité tout de même mettre ce tome au début de ma série d’ebooks car ces algorithmes cryptographiques constituent la base technique de Bitcoin. On les retrouve ainsi à tous les niveaux du protocole : minage, portefeuille, transaction…


Selon moi, les informations les plus importantes à retenir sont les caractéristiques de ces algorithmes, au-delà de leur fonctionnement technique. C’est cela qui vous permettra de comprendre pourquoi ils sont utilisés dans le protocole.


Nous avons donc pu voir que les fonctions de hachage produisent une empreinte de taille fixe et disposent de trois caractéristiques principales : l’irréversibilité, la résistance à la falsification et la résistance aux collisions.


Les algorithmes de signatures numériques permettent deux usages principaux : la génération d’une clé publique à partir d’une clé privée, et la signature d’une transaction. La dérivation de la clé publique à partir de la clé privée est également une fonction irréversible.


La signature numérique permet de prouver au réseau que vous êtes bien le propriétaire d’une certaine clé publique en fournissant une preuve mathématique irréfutable que vous êtes en connaissance de la clé privée associée, tout en gardant secrète ladite clé privée.


Dans le prochain tome, nous allons mettre en application tous ces algorithmes car nous allons étudier la construction d’un portefeuille Bitcoin. Nous verrons ce que sont la phrase mnémonique, la graine, les clés étendues, les adresses ou encore les chemins de dérivation. Nous étudierons comment tous ces éléments sont calculés et utilisés au sein du protocole.


Si ce concept de petits ebooks techniques sur Bitcoin en français vous plaît, n’hésitez pas à partager ce contenu auprès de votre entourage et à me suivre sur Twitter où je vous communiquerai les sorties des prochains tomes de la série.


Je publie également du contenu de vulgarisation technique sur mon blog que vous pouvez retrouver en cliquant ici : https://www.pandul.fr/blog




Pour aller plus loin :



Ressources externes :


Rapport SEC 2: Recommended Elliptic Curve Domain Parameters :

https://www.secg.org/SEC2-Ver-1.0.pdf


Rapport FIPS PUB 186-4 : Digital Signature Standard (DSS) :

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf


Articles et ressources sur le fonctionnement technique d’ECDSA :

https://cryptobook.nakov.com/digital-signatures/ecdsa-sign-verify-messages

https://suhailsaqan.medium.com/explanation-of-bitcoins-elliptic-curve-digital-signature-algorithm-6603f951863a

https://www.maximintegrated.com/en/design/technical-documents/tutorials/5/5767.html

https://jeremykun.com/2014/02/08/introducing-elliptic-curves/

https://www.johndcook.com/blog/2018/08/14/bitcoin-elliptic-curves/


Outils de visualisation de courbes elliptiques :

https://www.graui.de/