Vitalik Buterin via le Blog de Vitalik Buterin
Ceci est un miroir du message de https://medium.com/@VitalikButerin/exploration-elliptique-courbe-pairings-c73c1864e627
Avertissement déclencheur : mathématiques.
L'une des primitives cryptographiques clés derrière diverses constructions, notamment les signatures de seuil déterministes, les zk-SNARK et d'autres formes plus simples de preuves de connaissance nulle, est l'appariement de courbes elliptiques. Les paires de courbes elliptiques (ou « cartes bilinéaires ») sont un ajout récent à une histoire de 30 ans d'utilisation de courbes elliptiques pour des applications cryptographiques, notamment le cryptage et les signatures numériques ; les appariements introduisent une forme de « multiplication cryptée », élargissant considérablement ce que les protocoles basés sur des courbes elliptiques peuvent faire. Le but de cet article sera d’entrer en détail dans les appariements de courbes elliptiques et d’expliquer un aperçu général de leur fonctionnement.
On ne s'attend pas à ce que vous compreniez tout ici la première fois que vous le lisez, ni même la dixième fois ; ce truc est vraiment difficile. Mais j’espère que cet article vous donnera au moins une petite idée de ce qui se passe sous le capot.
Les courbes elliptiques elles-mêmes sont un sujet non trivial à comprendre, et cet article supposera généralement que vous savez comment elles fonctionnent ; si ce n’est pas le cas, je recommande cet article ici comme introduction : https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. En résumé, la cryptographie à courbe elliptique implique des objets mathématiques appelés « points » (ce sont des points bidimensionnels littéraux avec des coordonnées (�,�)), avec des formules spéciales pour les ajouter et les soustraire (c'est-à-dire pour calculer les coordonnées de �= �+�), et vous pouvez également multiplier un point par un nombre entier (c'est-à-dire �⋅�=�+�+…+�, bien qu'il existe un moyen beaucoup plus rapide de le calculer si � est grand).
Voici à quoi ressemble graphiquement l’ajout de points.
Il existe un point spécial appelé « point à l'infini » (�), l'équivalent du zéro en arithmétique des points ; c'est toujours le cas que �+�=�. De plus, une courbe a un «de commander« ; il existe un nombre � tel que �⋅�=� pour tout � (et bien sûr, �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5, et ainsi de suite). Il existe également un « point générateur » communément admis �, qui est censé représenter dans un certain sens le nombre 1. Théoriquement, tout point sur une courbe (sauf �) peut être � ; tout ce qui compte c’est que… soit standardisé.
Les appariements vont encore plus loin dans la mesure où ils vous permettent de vérifier certains types d'équations plus compliquées sur des points de courbe elliptique — par exemple, si �=�⋅�,�=�⋅� et �=�⋅�, vous pouvez vérifier si ou pas �⋅�=�, ayant juste �,� et � comme entrées. Cela peut donner l'impression que les garanties de sécurité fondamentales des courbes elliptiques sont brisées, car des informations sur � fuient simplement en connaissant P, mais il s'avère que la fuite est hautement contenue - en particulier, le problème décisionnel de Diffie Hellman est facile, mais le problème informatique de Diffie Hellman (connaissant � et � dans l'exemple ci-dessus, informatique �=�⋅�⋅�) et le problème de logarithme discret (récupérer � à partir de �) restent irréalisables sur le plan informatique (du moins, s'ils l'étaient avant).
Une troisième façon d'examiner ce que font les appariements, et celle qui est peut-être la plus éclairante pour la plupart des cas d'utilisation qui nous intéressent, est de considérer les points de la courbe elliptique comme des nombres cryptés unidirectionnels (c'est-à-dire ���� ���(�)=�⋅�=�), alors que les mathématiques traditionnelles de courbe elliptique vous permettent de vérifier linéaire contraintes sur les nombres (par exemple si �=�⋅�,�=�⋅� et �=�⋅�, vérifier 5⋅�+7⋅�=11⋅� est vraiment vérifiant que 5⋅�+7⋅�=11⋅�), les appariements vous permettent de vérifier quadratique contraintes (par exemple, vérifier �(�,�)⋅�(�,�⋅5)=1 est vraiment en vérifiant que �⋅�+5=0). Et passer au quadratique est suffisant pour nous permettre de travailler avec des signatures de seuil déterministes, des programmes d'arithmétique quadratique et toutes ces autres bonnes choses.
Maintenant, quel est ce drôle d’opérateur �(�,�) que nous avons présenté ci-dessus ? C'est le jumelage. Les mathématiciens l'appellent aussi parfois un carte bilinéaire; le mot « bilinéaire » signifie ici essentiellement qu'il satisfait aux contraintes :
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Notez que + et ⋅ peuvent être des opérateurs arbitraires ; lorsque vous créez de nouveaux types d'objets mathématiques sophistiqués, l'algèbre abstraite ne se soucie pas de la façon dont + et ⋅ sont défini, à condition qu'ils soient cohérents de la manière habituelle, par exemple. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) et (�⋅�)+(�⋅�)=(�+�)⋅�.
Si �, �, � et � étaient simples numéros, alors faire un appariement simple est facile : on peut faire �(�,�)=2��. On peut alors voir :
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
C'est bilinéaire !
Cependant, ces appariements simples ne conviennent pas à la cryptographie car les objets sur lesquels ils travaillent sont des entiers simples et sont trop faciles à analyser ; les nombres entiers facilitent la division, le calcul de logarithmes et divers autres calculs ; les entiers simples n'ont aucune notion de « clé publique » ou de « fonction à sens unique ». De plus, avec l'appariement décrit ci-dessus, vous pouvez revenir en arrière – connaissant � et connaissant �(�,�), vous pouvez simplement calculer une division et un logarithme pour déterminer �. Nous voulons des objets mathématiques qui se rapprochent le plus possible des « boîtes noires », où l'on peut additionner, soustraire, multiplier et diviser, mais ne fais rien d'autre. C'est là qu'interviennent les courbes elliptiques et les paires de courbes elliptiques.
Il s'avère qu'il est possible de créer une carte bilinéaire sur des points de courbe elliptique, c'est-à-dire de créer une fonction �(�,�) où les entrées � et � sont des points de courbe elliptique, et où la sortie est ce qu'on appelle un (��)12 éléments (au moins dans le cas spécifique que nous aborderons ici ; les détails diffèrent en fonction des détails de la courbe, nous y reviendrons plus tard), mais le calcul derrière cela est assez complexe.
Tout d’abord, couvrons les champs premiers et les champs d’extension. La jolie courbe elliptique de l'image plus tôt dans cet article ne ressemble à cela que si vous supposez que l'équation de la courbe est définie à l'aide de nombres réels réguliers. Cependant, si nous utilisons réellement des nombres réels normaux en cryptographie, alors vous pouvez utiliser des logarithmes pour « revenir en arrière », et tout se casse ; de plus, la quantité d'espace nécessaire pour stocker et représenter les nombres peut augmenter arbitrairement. Par conséquent, nous utilisons plutôt des nombres dans un champ principal.
Un corps premier est constitué de l'ensemble des nombres 0,1,2…�−1, où � est premier, et les différentes opérations sont définies comme suit :
�+� :(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
Fondamentalement, tous les calculs sont effectués modulo � (voir ici pour une introduction aux mathématiques modulaires). La division est un cas particulier ; normalement, 32 n'est pas un entier, et ici nous voulons traiter uniquement des entiers, nous essayons donc plutôt de trouver le nombre � tel que �⋅2=3, où ⋅ fait bien sûr référence à la multiplication modulaire telle que définie ci-dessus. Grâce à Le petit théorème de Fermat, l'astuce d'exponentiation présentée ci-dessus fait l'affaire, mais il existe également un moyen plus rapide de le faire, en utilisant le Algorithme euclidien étendu. Supposons que � = 7 ; Voici quelques exemples:
2+3=5 % 7=5
4+6=10 % 7=3
2−5=−3 % 7=4
6⋅3=18 % 7=4
3/2=(3⋅25) % 7=5
5⋅2=10 % 7=3
Si vous jouez avec ce genre de calcul, vous remarquerez qu'il est parfaitement cohérent et satisfait à toutes les règles habituelles. Les deux derniers exemples ci-dessus montrent comment (�/�)⋅�=� ; vous pouvez également voir que (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅�, et toutes les autres identités algébriques du lycée que vous connaissez et aimez continuent être vrai également. Dans les courbes elliptiques, en réalité, les points et les équations sont généralement calculés dans des champs premiers.
Maintenant, parlons de champs d'extension. Vous avez probablement déjà vu un champ d'extension auparavant ; l'exemple le plus courant que l'on rencontre dans les manuels de mathématiques est le champ des nombres complexes, où le champ des nombres réels est « étendu » avec l'élément supplémentaire −1=�. Fondamentalement, les champs d'extension fonctionnent en prenant un champ existant, puis en « inventant » un nouvel élément et en définissant la relation entre cet élément et les éléments existants (dans ce cas, �2+1=0), en s'assurant que cette équation n'est pas vraie. pour n'importe quel nombre qui se trouve dans le champ d'origine, et en regardant l'ensemble de toutes les combinaisons linéaires d'éléments du champ d'origine et du nouvel élément que vous venez de créer.
Nous pouvons également faire des extensions de champs premiers ; par exemple, nous pouvons étendre le champ premier mod7 que nous avons décrit ci-dessus avec �, et alors nous pouvons faire :
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Ce dernier résultat peut être un peu difficile à comprendre ; ce qui s'est passé là-bas, c'est que nous décomposons d'abord le produit en 4�⋅2+4�⋅�, ce qui donne 8�−4, et ensuite parce que nous travaillons en mathématiques mod7, cela devient �+3. Pour diviser, on fait :
�/�:(�⋅�(�2−2)) % �
Notez que l'exposant du petit théorème de Fermat est désormais �2 au lieu de �, mais encore une fois, si nous voulons être plus efficaces, nous pouvons également étendre l'algorithme euclidien étendu pour faire le travail. Notez que ��2−1=1 pour tout � dans ce corps, nous appelons donc �2−1 « l’ordre du groupe multiplicatif dans le corps ».
Avec des chiffres réels, le Théorème fondamental de l'algèbre garantit que l'extension quadratique que nous appelons les nombres complexes est « complète » — vous ne pouvez pas l'étendre davantage, car pour toute relation mathématique (au moins, toute relation mathématique définie par une formule algébrique) que vous pouvez établir entre un nouvel élément � et les nombres complexes existants, il est possible de trouver au moins un nombre complexe qui satisfait déjà à cette relation. Cependant, avec les champs premiers, nous n'avons pas ce problème, et nous pouvons donc aller plus loin et faire des extensions cubiques (où la relation mathématique entre un nouvel élément � et des éléments de champ existants est une équation cubique, donc 1,� et �2 sont tous linéairement indépendants les uns des autres), des extensions d'ordre supérieur, des extensions d'extensions, etc. Et ce sont ces types de nombres complexes modulaires suralimentés sur lesquels sont construits les appariements de courbes elliptiques.
Pour ceux qui souhaitent voir les calculs exacts impliqués dans la réalisation de toutes ces opérations écrites dans le code, les champs principaux et les extensions de champ sont implémentés ici : https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Passons maintenant aux appariements de courbes elliptiques. Un appariement de courbes elliptiques (ou plutôt la forme spécifique d'appariement que nous allons explorer ici ; il existe également d'autres types d'appariements, bien que leur logique soit assez similaire) est une application �2×�1→��, où :
- �1 est une courbe elliptique, où les points satisfont une équation de la forme �2=�3+�, et où les deux coordonnées sont des éléments de �� (c'est-à-dire que ce sont des nombres simples, sauf que l'arithmétique se fait modulo un nombre premier)
- �2 est une courbe elliptique, où les points satisfont à la même équation que �1, sauf lorsque les coordonnées sont des éléments de (��)12 (c'est-à-dire que ce sont les nombres complexes suralimentés dont nous avons parlé ci-dessus ; nous définissons un nouveau « nombre magique » " �, qui est défini par un polynôme du 12ème degré comme �12−18⋅�6+82=0)
- �� est le type d’objet dans lequel va le résultat de la courbe elliptique. Dans les courbes que nous regardons, �� vaut (��)12 (le même nombre complexe suralimenté que celui utilisé dans �2)
La principale propriété qu'il doit satisfaire est la bilinéarité, ce qui dans ce contexte signifie que :
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
Il existe deux autres critères importants :
- Calculabilité efficace (par exemple, nous pouvons faire un appariement facile en prenant simplement les logarithmes discrets de tous les points et en les multipliant ensemble, mais c'est aussi difficile en termes de calcul que de casser la cryptographie des courbes elliptiques en premier lieu, donc cela ne compte pas)
- Non-dégénérescence (bien sûr, vous pouvez simplement définir �(�,�)=1, mais ce n'est pas une association particulièrement utile)
Alors, comment faisons-nous cela?
Le calcul expliquant pourquoi les fonctions d'appariement fonctionnent est assez délicat et implique un peu d'algèbre avancée allant même au-delà de ce que nous avons vu jusqu'à présent, mais je vais vous en fournir un aperçu. Tout d'abord, nous devons définir le concept de diviseur, essentiellement une manière alternative de représenter des fonctions sur des points de courbe elliptique. Un diviseur d’une fonction compte essentiellement les zéros et les infinis de la fonction. Pour voir ce que cela signifie, passons en revue quelques exemples. Fixons un point �=(��,��), et considérons la fonction suivante :
�(�,�)=�−��
Le diviseur est [�]+[−�]−2⋅[�] (les crochets sont utilisés pour représenter le fait que nous faisons référence à la présence du point � dans l'ensemble des zéros et des infinis de la fonction, pas le point P lui-même ; [�]+[�] est ne sauraient la même chose que [�+�]). Le raisonnement est le suivant :
- La fonction est égale à zéro en �, puisque � is ��, donc �−��=0
- La fonction est égale à zéro en −�, puisque −� et � partagent la même coordonnée �
- La fonction va vers l’infini lorsque � va vers l’infini, on dit donc que la fonction est égale à l’infini en �. Il y a une raison technique pour laquelle cet infini doit être compté deux fois, donc � est ajouté avec une « multiplicité » de −2 (négative car c'est un infini et non un zéro, deux à cause de ce double comptage).
La raison technique est à peu près la suivante : parce que l'équation de la courbe est �3=�2+�,� va à l'infini "1.5 fois plus vite" que � pour que �2 suive �3 ; par conséquent, si une fonction linéaire comprend seulement � alors elle est représentée comme une infinité de multiplicité 2, mais si elle inclut � alors elle est représentée comme une infinité de multiplicité 3.
Considérons maintenant une « fonction de ligne » :
��+��+��=0
Où �, � et � sont soigneusement choisis pour que la droite passe par les points � et �. En raison du fonctionnement de l'addition de courbe elliptique (voir le diagramme en haut), cela signifie également qu'elle passe par −�−�. Et cela va jusqu'à l'infini en fonction de � et de �, donc le diviseur devient [�]+[�]+[−�−�]−3⋅[�].
Nous savons que chaque « fonction rationnelle » (c’est-à-dire une fonction définie uniquement à l’aide d’un nombre fini d’opérations +,−,⋅ et / sur les coordonnées du point) correspond de manière unique à un diviseur, jusqu’à multiplication par une constante (c’est-à-dire. si deux fonctions � et � ont le même diviseur, alors �=�⋅� pour une constante �).
Pour deux fonctions � et � quelconques, le diviseur de �⋅� est égal au diviseur de � plus le diviseur de � (dans les manuels de mathématiques, vous verrez (�⋅�)=(�)+(�)), donc par exemple si �(�,�)=��−�, alors (�3)=3⋅[�]+3⋅[−�]−6⋅[�] ; � et −� sont « comptés triplement » pour tenir compte du fait que �3 se rapproche de 0 à ces points « trois fois plus rapidement » dans un certain sens mathématique.
Notez qu'il existe un théorème qui stipule que si vous « supprimez les crochets » d'un diviseur d'une fonction, la somme des points doit donner �([�]+[�]+[−�−�]−3⋅[ �] s’ajuste clairement, car �+�−�−�−3⋅�=�), et tout diviseur qui a cette propriété est le diviseur d’une fonction.
Maintenant, nous sommes prêts à examiner les paires de Tate. Considérons les fonctions suivantes, définies via leurs diviseurs :
- (��)=�⋅[�]−�⋅[�], où � est de l'ordre de �1, c'est-à-dire. �⋅�=� pour tout �
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
Regardons maintenant le produit ��⋅��⋅��. Le diviseur est :
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅[�]
Ce qui se simplifie parfaitement en :
�⋅[�+�]−�⋅[�]
Notez que ce diviseur a exactement le même format que le diviseur pour �� et �� ci-dessus. Par conséquent, ��⋅��⋅��=��+�.
Maintenant, nous introduisons une procédure appelée « étape d’exponentiation finale », où nous prenons le résultat de nos fonctions ci-dessus (��,��, etc.) et l’élevons à la puissance �=(�12−1)/�, où �12−1 est l’ordre du groupe multiplicatif dans (��)12 (c’est-à-dire pour tous �∈(��)12,�(�12−1)=1). Notez que si vous appliquez cette exponentiation à un résultat qui a déjà étant élevé à la puissance �, vous obtenez une exponentiation à la puissance �12−1, donc le résultat devient 1. Ainsi, après l'exponentiation finale, �� s'annule et nous obtenons ���⋅���=( ��+�)�. Il y a une certaine bilinéarité pour vous.
Maintenant, si vous voulez créer une fonction bilinéaire dans les deux arguments, vous devez vous lancer dans des mathématiques plus effrayantes, où au lieu de prendre directement �� d'une valeur, vous prenez �� d'un diviseur, et c'est de là que vient le « jumelage Tate » complet. Pour prouver d’autres résultats, il faut traiter des notions telles que « l’équivalence linéaire » et la « réciprocité de Weil », et le terrier du lapin continue à partir de là. Vous pouvez trouver plus de matériel de lecture sur tout cela ici ainsi que les ici.
Pour une implémentation d'une version modifiée du couplage Tate, appelé couplage Ate optimal, voir ici. Le code implémente L'algorithme de Miller, ce qui est nécessaire pour calculer réellement ��.
Notez que le fait que de tels appariements soient possibles est en quelque sorte une bénédiction mitigée : d'une part, cela signifie que tous les protocoles que nous pouvons faire avec des appariements deviennent possibles, mais cela signifie également que nous devons faire plus attention aux courbes elliptiques. nous utilisons.
Chaque courbe elliptique a une valeur appelée degré d'intégration; essentiellement, le plus petit � tel que ��−1 est un multiple de � (où � est le nombre premier utilisé pour le champ et � est l'ordre de la courbe). Dans les champs ci-dessus, �=12, et dans les champs utilisés pour l'ECC traditionnel (c'est-à-dire où nous ne nous soucions pas des appariements), le degré d'intégration est souvent extrêmement grand, au point que les appariements sont impossibles à calculer informatiquement ; cependant, si nous n'y prêtons pas attention, nous pouvons générer des champs où �=4 ou même 1.
Si �=1, alors le problème du « logarithme discret » pour les courbes elliptiques (essentiellement, récupérer � en connaissant seulement le point �=�⋅�, le problème que vous devez résoudre pour « déchiffrer » une clé privée de courbe elliptique) peut être réduit dans un problème mathématique similaire sur ��, où le problème devient beaucoup plus simple (c'est ce qu'on appelle le Attaque MOV); l'utilisation de courbes avec un degré d'intégration de 12 ou plus garantit que cette réduction n'est pas disponible, ou que résoudre le problème du log discret sur les résultats d'appariement est au moins aussi difficile que de récupérer une clé privée à partir d'une clé publique « de la manière normale » (c.-à-d. informatiquement irréalisable). Ne t'inquiète pas; tous les paramètres de la courbe standard ont été minutieusement vérifiés pour ce problème.
Restez à l'écoute pour une explication mathématique du fonctionnement des zk-SNARK, à venir.
Un merci spécial à Christian Reitwiessner, Ariel Gabizon (de Zcash) et Alfred Menezes pour la révision et les corrections.
- Contenu propulsé par le référencement et distribution de relations publiques. Soyez amplifié aujourd'hui.
- PlatoData.Network Ai générative verticale. Autonomisez-vous. Accéder ici.
- PlatoAiStream. Intelligence Web3. Connaissance Amplifiée. Accéder ici.
- PlatonESG. Carbone, Technologie propre, Énergie, Environnement, Solaire, La gestion des déchets. Accéder ici.
- PlatoHealth. Veille biotechnologique et essais cliniques. Accéder ici.
- Décalages de bloc. Modernisation de la propriété des compensations environnementales. Accéder ici.
- La source: Intelligence de données Platon.