Vitalik Buterin prek Blog Vitalika Buterina
To je ogledalo objave na https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
Opozorilo sprožilca: matematika.
Eden od ključnih kriptografskih primitivov za različnimi konstrukcijami, vključno z determinističnimi podpisi pragov, zk-SNARK in drugimi enostavnejšimi oblikami dokazov brez znanja, je združevanje eliptičnih krivulj. Eliptični pari krivulj (ali "bilinearni zemljevidi") so nedavni dodatek k 30-letni zgodovini uporabe eliptičnih krivulj za kriptografske aplikacije, vključno s šifriranjem in digitalnimi podpisi; seznanjanje uvaja obliko "šifriranega množenja", ki močno razširja, kaj lahko storijo protokoli, ki temeljijo na eliptičnih krivuljah. Namen tega članka bo podrobno obravnavati pare eliptičnih krivulj in razložiti splošen oris njihovega delovanja.
Od vas se ne pričakuje, da boste razumeli vse tukaj, ko ga berete prvič ali celo desetič; te stvari so res težke. Upajmo pa, da vam bo ta članek dal vsaj malo predstave o tem, kaj se dogaja pod pokrovom.
Eliptične krivulje same po sebi so precej netrivialna tema za razumevanje in ta članek bo na splošno predvideval, da veste, kako delujejo; če ne, priporočam ta članek kot primer: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Kot hiter povzetek, kriptografija eliptične krivulje vključuje matematične objekte, imenovane "točke" (to so dobesedne dvodimenzionalne točke s (�,�) koordinatami), s posebnimi formulami za njihovo seštevanje in odštevanje (tj. za izračun koordinat �= �+�), točko pa lahko tudi pomnožite s celim številom (tj. �⋅�=�+�+…+�, čeprav obstaja veliko hitrejši način za izračun, če je � veliko).
Takole je grafično videti seštevanje točk.
Obstaja posebna točka, imenovana "točka v neskončnosti" (�), ki je enaka ničli v aritmetiki točk; vedno velja, da je �+�=�. Poleg tega ima krivulja "Da“; obstaja število � tako, da je �⋅�=� za poljubno � (in seveda �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5 in tako naprej). Obstaja tudi nekaj splošno dogovorjenih "generatorskih točk" �, za katere se razume, da v nekem smislu predstavljajo število 1. Teoretično je katera koli točka na krivulji (razen �) lahko �; pomembno je le, da je � standardiziran.
Seznanjanje gre še korak dlje, saj vam omogoča preverjanje določenih vrst bolj zapletenih enačb na točkah eliptične krivulje – na primer, če je �=�⋅�,�=�⋅� in �=�⋅�, lahko preverite, ali ne �⋅�=�, ki ima samo �,� in � kot vhodne podatke. To se morda zdi, kot da so temeljna varnostna jamstva eliptičnih krivulj porušena, saj informacije o � uhajajo samo zaradi poznavanja P, vendar se izkaže, da je uhajanje zelo omejeno - natančneje, odločitveni problem Diffie Hellman je enostaven, vendar računski problem Diffie Hellman (če poznamo � in � v zgornjem primeru, računalništvo �=�⋅�⋅�) in problem diskretnega logaritma (obnavljanje � iz �) ostajajo računsko neizvedljive (vsaj, če so bile prej).
Tretji način, kako pogledati, kaj počnejo pari, in tisti, ki je morda najbolj razsvetljujoč za večino primerov uporabe, ki jih obravnavamo, je ta, da na točke eliptične krivulje gledate kot na enosmerno šifrirana števila (to je ���� ���(�)=�⋅�=�), medtem ko vam tradicionalna matematika eliptične krivulje omogoča preverjanje linearna omejitve števil (npr. če je �=�⋅�,�=�⋅� in �=�⋅�, je preverjanje 5⋅�+7⋅�=11⋅� res preverjanje, da je 5⋅�+7⋅�=11⋅�), pari vam omogočajo preverjanje kvadratna omejitve (npr. preverjanje �(�,�)⋅�(�,�⋅5)=1 je res preverjanje, da je �⋅�+5=0). In prehod na kvadratno je dovolj, da lahko delamo z determinističnimi podpisi praga, programi za kvadratno aritmetiko in vsemi drugimi dobrimi stvarmi.
Zdaj pa, kaj je ta smešni �(�,�) operator, ki smo ga predstavili zgoraj? To je seznanjanje. Matematiki ga včasih imenujejo tudi a bilinearni zemljevid; beseda "bilinearen" tukaj v bistvu pomeni, da izpolnjuje omejitve:
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Upoštevajte, da sta lahko + in ⋅ poljubna operatorja; ko ustvarjate modne nove vrste matematičnih objektov, abstraktni algebri ni mar, kako sta + in ⋅ opredeljen, dokler so dosledni na običajne načine, npr. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) in (�⋅�)+(�⋅�)=(�+�)⋅�.
Če bi bili �, �, � in � preprosti številke, potem je enostavno seznanjanje preprosto: naredimo lahko �(�,�)=2��. Nato lahko vidimo:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
Bilinearno je!
Vendar pa takšna preprosta združevanja niso primerna za kriptografijo, ker so objekti, na katerih delajo, preprosta cela števila in jih je prelahko analizirati; cela števila olajšajo deljenje, računanje logaritmov in različne druge izračune; preprosta cela števila nimajo koncepta "javnega ključa" ali "enosmerne funkcije". Poleg tega se lahko z zgoraj opisanim združevanjem vrnete nazaj – če poznate � in poznate �(�,�), lahko preprosto izračunate deljenje in logaritem, da določite �. Želimo matematične objekte, ki so čim bližje »črnim skrinjicam«, kjer lahko seštevate, odštevate, množite in delite, ampak storiti nič drugega. Tu pridejo na vrsto eliptične krivulje in pari eliptičnih krivulj.
Izkazalo se je, da je mogoče izdelati bilinearni zemljevid nad točkami eliptične krivulje - to je, pripraviti funkcijo �(�,�), kjer sta vhoda � in � točki eliptične krivulje in kjer je izhod tako imenovana (��)12 element (vsaj v posebnem primeru, ki ga bomo obravnavali tukaj; specifike se razlikujejo glede na podrobnosti krivulje, več o tem pozneje), vendar je matematika za tem precej zapletena.
Najprej pokrijmo prapolja in razširitvena polja. Lepa eliptična krivulja na sliki prej v tem prispevku je videti tako le, če predpostavite, da je enačba krivulje definirana z običajnimi realnimi števili. Vendar, če v kriptografiji dejansko uporabljamo običajna realna števila, potem lahko uporabite logaritme, da se "vrnete nazaj", in vse se pokvari; poleg tega se lahko količina prostora, ki je potreben za dejansko shranjevanje in predstavitev števil, poljubno poveča. Zato namesto tega uporabljamo številke v a glavno polje.
Polje praštevil je sestavljeno iz niza števil 0,1,2…�−1, kjer je � praštevilo, različne operacije pa so definirane na naslednji način:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
V bistvu se vsa matematika izvaja po modulu � (glejte tukaj za uvod v modularno matematiko). Delitev je poseben primer; običajno 32 ni celo število in tukaj želimo obravnavati samo cela števila, zato namesto tega poskušamo najti število � tako, da je �⋅2=3, kjer se ⋅ seveda nanaša na modularno množenje, kot je definirano zgoraj. Zahvale gredo Fermatov mali izrek, trik s potenciranjem, prikazan zgoraj, opravi delo, vendar obstaja tudi hitrejši način za to, z uporabo Razširjeni evklidski algoritem. Recimo �=7; tukaj je nekaj primerov:
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
Če se poigrate s to vrsto matematike, boste opazili, da je popolnoma dosledna in izpolnjuje vsa običajna pravila. Zadnja dva zgornja primera prikazujeta, kako (�/�)⋅�=�; lahko vidite tudi, da (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅� in vse druge srednješolske algebraične identitete, ki jih poznate in imate radi, se nadaljujejo da tudi drži. V eliptičnih krivuljah v resnici so točke in enačbe običajno izračunane v prapoljih.
Zdaj pa se pogovorimo razširitvena polja. Verjetno ste že videli razširitveno polje; najpogostejši primer, ki ga srečate v učbenikih za matematiko, je polje kompleksnih števil, kjer je polje realnih števil “razširjeno” z dodatnim elementom −1=�. V bistvu razširitvena polja delujejo tako, da vzamejo obstoječe polje, nato "izumijo" nov element in definirajo razmerje med tem elementom in obstoječimi elementi (v tem primeru �2+1=0), s čimer zagotovijo, da ta enačba ne drži za poljubno število, ki je v izvirnem polju, in gleda na nabor vseh linearnih kombinacij elementov izvirnega polja in novega elementa, ki ste ga pravkar ustvarili.
Delamo lahko tudi razširitve prapolj; na primer, lahko razširimo osnovno polje mod7, ki smo ga opisali zgoraj, z �, nato pa lahko naredimo:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Ta zadnji rezultat je morda nekoliko težko ugotoviti; tam se je zgodilo, da produkt najprej razčlenimo na 4�⋅2+4�⋅�, kar da 8�−4, nato pa, ker delamo v matematiki mod7, postane �+3. Za delitev naredimo:
�/�:(�⋅�(�2−2)) % �
Upoštevajte, da je eksponent za Fermatov mali izrek zdaj �2 namesto �, čeprav lahko ponovno, če želimo biti učinkovitejši, namesto tega razširimo razširjeni evklidski algoritem, da opravi to delo. Upoštevajte, da je ��2−1=1 za kateri koli � v tem polju, zato �2−1 imenujemo “vrstni red multiplikativne skupine v polju”.
Z realnimi številkami, Osnovni izrek algebre zagotavlja, da je kvadratna razširitev, ki ji pravimo kompleksna števila, "popolna" - ne morete je nadalje razširiti, ker za katero koli matematično razmerje (vsaj katero koli matematično razmerje, definirano z algebrsko formulo), ki ga lahko najdete med nekim novim elementom � in obstoječih kompleksnih števil, je mogoče najti vsaj eno kompleksno število, ki že izpolnjuje to razmerje. Pri prapoljih pa te težave nimamo, zato lahko gremo dlje in naredimo kubične razširitve (kjer je matematično razmerje med nekim novim elementom � in obstoječimi elementi polja kubična enačba, torej so 1,� in �2 vsi linearno neodvisni drug od drugega), razširitve višjega reda, razširitve razširitev itd. In na teh vrstah nabitih modularnih kompleksnih števil so zgrajeni pari eliptičnih krivulj.
Za tiste, ki si želijo ogledati natančno matematiko, ki je vključena v izdelavo vseh teh operacij, zapisanih v kodi, so tukaj implementirana prapolja in razširitve polja: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Zdaj pa k parom eliptičnih krivulj. Parjenje eliptične krivulje (ali bolje rečeno, posebna oblika parjenja, ki jo bomo tukaj raziskali; obstajajo tudi druge vrste parjenja, čeprav je njihova logika precej podobna) je preslikava �2×�1→��, kjer:
- �1 je eliptična krivulja, kjer točke zadoščajo enačbi oblike �2=�3+� in kjer sta obe koordinati elementa �� (tj. sta enostavni števili, le da se aritmetika izvaja po modulu nekega praštevila)
- �2 je eliptična krivulja, kjer točke izpolnjujejo isto enačbo kot �1, razen kjer so koordinate elementi (��)12 (tj. so supernabita kompleksna števila, o katerih smo govorili zgoraj; definiramo novo »magično število ” �, ki je definiran s polinomom 12. stopnje, kot je �12−18⋅�6+82=0)
- �� je vrsta predmeta, v katerega gre rezultat eliptične krivulje. V krivuljah, ki si jih ogledamo, je �� (��)12 (isto nabito kompleksno število, kot je uporabljeno v �2)
Glavna lastnost, ki jo mora izpolnjevati, je bilinearnost, kar v tem kontekstu pomeni, da:
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
Obstajata še dve pomembni merili:
- Učinkovita izračunljivost (npr. enostavno združimo lahko tako, da preprosto vzamemo diskretne logaritme vseh točk in jih pomnožimo skupaj, vendar je to računsko tako težko kot razbijanje kriptografije eliptične krivulje na prvem mestu, zato ne šteje)
- Nedegeneriranost (seveda, lahko samo definirate �(�,�)=1, vendar to ni posebno uporabno združevanje)
Kako to storimo?
Matematika, zakaj funkcije združevanja delujejo, je precej zapletena in vključuje kar nekaj napredne algebre, ki celo presega tisto, kar smo videli do zdaj, vendar bom ponudil oris. Najprej moramo definirati pojem a delilnik, v bistvu alternativni način predstavitve funkcij na točkah eliptične krivulje. Delitelj funkcije v bistvu šteje ničle in neskončnosti funkcije. Da bi videli, kaj to pomeni, poglejmo nekaj primerov. Popravimo neko točko ��=(��,��) in razmislimo o naslednji funkciji:
�(�,�)=�−��
Delitelj je [�]+[−�]−2⋅[�] (oglati oklepaji se uporabljajo za prikaz dejstva, da se sklicujemo na prisotnost točke � v nizu ničel in neskončnosti funkcije, ne sama točka P; [�]+[�] je ne enako kot [�+�]). Obrazložitev je naslednja:
- Funkcija je enaka nič pri �, ker � is ��, torej ����=0
- Funkcija je enaka nič pri −�, ker imata −� in � isto � koordinato
- Funkcija gre v neskončnost, ko gre � v neskončnost, zato pravimo, da je funkcija enaka neskončnosti pri �. Obstaja tehnični razlog, zakaj je treba to neskončnost prešteti dvakrat, zato se � doda z "množnico" −2 (negativno, ker je neskončnost in ne ničla, dve zaradi tega dvojnega štetja).
Tehnični razlog je približno naslednji: ker je enačba krivulje �3=�2+�,� gre v neskončnost "1.5-krat hitreje" kot �, da bi �2 sledil �3; torej, če linearna funkcija vključuje samo �, potem je predstavljena kot neskončnost večkratnosti 2, če pa vključuje �, potem je predstavljena kot neskončnost večkratnosti 3.
Zdaj razmislite o "linijski funkciji":
��+��+�=0
Pri čemer so �, � in � skrbno izbrani, tako da premica poteka skozi točki � in �. Zaradi tega, kako deluje seštevanje eliptične krivulje (glej diagram na vrhu), to tudi pomeni, da gre skozi −�−�. In gre do neskončnosti, odvisno od � in �, tako da delitelj postane [�]+[�]+[−�−�]−3⋅[�].
Vemo, da vsaka »racionalna funkcija« (tj. funkcija, definirana samo z uporabo končnega števila +,−,⋅ in / operacij na koordinatah točke) enolično ustreza nekemu delitelju, do množenja s konstanto (tj. če imata dve funkciji � in � enak delitelj, potem je �=�⋅� za neko konstanto �).
Za kateri koli dve funkciji � in � je delitelj �⋅� enak delitelju � plus delitelju � (v učbenikih za matematiko boste videli (�⋅�)=(�)+(�)), če je na primer �(�,�)=��−�, potem (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � in −� se "trojno štejeta", da se upošteva dejstvo, da se �3 približuje 0 na teh točkah "trikrat hitreje" v določenem matematičnem smislu.
Upoštevajte, da obstaja izrek, ki pravi, da če »odstranite oglate oklepaje« z delitelja funkcije, mora biti seštevek točk �([�]+[�]+[−�−�]−3⋅[ �] jasno ustreza, kot �+�−�−�−3⋅�=�), in vsak delitelj, ki ima to lastnost, je delitelj funkcije.
Zdaj smo pripravljeni pogledati pare Tate. Razmislite o naslednjih funkcijah, definiranih prek njihovih deliteljev:
- (��)=�⋅[�]−�⋅[�], kjer je � vrstni red �1, tj. �⋅�=� za katero koli �
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
Zdaj pa poglejmo izdelek ��⋅��⋅��. Delitelj je:
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�⋅[�]
Kar je lepo poenostavljeno na:
�⋅[�+�]−�⋅[�]
Upoštevajte, da je ta delitelj popolnoma enake oblike kot delitelj za �� in �� zgoraj. Zato je ��⋅��⋅��=��+�.
Zdaj uvedemo postopek, imenovan korak "končnega potenciranja", kjer vzamemo rezultat naših zgornjih funkcij (��,�� itd.) in ga dvignemo na potenco �=(�12−1)/�, kjer je �12−1 vrstni red multiplikativne skupine v (��)12 (tj. za kaj �∈(��)12,�(�12−1)=1). Upoštevajte, da če uporabite to potenciranje za kateri koli rezultat, ki ima že povišano na potenco �, dobiš potenciranje na potenco �12−1, tako da se rezultat spremeni v 1. Zato se po končnem potenciranju �� izniči in dobimo ���⋅���=( ��+�)�. Nekaj dvoličnosti je za vas.
Zdaj, če želite narediti funkcijo, ki je bilinearna v obeh argumentih, morate iti v bolj grozljivo matematiko, kjer namesto �� vrednosti vzamete neposredno, �� vrednosti delilnik, in od tod izvira popolno »združevanje Tate«. Če želite dokazati nekaj več rezultatov, se morate ukvarjati s pojmi, kot sta "linearna enakovrednost" in "Weilova vzajemnost", od tam pa se nadaljuje zajčja luknja. O vsem tem lahko najdete več gradiva za branje tukaj in tukaj.
Za izvedbo spremenjene različice združevanja Tate, imenovane optimalno pariranje Ate, glej tukaj. Koda izvaja Millerjev algoritem, ki je potreben za dejansko izračunavanje ��.
Upoštevajte, da je dejstvo, da so takšna združevanja možna, nekoliko mešan blagoslov: po eni strani to pomeni, da postanejo možni vsi protokoli, ki jih lahko izvajamo s seznanjanji, vendar to pomeni tudi, da moramo biti bolj previdni glede eliptičnih krivulj. uporabljamo.
Vsaka eliptična krivulja ima vrednost, imenovano an stopnja vdelave; v bistvu najmanjše �, tako da je ��−1 večkratnik � (kjer je � praštevilo, ki se uporablja za polje, in � je vrstni red krivulje). V zgornjih poljih, �=12, in v poljih, ki se uporabljajo za tradicionalni ECC (tj. kjer nam ni mar za združevanje), je stopnja vdelave pogosto izjemno velika, do te mere, da je združevanje računsko neizvedljivo; če pa nismo previdni, lahko ustvarimo polja, kjer je �=4 ali celo 1.
Če je �=1, potem se lahko problem "diskretnega logaritma" za eliptične krivulje (v bistvu obnovitev � ob poznavanju samo točke �=�⋅�, problem, ki ga morate rešiti, da "razbijete" zasebni ključ eliptične krivulje) zmanjša v podoben matematični problem nad ��, kjer problem postane veliko lažji (to se imenuje MOV napad); uporaba krivulj s stopnjo vdelanosti 12 ali več zagotavlja, da to zmanjšanje bodisi ni na voljo ali pa je reševanje problema diskretnega dnevnika nad rezultati združevanja vsaj tako težko kot obnovitev zasebnega ključa iz javnega ključa "na običajen način" (tj. računsko neizvedljivo). Ne skrbi; vsi parametri standardne krivulje so bili temeljito preverjeni za to težavo.
Spremljajte nas za matematično razlago delovanja zk-SNARK, ki bo kmalu na voljo.
Posebna zahvala Christianu Reitwiessnerju, Arielu Gabizonu (iz Zcash) in Alfredu Menezesu za pregled in popravke.
- Distribucija vsebine in PR s pomočjo SEO. Okrepite se še danes.
- PlatoData.Network Vertical Generative Ai. Opolnomočite se. Dostopite tukaj.
- PlatoAiStream. Web3 Intelligence. Razširjeno znanje. Dostopite tukaj.
- PlatoESG. Ogljik, CleanTech, Energija, Okolje, sončna energija, Ravnanje z odpadki. Dostopite tukaj.
- PlatoHealth. Obveščanje o biotehnologiji in kliničnih preskušanjih. Dostopite tukaj.
- BlockOffsets. Posodobitev okoljskega offset lastništva. Dostopite tukaj.
- vir: Platonova podatkovna inteligenca.