Vitalik Buterin prin intermediul Blogul Vitalik Buterin
Aceasta este o oglindă a postării de la https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
Avertisment de declanșare: matematică.
Una dintre primitivele criptografice cheie din spatele diferitelor construcții, inclusiv semnăturile de prag deterministe, zk-SNARK-urile și alte forme mai simple de dovezi cu cunoștințe zero este împerecherea curbei eliptice. Perechile de curbe eliptice (sau „hărți bilineare”) sunt o completare recentă la o istorie de 30 de ani de utilizare a curbelor eliptice pentru aplicații criptografice, inclusiv criptarea și semnăturile digitale; împerecherile introduc o formă de „multiplicare criptată”, extinzând foarte mult ceea ce pot face protocoalele bazate pe curbe eliptice. Scopul acestui articol va fi de a intra în perechi de curbe eliptice în detaliu și de a explica o schiță generală a modului în care funcționează.
Nu ești de așteptat să înțelegi totul aici prima dată când îl citești sau chiar a zecea oară; chestiile astea sunt cu adevărat grele. Dar sperăm că acest articol vă va oferi măcar o idee despre ce se întâmplă sub capotă.
Curbele eliptice în sine sunt un subiect netrivial de înțeles, iar acest articol va presupune în general că știți cum funcționează; dacă nu, vă recomand acest articol aici ca un primer: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Ca un rezumat rapid, criptografia cu curbe eliptice implică obiecte matematice numite „puncte” (acestea sunt puncte literale bidimensionale cu coordonate (�,�)), cu formule speciale de adunare și scădere (adică pentru calcularea coordonatelor lui �=). �+�) și, de asemenea, puteți înmulți un punct cu un număr întreg (adică �⋅�=�+�+…+�, deși există o modalitate mult mai rapidă de a-l calcula dacă � este mare).
Iată cum arată grafic adăugarea punctelor.
Există un punct special numit „punct la infinit” (�), echivalentul lui zero în aritmetica punctului; este întotdeauna cazul că �+�=�. De asemenea, o curbă are un „comandă„; există un număr � astfel încât �⋅�=� pentru orice � (și desigur, �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5 și așa mai departe). Există, de asemenea, de comun acord despre „punct generator” �, care se înțelege că reprezintă într-un anumit sens numărul 1. Teoretic, orice punct de pe o curbă (cu excepția �) poate fi �; tot ceea ce contează este că � este standardizat.
Împerecherile merg un pas mai departe, deoarece vă permit să verificați anumite tipuri de ecuații mai complicate pe punctele curbei eliptice — de exemplu, dacă �=�⋅�,�=�⋅� și �=�⋅�, puteți verifica dacă sau nu �⋅�=�, având doar �,� și � ca intrări. Acest lucru ar putea părea că garanțiile fundamentale de securitate ale curbelor eliptice sunt încălcate, deoarece informațiile despre � se scurg doar din cunoașterea lui P, dar se dovedește că scurgerea este foarte limitată - în special, problema decizională Diffie Hellman este ușor, dar problema computațională Diffie Hellman (știind � și � în exemplul de mai sus, tehnica de calcul �=�⋅�⋅�) și problema logaritmului discret (recuperarea � din �) rămân infezabile din punct de vedere computațional (cel puțin, dacă au fost înainte).
Un al treilea mod de a vedea ce fac împerecherile, și unul care este poate cel mai iluminator pentru majoritatea cazurilor de utilizare despre care ne referim, este că dacă priviți punctele curbei eliptice ca numere criptate unidirecționale (adică ���� ���(�)=�⋅�=�), atunci în timp ce matematica tradițională a curbei eliptice vă permite să verificați liniar constrângeri asupra numerelor (de exemplu, dacă �=�⋅�,�=�⋅� și �=�⋅�, verificarea 5⋅�+7⋅�=11⋅� este într-adevăr verificând că 5⋅�+7⋅�=11⋅�), împerecherile vă permit să verificați pătratic constrângeri (de exemplu, verificarea �(�,�)⋅�(�,�⋅5)=1 este într-adevăr verificând că �⋅�+5=0). Și trecerea la pătratică este suficientă pentru a ne permite să lucrăm cu semnături de prag deterministe, programe de aritmetică pătratică și toate celelalte lucruri bune.
Acum, ce este acest operator amuzant �(�,�) pe care l-am introdus mai sus? Aceasta este perechea. Matematicienii o mai numesc uneori a hartă biliniară; cuvântul „bilinear” aici înseamnă practic că satisface constrângerile:
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Rețineți că + și ⋅ pot fi operatori arbitrari; când creați noi tipuri de obiecte matematice, algebrei abstracte nu-i pasă cum sunt + și ⋅ definit, atâta timp cât sunt consecvente în modurile obișnuite, de ex. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) și (�⋅�)+(�⋅�)=(�+�)⋅�.
Dacă �, �, � și � ar fi simple numere, atunci a face o împerechere simplă este ușor: putem face �(�,�)=2��. Apoi, putem vedea:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
Este biliniar!
Totuși, astfel de perechi simple nu sunt potrivite pentru criptografie deoarece obiectele pe care lucrează sunt numere întregi simple și sunt prea ușor de analizat; numerele întregi facilitează împărțirea, calcularea logaritmilor și efectuarea diferitelor alte calcule; numerele întregi simple nu au conceptul de „cheie publică” sau „funcție unidirecțională”. În plus, cu împerecherea descrisă mai sus puteți merge înapoi – cunoscând � și știind �(�,�), puteți calcula pur și simplu o diviziune și un logaritm pentru a determina �. Dorim obiecte matematice cât mai apropiate de „cutiile negre”, unde puteți adăuga, scădea, înmulți și împărți, dar nu face nimic altceva. Aici intervin curbele eliptice și perechile de curbe eliptice.
Se dovedește că este posibil să se realizeze o hartă biliniară peste punctele curbei eliptice - adică să se creeze o funcție �(�,�) în care intrările � și � sunt puncte ale curbei eliptice și unde rezultatul este ceea ce se numește o Elementul (��)12 (cel puțin în cazul specific pe care îl vom acoperi aici; specificul diferă în funcție de detaliile curbei, mai multe despre asta mai târziu), dar matematica din spatele acestui lucru este destul de complexă.
Mai întâi, să acoperim câmpurile principale și câmpurile de extensie. Curba destul de eliptică din imaginea de mai devreme în această postare arată așa doar dacă presupuneți că ecuația curbei este definită folosind numere reale obișnuite. Cu toate acestea, dacă folosim efectiv numere reale obișnuite în criptografie, atunci puteți folosi logaritmi pentru a „mergi înapoi” și totul se rupe; în plus, cantitatea de spațiu necesară pentru stocarea și reprezentarea efectivă a numerelor poate crește în mod arbitrar. Prin urmare, folosim în schimb numere în a câmp prim.
Un câmp prim este format din mulțimea de numere 0,1,2…�−1, unde � este prim, iar diferitele operații sunt definite după cum urmează:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
Practic, toată matematica se face modulo � (vezi aici pentru o introducere în matematica modulară). Diviziunea este un caz special; în mod normal, 32 nu este un număr întreg și aici vrem să ne ocupăm doar de numere întregi, așa că încercăm în schimb să găsim numărul � astfel încât �⋅2=3, unde ⋅ se referă, desigur, la înmulțirea modulară așa cum a fost definită mai sus. Mulțumită Mica teoremă a lui Fermat, trucul de exponențiere prezentat mai sus face treaba, dar există și o modalitate mai rapidă de a o face, folosind Algoritmul euclidian extins. Să presupunem �=7; iată câteva exemple:
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
Dacă te joci cu acest tip de matematică, vei observa că este perfect consecventă și îndeplinește toate regulile obișnuite. Ultimele două exemple de mai sus arată cum (�/�)⋅�=�; de asemenea, puteți vedea că (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅� și toate celelalte identități algebrice de liceu pe care le cunoașteți și le iubiți continuă să fie și adevărată. În curbele eliptice în realitate, punctele și ecuațiile sunt de obicei calculate în câmpuri prime.
Acum, să vorbim despre câmpurile de extensie. Probabil că ați văzut deja un câmp de extensie înainte; cel mai comun exemplu pe care îl întâlniți în manualele de matematică este domeniul numerelor complexe, unde câmpul numerelor reale este „extins” cu elementul suplimentar −1=�. Practic, câmpurile de extensie funcționează luând un câmp existent, apoi „inventând” un nou element și definind relația dintre acel element și elementele existente (în acest caz, �2+1=0), asigurându-vă că această ecuație nu este adevărată. pentru orice număr care se află în câmpul inițial și privind setul tuturor combinațiilor liniare de elemente din câmpul original și noul element pe care tocmai l-ați creat.
Putem face și extensii ale câmpurilor prime; de exemplu, putem extinde câmpul prim mod7 pe care l-am descris mai sus cu � și apoi putem face:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Acest ultim rezultat poate fi puțin greu de înțeles; ceea ce s-a întâmplat acolo a fost că mai întâi descompunem produsul în 4�⋅2+4�⋅�, ceea ce dă 8�−4, și apoi pentru că lucrăm în mod7 matematică care devine �+3. Pentru a împărți, facem:
�/�:(�⋅�(�2−2)) % �
Rețineți că exponentul pentru mica teoremă a lui Fermat este acum �2 în loc de �, deși încă o dată, dacă vrem să fim mai eficienți, putem extinde și algoritmul euclidian extins pentru a face treaba. Rețineți că ��2−1=1 pentru orice � din acest câmp, deci numim �2−1 „ordinea grupului multiplicativ din câmp”.
Cu numere reale, the Teorema fundamentală a algebrei asigură că extensia pătratică pe care o numim numere complexe este „completă” - nu o puteți extinde mai departe, deoarece pentru orice relație matematică (cel puțin, orice relație matematică definită printr-o formulă algebrică) pe care o puteți găsi între un element nou � și numerele complexe existente, este posibil să veniți cu cel puțin un număr complex care să satisfacă deja acea relație. Cu câmpurile prime, totuși, nu avem această problemă și, prin urmare, putem merge mai departe și putem face extensii cubice (unde relația matematică dintre un element nou � și elementele de câmp existente este o ecuație cubică, deci 1,� și �2 sunt toate liniar independente unele de altele), extensii de ordin superior, extensii de extensii etc. Și pe aceste tipuri de numere complexe modulare supraalimentate sunt construite perechile de curbe eliptice.
Pentru cei interesați să vadă matematica exactă implicată în realizarea tuturor acestor operațiuni scrise în cod, câmpurile prime și extensiile de câmp sunt implementate aici: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Acum, trecem la perechi de curbe eliptice. O împerechere de curbă eliptică (sau mai degrabă, forma specifică de împerechere pe care o vom explora aici; există și alte tipuri de împerecheri, deși logica lor este destul de similară) este o hartă �2×�1→��, unde:
- �1 este o curbă eliptică, în care punctele satisfac o ecuație de forma �2=�3+� și unde ambele coordonate sunt elemente ale lui �� (adică sunt numere simple, cu excepția faptului că aritmetica se face modulo un număr prim)
- �2 este o curbă eliptică, în care punctele satisfac aceeași ecuație ca și �1, cu excepția cazului în care coordonatele sunt elemente ale lui (��)12 (adică sunt numerele complexe supraalimentate despre care am vorbit mai sus; definim un nou „număr magic ” �, care este definit de un polinom de gradul 12 precum �12−18⋅�6+82=0)
- �� este tipul de obiect în care intră rezultatul curbei eliptice. În curbele pe care le privim, �� este (��)12 (același număr complex supraalimentat ca cel folosit în �2)
Principala proprietate pe care trebuie să o îndeplinească este biliniaritatea, ceea ce în acest context înseamnă că:
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
Există alte două criterii importante:
- Calculabilitate eficientă (de exemplu, putem face o împerechere ușoară luând pur și simplu logaritmii discreti ai tuturor punctelor și înmulțindu-le împreună, dar acest lucru este la fel de greu din punct de vedere computațional ca și ruperea criptografiei cu curbe eliptice în primul rând, deci nu contează)
- Non-degenerare (sigur, puteți defini doar �(�,�)=1, dar aceasta nu este o pereche deosebit de utilă)
Deci, cum facem asta?
Matematica din spatele motivului pentru care funcțiile de împerechere funcționează este destul de complicată și implică un pic de algebră avansată, care merge chiar și dincolo de ceea ce am văzut până acum, dar voi oferi o schiță. În primul rând, trebuie să definim conceptul de a compas, practic o modalitate alternativă de reprezentare a funcțiilor pe punctele curbei eliptice. Un divizor al unei funcții numără practic zerourile și infinititățile funcției. Pentru a vedea ce înseamnă asta, hai să trecem prin câteva exemple. Să reparăm un punct �=(��,��) și să luăm în considerare următoarea funcție:
�(�,�)=�−��
Împărțitorul este [�]+[−�]−2⋅[�] (parantezele pătrate sunt folosite pentru a reprezenta faptul că ne referim la prezența punctului � în mulțimea de zerouri și infinitate a funcției, nu punctul P în sine; [�]+[�] este nu același lucru ca [�+�]). Raționamentul este următorul:
- Funcția este egală cu zero la �, deoarece � is ��, deci �−��=0
- Funcția este egală cu zero la −�, deoarece −� și � au aceeași coordonată �
- Funcția merge la infinit pe măsură ce � merge la infinit, deci spunem că funcția este egală cu infinit la �. Există un motiv tehnic pentru care acest infinit trebuie să fie numărat de două ori, așa că � se adaugă cu o „multiplicitate” de −2 (negativ pentru că este un infinit și nu un zero, doi din cauza acestei numărări duble).
Motivul tehnic este aproximativ acesta: deoarece ecuația curbei este �3=�2+�,� merge la infinit „de 1.5 ori mai rapid” decât o face � pentru ca �2 să țină pasul cu �3; prin urmare, dacă o funcție liniară include numai �, atunci este reprezentată ca o infinitate a multiplicității 2, dar dacă include � atunci este reprezentată ca o infinitate a multiplicității 3.
Acum, luați în considerare o „funcție linie”:
��+��+�=0
Unde �, � și � sunt alese cu grijă, astfel încât linia să treacă prin punctele � și �. Din cauza modului în care funcționează adăugarea curbei eliptice (vezi diagrama din partea de sus), aceasta înseamnă, de asemenea, că trece prin −�−�. Și merge până la infinit în funcție de ambele � și �, deci divizorul devine [�]+[�]+[−�−�]−3⋅[�].
Știm că fiecare „funcție rațională” (adică o funcție definită doar folosind un număr finit de +,−,⋅ și / operații pe coordonatele punctului) corespunde în mod unic unui anumit divizor, până la înmulțirea cu o constantă (adică. dacă două funcții � și � au același divizor, atunci �=�⋅� pentru o constantă �).
Pentru oricare două funcții � și �, divizorul lui �⋅� este egal cu divizorul lui � plus divizorul lui � (în manualele de matematică, veți vedea (�⋅�)=(�)+(�)), deci de exemplu dacă �(�,�)=��−�, atunci (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � și −� sunt „numărate de trei ori” pentru a explica faptul că �3 se apropie de 0 în acele puncte „de trei ori mai repede” într-un anumit sens matematic.
Rețineți că există o teoremă care afirmă că, dacă „eliminați parantezele pătrate” dintr-un divizor al unei funcții, punctele trebuie să adună până la �([�]+[�]+[−�−�]−3⋅[ �] se potrivește clar, ca �+�−�−�−3⋅�=�), și orice divizor care are această proprietate este divizorul unei funcții.
Acum, suntem gata să ne uităm la perechile Tate. Luați în considerare următoarele funcții, definite prin divizorii lor:
- (��)=�⋅[�]−�⋅[�], unde � este de ordinul lui �1, adică. �⋅�=� pentru orice �
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
Acum, să ne uităm la produsul ��⋅��⋅��. Divizorul este:
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅[�]
Ceea ce se simplifică clar la:
�⋅[�+�]−�⋅[�]
Observați că acest divizor are exact același format ca și divizorul pentru �� și �� de mai sus. Prin urmare, ��⋅��⋅��=��+�.
Acum, introducem o procedură numită pasul de „exponențiere finală”, în care luăm rezultatul funcțiilor noastre de mai sus (��,��, etc.) și îl ridicăm la puterea �=(�12−1)/�, unde �12−1 este ordinul grupului multiplicativ din (��)12 (adică pentru Orice �∈(��)12,�(�12−1)=1). Observați că dacă aplicați această exponențiere oricărui rezultat care are deja a fost ridicat la puterea lui �, obțineți o exponențiere la puterea lui �12−1, deci rezultatul se transformă în 1. Prin urmare, după exponențiarea finală, �� se anulează și obținem ���⋅���=( ��+�)�. Există o oarecare bilinearitate pentru tine.
Acum, dacă doriți să faceți o funcție biliniară în ambele argumente, trebuie să treceți la matematică mai înfricoșătoare, unde în loc să luați direct �� dintr-o valoare, luați �� dintr-o compas, și de aici provine „împerecherea Tate” completă. Pentru a dovedi mai multe rezultate, trebuie să te ocupi de noțiuni precum „echivalență liniară” și „reciprocitate Weil”, iar de acolo se continuă grozava. Puteți găsi mai multe materiale de lectură despre toate acestea aici și aici.
Pentru o implementare a unei versiuni modificate a asocierii Tate, numită asociere Ate optimă, Vezi aici. Codul implementează algoritmul lui Miller, care este necesar pentru a calcula efectiv ��.
Rețineți că faptul că astfel de perechi sunt posibile este oarecum o binecuvântare mixtă: pe de o parte, înseamnă că toate protocoalele pe care le putem face cu asocieri devin posibile, dar înseamnă și că trebuie să fim mai atenți la ce curbe eliptice folosim.
Fiecare curbă eliptică are o valoare numită an gradul de încorporare; în esență, cel mai mic � astfel încât ��−1 este un multiplu al � (unde � este primul folosit pentru câmp și � este ordinea curbei). În câmpurile de mai sus, �=12, și în câmpurile folosite pentru ECC tradițional (adică unde nu ne pasă de împerecheri), gradul de încorporare este adesea extrem de mare, până la punctul în care împerecherile sunt imposibil de calculat din punct de vedere computațional; totuși, dacă nu suntem atenți, atunci putem genera câmpuri în care �=4 sau chiar 1.
Dacă �=1, atunci problema „logaritmului discret” pentru curbele eliptice (în esență, recuperând � cunoscând doar punctul �=�⋅�, problema pe care trebuie să o rezolvi pentru a „rupe” o cheie privată de curbă eliptică) poate fi redusă într-o problemă de matematică similară peste ��, unde problema devine mult mai ușoară (aceasta se numește Atacul MOV); utilizarea curbelor cu un grad de încorporare de 12 sau mai mare asigură că această reducere este fie indisponibilă, fie că rezolvarea problemei jurnalului discret asupra rezultatelor asocierii este cel puțin la fel de dificilă ca recuperarea unei chei private de la o cheie publică „modul normal” (de ex. imposibil din punct de vedere computațional). Nu vă faceți griji; toți parametrii curbei standard au fost verificați temeinic pentru această problemă.
Rămâneți pe fază pentru o explicație matematică a modului în care funcționează zk-SNARK-urile, în curând.
Mulțumiri speciale lui Christian Reitwiessner, Ariel Gabizon (de la Zcash) și Alfred Menezes pentru revizuire și corectări.
- Distribuție de conținut bazat pe SEO și PR. Amplifică-te astăzi.
- PlatoData.Network Vertical Generative Ai. Împuterniciți-vă. Accesați Aici.
- PlatoAiStream. Web3 Intelligence. Cunoștințe amplificate. Accesați Aici.
- PlatoESG. carbon, CleanTech, Energie, Mediu inconjurator, Solar, Managementul deșeurilor. Accesați Aici.
- PlatoHealth. Biotehnologie și Inteligență pentru studii clinice. Accesați Aici.
- BlockOffsets. Modernizarea proprietății de compensare a mediului. Accesați Aici.
- Sursa: Inteligența datelor Platon.