Les mathématiques derrière le protocole Bitcoin

ONEune des raisons pour lesquelles le Bitcoin peut être déroutant pour les débutants est que la Technologies qui le sous-tend redéfinit le concept de propriété.

Posséder quelque chose au sens traditionnel du terme, qu’il s’agisse d’une maison ou d’une somme d’argent, signifie soit avoir la garde personnelle de la chose, soit en confier la garde à une entité de confiance comme une banque.

Protocole Bitcoin

Avec le Bitcoin , la situation est différente. Les bitcoins eux-mêmes ne sont stockés ni de manière centralisée ni localement ; ONE entité n'en est donc le dépositaire. Ils existent sous forme d'enregistrements sur un registre distribué appelé blockchain, dont les copies sont partagées par un réseau bénévole d'ordinateurs connectés. « Posséder » un Bitcoin signifie simplement avoir la possibilité d'en transférer le contrôle à quelqu'un d'autre en créant un enregistrement du transfert dans la blockchain. Qu'est-ce qui confère cette possibilité ? L'accès à un ECDSA Paire de clés privée et publique. Qu'est-ce que cela signifie et comment cela sécurise-t-il Bitcoin?

Jetons un œil sous le capot.

ECDSAest l'abréviation de Elliptic Curve Digital Signature Algorithm (algorithme de signature numérique à courbe elliptique). Il s'agit d'un processus qui utilise uncourbe elliptiqueet uncorps fini « Signer » des données de manière à ce que des tiers puissent vérifier l'authenticité de la signature, tandis que le signataire conserve l'exclusivité de la création de la signature. Avec Bitcoin, les données signées constituent la transaction qui transfère la propriété.

L'ECDSA dispose de procédures distinctes pour la signature et la vérification. Chaque procédure est un algorithme composé de quelques opérations arithmétiques. L'algorithme de signature utilise la clé privée, tandis que le processus de vérification utilise la clé publique. Nous en montrerons un exemple ultérieurement.

Mais d’abord, un cours accéléré sur les courbes elliptiques et les corps finis.

Courbes elliptiques

Une courbe elliptique est représentée algébriquement par une équation de la forme :

y2 = x3 + ax + b

Pour a = 0 et b = 7 (la version utilisée par Bitcoin), cela LOOKS à ceci :

Les courbes elliptiques possèdent des propriétés utiles. Par exemple, une droite non verticale coupant deux points non tangents de la courbe coupera toujours un troisième point de la courbe. Une autre propriété est qu'une droite non verticale tangente à la courbe en un point coupera précisément un autre point de la courbe.

Nous pouvons utiliser ces propriétés pour définir deux opérations : l’addition de points et le doublement de points.

Ajout de points,P + Q = R,est défini comme la réflexion par l'axe des x du troisième point d'intersectionR’sur une ligne qui comprendP et QIl est plus facile de comprendre cela à l’aide d’un diagramme :

De la même manière,doublement de points,P + P = Rest défini en trouvant la ligne tangente au point à doubler,P, et en prenant la réflexion par l'axe des x du point d'intersectionR’sur la courbe pour obtenirRVoici un exemple de ce à quoi cela ressemblerait :

Ensemble, ces deux opérations sont utilisées pourmultiplication scalaire,R = a P,défini en ajoutant le pointPà lui-mêmeunfois. Par exemple :

R = 7P

R = P + (P + (P + (P + (P + (P + P)))))

Le processus de multiplication scalaire est généralement simplifié par une combinaison d'opérations d'addition et de doublement de points. Par exemple :

R = 7P

R = P + 6P

R = P + 2 (3P)

R = P + 2 (P + 2P)

Ici, 7Pa été décomposé en deux étapes de doublement de points et deux étapes d'ajout de points.

Corps finis

Dans le contexte de l'ECDSA, un corps fini peut être considéré comme un intervalle prédéfini de nombres positifs dans lequel chaque calcul doit se situer. Tout nombre hors de cet intervalle « s'enroule » pour y être inclus.

La façon la plus simple d'envisager ce problème est de calculer les restes, représentés par l'opérateur modulo (mod). Par exemple, 9/7 donne 1 avec un reste de 2 :

9 mod 7 = 2

Ici, notre corps fini est modulo 7, et toutes les opérations de modulation sur ce corps donnent un résultat compris entre 0 et 6.

Mettre tout cela ensemble

L'ECDSA utilise des courbes elliptiques dans le contexte d'un corps fini, ce qui modifie considérablement leur apparence, mais pas leurs équations sous-jacentes ni leurs propriétés particulières. La même équation, représentée ci-dessus, dans un corps fini de modulo 67, LOOKS ainsi :

C'est désormais un ensemble de points, dans lequel tous lesx et etles valeurs sont des entiers compris entre 0 et 66. Notez que la « courbe » conserve toujours sa symétrie horizontale.

L'addition et le doublement de points sont désormais légèrement différents visuellement. Les lignes tracées sur ce graphique s'enroulent autour des directions horizontale et verticale, comme dans un jeu d'Astéroïdes, en conservant la même pente. Ainsi, l'addition des points (2, 22) et (6, 25) LOOKS comme suit :

Le troisième point d'intersection est (47, 39) et son point de réflexion est (47, 28).

Retour à l'ECDSA et au Bitcoin

Un protocole tel que Bitcoin sélectionne un ensemble de paramètres pour la courbe elliptique et sa représentation en corps fini, qui est fixe pour tous les utilisateurs du protocole. Ces paramètres incluent : équationutilisé, lePRIME modulodu terrain, et unpoint de basequi tombe sur la courbe. Lecommande Le point de base, qui n'est pas choisi indépendamment mais est fonction des autres paramètres, peut être représenté graphiquement comme le nombre de fois que le point peut être additionné à lui-même jusqu'à ce que sa pente soit infinie, ou une droite verticale. Le point de base est choisi de telle sorte que l'ordre soit un grand nombre PRIME .

Bitcoin utilise des nombres très grands pour son point de base, son modulo PRIME et son ordre. En fait, toutes les applications pratiques de l'ECDSA utilisent des valeurs énormes. La sécurité de l'algorithme repose sur la grandeur de ces valeurs, et donc sur leur impraticabilité par force brute ou rétro-ingénierie.

Dans le cas du Bitcoin:

Équation de la courbe elliptique : y2 = x3 + 7

PRIME modulo = 2256 – 232 – 29 – 28 – 27 – 26 – 24 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Point de base = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Commande = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Qui a choisi ces chiffres et pourquoi ? Beaucouprecherche, et une bonne quantité deintrigue, entoure la sélection des paramètres appropriés. Après tout, un grand nombre apparemment aléatoire pourrait cacher une méthode détournée de reconstruction de la clé privée. En bref, cette réalisation particulière est appelée secp256k1 et fait partie d'une famille de solutions de courbes elliptiques sur corps finis proposées pour une utilisation en cryptographie.

Clés privées et clés publiques

Ces formalités étant réglées, nous sommes désormais en mesure de comprendre les clés privées et publiques et leurs relations. En résumé : dans ECDSA, la clé privée est un nombre aléatoire compris entre 1 et l'ordre. La clé publique est dérivée de la clé privée par multiplication scalaire du point de base par un nombre égal à la valeur de la clé privée. Exprimée sous forme d'équation :

clé publique = clé privée * point de base

Cela montre que le nombre maximal possible de clés privées (et donc d'adresses Bitcoin ) est égal à la commande.

Dans un champ continu, nous pourrions tracer la ligne tangente et localiser la clé publique sur The Graph, mais il existe quelques équationsqui accomplissent la même chose dans le contexte des corps finis. Addition de points dep + qtrouverrest défini composant par composant comme suit :

c = (qy - py) / (qx - px)

rx = c2 - px - qx

ry = c (px - rx) - py

Et le point de doublement pour trouverrest comme suit :

c = (3px2 + a) / 2py

rx = c2 - 2px

ry = c (px - rx) - py

En pratique, le calcul de la clé publique est décomposé en un certain nombre d'opérations de doublement et d'ajout de points à partir du point de base.

Prenons un exemple simple avec de petits nombres pour comprendre comment les clés sont construites et utilisées pour la signature et la vérification. Les paramètres que nous utiliserons sont :

Équation : y2 = x3 + 7 (c'est-à-dire a = 0 et b = 7)

PRIME modulo : 67

Point de base : (2, 22)

Commande : 79

Clé privée : 2

Commençons par trouver la clé publique. Puisque nous avons sélectionné la clé privée la plus simple possible, avec une valeur égale à 2, il suffit d'un seul point de doublement à partir du point de base. Le calcul LOOKS comme suit :

c = (3 * 22 + 0) / (2 * 22) mod 67

c = (3 * 4) / (44) mod 67

c = 12 / 44 mod 67

Il faut ici s'arrêter un instant pour un tour de passe-passe : comment effectuer une division dans le contexte d'un corps fini, où le résultat doit toujours être un entier ? Il faut multiplier par l'inverse, ce que l'espace ne nous permet pas de définir ici (nous vous renvoyons à ici et iciSi vous êtes intéressé(e). Dans le cas présent, vous devrez nous faire confiance pour le moment :

44-1 = 32

Continuons sur notre lancée :

c = 12 * 32 mod 67

c = 384 mod 67

c = 49

rx = (492 - 2 * 2) mod 67

rx = (2401 - 4) mod 67

rx = 2397 mod 67

rx = 52

ry = (49 * (2 - 52) - 22) mod 67

ry = (49 * (-50) - 22) mod 67

ry = (-2450 - 22) mod 67

ry = -2472 mod 67

ry = 7

Notre clé publique correspond donc au point (52, 7). Tout ce travail pour une clé privée de 2 !

Cette opération - passer de la clé privée à la clé publique - est simple à calculer, comparée à la tentative de travailler à rebours pour déduire la clé privée de la clé publique, ce qui, bien que théoriquement possible, est irréalisable en raison des paramètres importants utilisés dans la cryptographie elliptique réelle.

Par conséquent, passer de la clé privée à la clé publique est, par conception, un voyage à sens unique.

Comme la clé privée, la clé publique est normalement représentée par une chaîne hexadécimale. Mais comment passer d'un point d'un plan, décrit par deux nombres, à un seul nombre ? Dans une clé publique non compressée, les deux nombres de 256 BIT représentent x et etLes coordonnées sont simplement regroupées dans une longue chaîne. On peut également tirer parti de la symétrie de la courbe elliptique pour produire une clé publique compressée, en ne conservant que les xet en notant sur quelle moitié de la courbe se trouve le point. À partir de cette information partielle, nous pouvons récupérer les deux coordonnées.

Signature des données avec la clé privée

Maintenant que nous avons une paire de clés privée et publique, signons quelques données !

Les données peuvent être de n'importe quelle longueur. La première étape habituelle consiste à hacher les données pour générer un nombre contenant le même nombre de bits (256) que l'ordre de la courbe. Ici, par souci de simplicité, nous omettons l'étape de hachage et signons simplement les données brutes.zNous appelleronsGle point de base, l'ordre etdla clé privée. La recette pour signer est la suivante :

• Choisissez un entier k compris entre 1 et n - 1.
• Calculez le point (x, y) = k * G, en utilisant la multiplication scalaire.
• Trouvez r = x mod n. Si r = 0, revenez à l'étape 1.
• Trouvez s = (z + r * d) / k mod n. Si s = 0, revenez à l'étape 1.
• La signature est la paire (r, s)

Pour rappel, à l'étape 4, si les nombres donnent une fraction (ce qui est presque toujours le cas dans la réalité), le numérateur doit être multiplié par l'inverse du dénominateur. À l'étape 1, il est important quekne doit pas être répété dans différentes signatures et ne doit pas être deviné par un tiers. Autrement dit,k devrait être aléatoire ou générée par des moyens déterministes tenus Secret . Sinon, il serait possible d'extraire la clé privée de l'étape 4, car , z,r,ket sont tous connus. Vous pouvez lire un récit d'un exploit antérieur de ce type.ici.

Prenons comme données le nombre 17 et Réseaux sociaux la recette. Nos variables :

z = 17 (données)

n = 79 (ordre)

G = (2, 22) (point de base)

d = 2 (clé privée)

• Choisissez un nombre au hasard :

k = rand(1, n - 1)

k = rand(1, 79 - 1)

k = 3 (est-ce vraiment aléatoire ? OK, vous nous avez eu, mais cela simplifiera notre exemple !)

1. Calculer le point. Cette opération s'effectue de la même manière que pour la détermination de la clé publique, mais par souci de concision, nous omettons les calculs d'addition et de doublement de points.

(x, y) = 3G

(x, y) = G + 2G

(x, y) = (2, 22) + (52, 7)

(x, y) = (62, 63)

x = 62

y = 63

1. Trouver r:

r = x modulo n

r = 62 mod 79

r = 62

1. Trouver :

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 47 mod 79

s = 47

Notez que ci-dessus, nous avons pu diviser par 3 puisque le résultat était un entier. Dans la réalité, nous utiliserions l'inverse dek(comme avant, nous avons caché quelques détails sanglants en les calculant ailleurs) :

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 141 * 3-1 mod 79

s = 141 * 53 mod 79

s = 7473 mod 79

s = 47

1. Notre signature est la paire (r, ) = (62, 47).

Comme pour les clés privées et publiques, cette signature est normalement représentée par une chaîne hexadécimale.

Vérification de la signature avec la clé publique

Nous disposons désormais de données et d'une signature. Un tiers disposant de notre clé publique peut recevoir nos données et notre signature et vérifier que nous en sommes bien l'expéditeur. Voyons comment cela fonctionne.

Avec Qétant la clé publique et les autres variables définies comme précédemment, les étapes de vérification d'une signature sont les suivantes :

• Vérifiez que r et s sont compris entre 1 et n - 1.
• Calculer w = s-1 mod n
• Calculer u = z * w mod n
• Calculer v = r * w mod n
• Calculer le point (x, y) = uG + vQ
• Vérifiez que r = x mod n. La signature est invalide si ce n'est pas le cas.

Pourquoi ces étapes fonctionnent-elles ? Nous omettons les preuves, mais vous pouvez lire les détails.iciRéseaux sociaux la recette et voyons comment elle fonctionne. Voici nos variables :

z = 17 (données)

(r, s) = (62, 47) (signature)

n = 79 (ordre)

G = (2, 22) (point de base)

Q = (52, 7) (clé publique)

• Vérifiez queret sont compris entre 1 et - 1. Vérifiez et vérifiez.

r: 1 <= 62 < 79

s: 1 <= 47 < 79

1. Calculerw:

w = s-1 modulo n

l = 47-1 mod 79

l = 37

1. Calculertoi:

u = zw modulo n

u = 17 * 37 mod 79

u = 629 mod 79

u = 76

1. Calculerv:

v = rw modulo n

v = 62 * 37 mod 79

v = 2294 mod 79

v = 3

1. Calculer le point (x,et):

(x, y) = uG + vQ

Décomposons le doublement et l’addition de points dansuG et vQséparément.

uG = 76G

uG = 2(38G)

uG = 2( 2(19G) )

uG = 2( 2(G + 18G) )

uG = 2( 2(G + 2(9G) ) )

uG = 2( 2(G + 2(G + 8G) ) )

uG = 2( 2(G + 2(G + 2(4G) ) ) )

uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

Prenez un instant pour comprendre qu'en utilisant l'astuce du regroupement, nous réduisons 75 additions successives à seulement six opérations de doublement de points et deux opérations d'addition de points. Ces astuces seront utiles lorsque les nombres deviendront vraiment importants.

En travaillant de l’intérieur vers l’extérieur :

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )

uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )

uG = 2( 2(G + 2(G + 2(25, 17) ) ) )

uG = 2( 2(G + 2( (2, 22) + (21, 42) ) ) )

uG = 2( 2(G + 2(13, 44) ) )

uG = 2( 2( (2, 22) + (66, 26) ) )

uG = 2( 2(38, 26) )

uG = 2(27, 40)

uG = (62, 4)

Et maintenant pourvQ:

vQ = 3Q

vQ = Q + 2Q

vQ = Q + 2(52, 7)

vQ = (52, 7) + (25, 17)

vQ = (11, 20)

Les mettre ensemble :

(x, y) = uG + vQ

(x, y) = (62, 4) + (11, 20)

(x, y) = (62, 63)

L'étape 5 représente clairement l'essentiel du travail. Pour la dernière étape,

1. Vérifiez que r = x mod n

r = x modulo n

62 = 62 mod 79

62 = 62

Notre signature est valable !

Conclusion

Pour ceux d’entre vous qui ont vu toutes les équations et sont allés jusqu’en bas, que venons-nous d’apprendre ?

Nous avons développé une certaine intuition quant à la relation mathématique profonde qui existe entre les clés publiques et privées. Nous avons constaté que, même dans les exemples les plus simples, les mathématiques derrière les signatures et la vérification se complexifient rapidement, et nous pouvons apprécier l'énorme complexité inhérente à des paramètres de 256 BIT . Nous avons vu comment l'application astucieuse des procédures mathématiques les plus simples peut créer les fonctions de « trappe » à sens unique nécessaires à la préservation de l'asymétrie d'information qui définit la propriété d'un Bitcoin. Et nous avons acquis une confiance nouvelle dans la robustesse du système, à condition de protéger soigneusement la connaissance de nos clés privées.

En d’autres termes, c’est pourquoi on dit souvent que le Bitcoin est « soutenu par les mathématiques ».

Si vous avez persévéré pendant les parties compliquées, nous espérons que cela vous a donné la confiance nécessaire pour passer à l'étape suivante et essayer les mathématiques par vous-même (unCalculateur arithmétique modulaire(ce qui simplifie grandement les mathématiques des corps finis). Nous avons constaté que la signature et la vérification manuelles des données permettent de mieux comprendre la cryptographie qui permet la forme unique de propriété du bitcoin.

Cet article a été republié ici avec l'autorisation de l'auteur. Initialement publié leChain.comL'auteur remercie tout particulièrement Steven Phelps pour son aide à la rédaction de cet article.

Eric Rykwalder est un ingénieur logiciel et ONEun des Chain.comLes fondateurs de.