Vitalik Buterin keresztül a Vitalik Buterin Blog
Ez a bejegyzés tükre a címen https://medium.com/@VitalikButerin/exploring-elliptic curve-pairings-c73c1864e627
Kiváltó figyelmeztetés: math.
Az egyik kulcsfontosságú kriptográfiai primitív a különféle konstrukciók mögött, beleértve a determinisztikus küszöb aláírásokat, a zk-SNARK-okat és a nulla tudásalapú bizonyítások más egyszerűbb formáit, az elliptikus görbe párosítás. Az elliptikus görbék párosításai (vagy „bilineáris térképek”) az elliptikus görbék kriptográfiai alkalmazásokhoz, köztük titkosításhoz és digitális aláírásokhoz való használatának 30 éves történetéhez a közelmúltban jöttek létre; A párosítások bevezetik a „titkosított szorzás” formáját, nagymértékben kibővítve az elliptikus görbe alapú protokollok lehetőségeit. Ennek a cikknek az a célja, hogy részletesen kitérjen az elliptikus görbék párosítására, és elmagyarázza azok működésének általános vázlatát.
Nem várható el, hogy itt mindent megértsen, amikor először olvassa, sőt tizedik alkalommal sem; ez a cucc valóban nehéz. De remélhetőleg ez a cikk legalább egy kis ötletet ad arról, hogy mi folyik a motorháztető alatt.
Maguk az elliptikus görbék nagyon nem triviális téma, amelyet meg kell érteni, és ez a cikk általában feltételezi, hogy ismeri a működésüket; ha nem, akkor ezt a cikket ajánlom alapozónak: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Gyors összefoglalóként elmondható, hogy az elliptikus görbe titkosítása matematikai objektumokat foglal magában, amelyeket „pontoknak” neveznek (ezek szó szerinti kétdimenziós pontok (�,�) koordinátákkal), speciális képletekkel ezek összeadására és kivonására (azaz �= koordinátáinak kiszámítására). �+�), és megszorozhat egy pontot egy egész számmal (pl. �⋅�=�+�+…+�, bár van egy sokkal gyorsabb módszer is a kiszámítására, ha � nagy).
Így néz ki grafikusan a pontösszeadás.
Létezik egy speciális pont, az úgynevezett „pont a végtelenben” (�), amely a nulla megfelelője a pontaritmetikában; mindig így van, hogy �+�=�. Ezenkívül egy görbének van egy „érdekében“; létezik egy olyan � szám, hogy �⋅�=� bármely � esetén (és természetesen �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5, és így tovább). Van néhány általánosan elfogadott „generátorpont” �, amely bizonyos értelemben az 1-es számot jelenti. Elméletileg a görbe bármely pontja (kivéve �) lehet �; csak az számít, hogy � szabványos legyen.
A párosítások egy lépéssel tovább mennek, mivel lehetővé teszik bizonyos típusú, bonyolultabb egyenletek ellenőrzését elliptikus görbe pontjain – például ha �=�⋅�,�=�⋅� és �=�⋅�, akkor ellenőrizheti, hogy nem �⋅�=�, csak �,� és � bemenetként. Ez úgy tűnhet, mintha az elliptikus görbék alapvető biztonsági garanciái megsérülnének, mivel a �-ről információ szivárog a P ismeretéből, de kiderül, hogy a szivárgás erősen korlátozott – konkrétan a döntési Diffie Hellman probléma egyszerű, de a számítási Diffie Hellman-probléma (a fenti példában szereplő � és � ismeretében, számítástechnika �=�⋅�⋅�) és a diszkrét logaritmus feladat (helyreállítása �-ból �) számításilag kivitelezhetetlen marad (legalábbis, ha korábban volt).
A párosítások működésének egy harmadik módja, amely talán a legmegvilágítóbb az általunk érintett felhasználási esetek többségében, az az, hogy ha az elliptikus görbe pontjait egyirányú titkosított számoknak tekinti (vagyis ���� ���(�)=�⋅�=�), míg a hagyományos elliptikus görbe matematika lehetővé teszi az ellenőrzést lineáris a számokra vonatkozó megszorítások (pl. ha �=�⋅�,�=�⋅� és �=�⋅�, az 5⋅�+7⋅�=11⋅� ellenőrzése tényleg annak ellenőrzése, hogy 5⋅�+7⋅�=11⋅�), a párosítások lehetővé teszik az ellenőrzést négyzetes megszorítások (pl. a �(�,�)⋅�(�,�⋅5)=1 ellenőrzése tényleg ellenőrizze, hogy �⋅�+5=0). A másodfokúra való fellépés pedig elég ahhoz, hogy dolgozhassunk determinisztikus küszöb aláírásokkal, másodfokú aritmetikai programokkal és minden egyéb jó dologgal.
Nos, mi ez a vicces �(�,�) operátor, amelyet fent bemutattunk? Ez a párosítás. A matematikusok néha a bilineáris térkép; a „bilineáris” szó itt alapvetően azt jelenti, hogy teljesíti a korlátokat:
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Vegye figyelembe, hogy a + és ⋅ tetszőleges operátorok lehetnek; Amikor divatos új típusú matematikai objektumokat hoz létre, az absztrakt algebrának nem számít, hogy + és ⋅ meghatározott, amennyiben konzisztensek a szokásos módon, pl. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) és (�⋅�)+(�⋅�)=(�+�)⋅�.
Ha �, �, � és � egyszerűek lennének számok, akkor az egyszerű párosítás elkészítése egyszerű: megtehetjük, hogy �(�,�)=2��. Akkor láthatjuk:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
Ez bilineáris!
Az ilyen egyszerű párosítások azonban nem alkalmasak kriptográfiára, mert az objektumok, amelyeken dolgoznak, egyszerű egész számok, és túl könnyen elemezhetők; az egész számok megkönnyítik az osztást, a logaritmusok kiszámítását és különféle egyéb számítások elvégzését; az egyszerű egész számoknak nincs fogalmuk a „nyilvános kulcsról” vagy az „egyirányú függvényről”. Ezenkívül a fent leírt párosítással visszafelé is léphet – � ismeretében és �(�,�) ismeretében egyszerűen kiszámíthat egy osztást és egy logaritmust a � meghatározásához. Olyan matematikai objektumokat akarunk, amelyek a lehető legközelebb állnak a „fekete dobozokhoz”, ahol összeadhat, kivonhat, szorozhat és oszthat, de ne csinálj mást. Itt jönnek be az elliptikus görbék és az elliptikus görbék párosításai.
Kiderült, hogy lehetséges bilineáris leképezést készíteni az elliptikus görbe pontjai felett – vagyis kitalálni egy �(�,�) függvényt, ahol a � és � bemenetek elliptikus görbe pontjai, és ahol a kimenet az ún. (��)12 elem (legalábbis abban a konkrét esetben, amelyre itt kitérünk; a konkrétumok a görbe részleteitől függően változnak, erről később), de a matematika ennek hátterében meglehetősen összetett.
Először fedjük le az elsődleges mezőket és a kiterjesztési mezőket. A cikk korábbi képén látható szép elliptikus görbe csak akkor néz ki így, ha feltételezi, hogy a görbeegyenlet szabályos valós számokkal van definiálva. Ha azonban a kriptográfiában ténylegesen szabályos valós számokat használunk, akkor logaritmusokkal lehet „visszafelé menni”, és minden megszakad; emellett a számok tényleges tárolásához és megjelenítéséhez szükséges hely mennyisége tetszőlegesen nőhet. Ezért ehelyett számokat használunk az a-ban elsődleges mező.
Egy prímmező a 0,1,2…�−1 számok halmazából áll, ahol � a prím, és a különböző műveletek a következők:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
Alapvetően minden matematika modulo � (lásd itt a moduláris matematikába való bevezetéshez). Az osztás speciális eset; Általában a 32 nem egész szám, és itt csak egész számokkal akarunk foglalkozni, ezért ehelyett megpróbáljuk megkeresni a � számot úgy, hogy �⋅2=3, ahol a ⋅ természetesen a fent definiált moduláris szorzásra utal. Köszönet Fermat kis tétele, a fent bemutatott hatványozási trükk elvégzi a feladatot, de van ennek gyorsabb módja is, a Kiterjesztett euklideszi algoritmus. Tegyük fel, hogy �=7; íme néhány példa:
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
Ha játszol ezzel a fajta matematikával, észre fogod venni, hogy ez tökéletesen következetes és megfelel az összes szokásos szabálynak. A fenti utolsó két példa azt mutatja, hogyan (�/�)⋅�=�; azt is láthatja, hogy (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅�, és az összes többi középiskolai algebrai identitás, amelyet ismer és szeret hogy igaz is legyen. Az elliptikus görbékben a valóságban a pontokat és az egyenleteket általában prímezőkben számítják ki.
Most beszéljünk kiterjesztési mezők. Valószínűleg már látott már bővítménymezőt; A matematikai tankönyvekben leggyakrabban előforduló példa a komplex számok mezője, ahol a valós számok mezője a −1=� kiegészítő elemmel van „kibővítve”. Alapvetően a kiterjesztési mezők úgy működnek, hogy vesznek egy meglévő mezőt, majd „kitalálnak” egy új elemet, és meghatározzák az elem és a meglévő elemek közötti kapcsolatot (ebben az esetben �2+1=0), ügyelve arra, hogy ez az egyenlet ne igaz legyen. bármely számra, amely az eredeti mezőben található, és az eredeti mező és az imént létrehozott új elem elemeinek összes lineáris kombinációjának halmazát tekintve.
A prím mezők kiterjesztését is elvégezhetjük; például kiterjeszthetjük a mod7 prímmezőt, amit fent leírtunk a �-vel, majd megtehetjük:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Az utolsó eredményt kissé nehéz kitalálni; ott az történt, hogy a szorzatot először 4�⋅2+4�⋅�-re bontjuk, ami 8�−4-et ad, majd mivel a mod7 matematikában dolgozunk, ebből �+3 lesz. A felosztáshoz a következőket tesszük:
�/�:(�⋅�(�2−2)) % �
Ne feledje, hogy Fermat kis tételének kitevője most �2 helyett �, bár még egyszer, ha hatékonyabbak akarunk lenni, ehelyett a kiterjesztett euklideszi algoritmust is kiterjeszthetjük a feladat elvégzésére. Vegye figyelembe, hogy ��2-1=1 minden � esetén ebben a mezőben, ezért a �2-1-et a „mezőben lévő multiplikatív csoport sorrendjének” nevezzük.
Valós számokkal a Algebra alaptétele biztosítja, hogy az általunk komplex számoknak nevezett másodfokú kiterjesztés „teljes” legyen – nem terjesztheti tovább, mert bármilyen matematikai összefüggésre (legalábbis algebrai képlettel definiált matematikai kapcsolatra), amelyet valamilyen új elem között találhat � és a meglévő komplex számok segítségével legalább egy olyan komplex számot találhatunk, amely már kielégíti ezt a kapcsolatot. A prímmezőknél azonban nincs ilyen probléma, így tovább léphetünk, és köbkiterjesztéseket készíthetünk (ahol az új � elem és a meglévő mezőelemek közötti matematikai kapcsolat egy köbös egyenlet, tehát 1,� és �2 mindegyik egymástól lineárisan független), magasabb rendű kiterjesztések, kiterjesztések kiterjesztései stb. És az ilyen típusú szupertöltött moduláris komplex számokra épülnek az elliptikus görbepárosítások.
Azok számára, akik szeretnék látni, hogy pontosan milyen matematikai műveletek szükségesek ezeknek a műveleteknek a kódba írásához, a prímmezők és a mezőbővítmények itt vannak implementálva: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Most pedig térjünk át az elliptikus görbe párosítására. Egy elliptikus görbe párosítás (vagy inkább a párosítás konkrét formája, amelyet itt megvizsgálunk; vannak más típusú párosítások is, bár logikájuk meglehetősen hasonló) egy �2×�1→�� térkép, ahol:
- �1 egy elliptikus görbe, ahol a pontok kielégítik a �2=�3+� formájú egyenletet, és ahol mindkét koordináta a �� eleme (azaz egyszerű számok, kivéve, hogy az aritmetika mindegyiket valamilyen prímszám modulja alapján végezzük)
- A �2 egy elliptikus görbe, ahol a pontok ugyanazt az egyenletet teljesítik, mint az �1, kivéve, ha a koordináták a (��)12 elemei (azaz azok a feltöltött komplex számok, amelyekről fentebb beszéltünk; egy új „varázsszámot” definiálunk ” �, amelyet egy 12. fokú polinom határoz meg, például �12−18⋅�6+82=0)
- �� az objektum típusa, amelybe az elliptikus görbe eredménye kerül. Az általunk vizsgált görbékben a �� (��)12 (ugyanaz a feltöltött komplex szám, mint a �2-ben).
A fő tulajdonság, amelynek meg kell felelnie, a bilinearitás, ami ebben az összefüggésben azt jelenti, hogy:
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
Van még két fontos kritérium:
- Hatékony kiszámíthatóság (pl. egyszerű párosítást készíthetünk úgy, hogy egyszerűen felvesszük az összes pont diszkrét logaritmusát és megszorozzuk őket, de ez számításilag olyan nehéz, mint az elliptikus görbe kriptográfiájának feltörése, tehát nem számít)
- Nem-degeneráltság (Persze, csak definiálhatnád a �(�,�)=1-et, de ez nem túl hasznos párosítás)
Tehát hogyan csináljuk ezt?
A függvények párosításának működési okai mögött meghúzódó matematika meglehetősen bonyolult, és meglehetősen fejlett algebrát foglal magában, még az eddig látottakon is túlmutatva, de adok egy vázlatot. Először is meg kell határoznunk a fogalmát osztó, alapvetően a függvények elliptikus görbe pontjain történő ábrázolásának alternatív módja. Egy függvény osztója alapvetően a függvény nulláit és végtelenjeit számolja. Hogy ez mit jelent, nézzünk át néhány példát. Javítsunk ki egy �=(��,��) pontot, és vegyük figyelembe a következő függvényt:
�(�,�)=�−��
Az osztó: [�]+[−�]−2⋅[�] (a szögletes zárójelek azt a tényt jelölik, hogy a a � pont jelenléte a függvény nullák és végteleneinek halmazában, nem maga a P pont; [�]+[�] van nem ugyanaz, mint [�+�]). Az indoklás a következő:
- A függvény �-nél egyenlő nullával, mivel � is ��, tehát �−��=0
- A függvény a −� pontban egyenlő nullával, mivel −� és � ugyanazon a koordinátán
- A függvény úgy megy a végtelenbe, mint a � a végtelenbe, ezért azt mondjuk, hogy a függvény egyenlő a �-nél lévő végtelennel. Technikai oka van annak, hogy ezt a végtelent kétszer kell megszámolni, ezért a � -2-es „sokszorosával” adódik hozzá (negatív, mert végtelen, és nem nulla, kettő a kettős számlálás miatt).
A technikai ok nagyjából a következő: mivel a görbe egyenlete �3=�2+�,� „1.5-szer gyorsabban” megy a végtelenbe, mint a �, hogy �2 lépést tudjon tartani �3-mal; így ha egy lineáris függvény csak �-t tartalmaz, akkor a 2-es multiplicitás végtelenjeként jelenik meg, de ha tartalmazza a �-t, akkor a 3-as multiplicitás végtelenjeként jelenik meg.
Most vegyünk egy „vonalfüggvényt”:
��+��+�=0
Ahol �, � és � gondosan megválasztott, hogy az egyenes átmenjen a � és � pontokon. Az elliptikus görbe összeadása miatt (lásd a diagramot fent), ez azt is jelenti, hogy átmegy a −�−�-n. És felmegy a végtelenbe, � és � függvényében, így az osztó [�]+[�]+[−�−�]−3⋅[�] lesz.
Tudjuk, hogy minden „racionális függvény” (azaz egy csak véges számú +,−,⋅ és / a pont koordinátáin végzett műveletek felhasználásával definiált függvény) egyedileg megfelel valamilyen osztónak, egészen a konstans szorzásáig (pl. ha két � és � függvénynek ugyanaz az osztója, akkor �=�⋅� valamilyen konstans esetén �).
Bármely két � és � függvény esetén a �⋅� osztója megegyezik a � osztójával plusz a � osztójával (a matematikai tankönyvekben a következőt láthatja: (�⋅�)=(�)+(�)), így például ha �(�,�)=��−�, akkor (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; A � és a −� „hármas számolása” annak a ténynek a figyelembevétele érdekében, hogy a �3 ezeken a pontokon „háromszor olyan gyorsan” közelít a 0-hoz, bizonyos matematikai értelemben.
Vegye figyelembe, hogy van egy tétel, amely szerint ha „eltávolítja a szögletes zárójeleket” egy függvény osztójából, akkor a pontok összege �([�]+[�]+[−�−�]−3⋅[ �] egyértelműen illeszkedik, mint �+�−�−�−3⋅�=�), és minden osztó, amely rendelkezik ezzel a tulajdonsággal, egy függvény osztója.
Most készen állunk, hogy megvizsgáljuk a Tate-párosításokat. Tekintsük a következő függvényeket, amelyek osztóikon keresztül definiálhatók:
- (��)=�⋅[�]−�⋅[�], ahol � az �1 sorrendje, azaz. �⋅�=� bármely � esetén
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
Most pedig nézzük a terméket ��⋅��⋅��. Az osztó a következő:
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�]⋅[�]
Ami szépen leegyszerűsíti:
�⋅[�+�]−�⋅[�]
Figyelje meg, hogy ez az osztó pontosan ugyanolyan formátumú, mint a fenti �� és �� osztója. Ezért ��⋅��⋅��=��+�.
Most bevezetjük a „végső hatványozás” lépésnek nevezett eljárást, ahol a fenti függvényeink eredményét (��,�� stb.) vesszük és �=(�12−1)/� hatványra emeljük, ahol �12−1 a szorzócsoport sorrendje (��)12-ben (vagyis bármilyen �∈(��)12,�(�12−1)=1). Figyelje meg, hogy ha ezt a hatványozást bármilyen eredményre alkalmazza, amely rendelkezik már Ha � hatványára emeltük, akkor hatványozást kapunk �12−1 hatványára, így az eredmény 1-re változik. Így a végső hatványozás után a �� megszűnik, és azt kapjuk, hogy ���⋅���=( ��+�)�. Van benned némi bilinearitás.
Most, ha olyan függvényt szeretne létrehozni, amely mindkét argumentumban bilineáris, akkor a kísértetiesebb matematikára kell mennie, ahol ahelyett, hogy közvetlenül vesz egy értéket, inkább egy értéket vesz fel. osztó, és innen ered a teljes „Tate párosítás”. További eredmények bizonyításához olyan fogalmakkal kell foglalkozni, mint a „lineáris ekvivalencia” és a „Weil-reciprocitás”, és a nyúllyuk innentől folytatódik. Minderről további olvasnivalót találhat itt és a itt.
A Tate-párosítás módosított változatának, az úgynevezett optimális Ate-párosításnak a megvalósításához, lásd itt. A kód megvalósítja Miller algoritmusa, amely a �� tényleges kiszámításához szükséges.
Megjegyzendő, hogy az ilyen párosítások lehetséges ténye némileg vegyes áldás: egyrészt azt jelenti, hogy minden protokoll, amit a párosítással elvégezhetünk, lehetővé válik, de azt is jelenti, hogy jobban kell figyelnünk, milyen elliptikus görbék. használjuk.
Minden elliptikus görbének van egy an értéke beágyazottsági fok; lényegében a legkisebb �, amelyben ��−1 a � többszöröse (ahol � a mezőhöz használt prímszám, és � a görbe sorrendje). A fenti mezőkben, �=12, és a hagyományos ECC-hez használt mezőkben (azaz ahol nem törődünk a párosításokkal), a beágyazás mértéke gyakran rendkívül nagy, egészen addig a pontig, hogy a párosításokat számításilag lehetetlen kiszámítani; de ha nem vagyunk óvatosak, akkor generálhatunk olyan mezőket, ahol �=4 vagy akár 1 is.
Ha �=1, akkor az elliptikus görbékre vonatkozó „diszkrét logaritmus” probléma (lényegében helyreállítva � csak a pontot �=�⋅�, azt a problémát, amelyet meg kell oldanunk egy elliptikus görbe privát kulcsának „feltöréséhez” egy hasonló matematikai feladatba a �� felett, ahol a feladat sokkal könnyebbé válik (ez az úgynevezett MOV támadás); A 12-es vagy magasabb beágyazási fokozatú görbék használata biztosítja, hogy ez a csökkentés vagy ne legyen elérhető, vagy hogy a párosítási eredményekhez kapcsolódó diszkrét naplóprobléma megoldása legalább olyan nehéz, mint a privát kulcs helyreállítása nyilvános kulcsból „a szokásos módon” (pl. számításilag kivitelezhetetlen). Ne aggódj; az összes standard görbe paramétert alaposan ellenőrizték erre a problémára.
Maradjon velünk a hamarosan megjelenő matematikai magyarázatért a zk-SNARK működéséről.
Külön köszönet Christian Reitwiessnernek, Ariel Gabizonnak (a Zcash-tól) és Alfred Menezesnek az áttekintésért és a javítások elvégzéséért.
- SEO által támogatott tartalom és PR terjesztés. Erősödjön még ma.
- PlatoData.Network Vertical Generative Ai. Erősítse meg magát. Hozzáférés itt.
- PlatoAiStream. Web3 Intelligence. Felerősített tudás. Hozzáférés itt.
- PlatoESG. Carbon, CleanTech, Energia, Környezet, Nap, Hulladékgazdálkodás. Hozzáférés itt.
- PlatoHealth. Biotechnológiai és klinikai vizsgálatok intelligencia. Hozzáférés itt.
- BlockOffsets. A környezetvédelmi ellentételezési tulajdon korszerűsítése. Hozzáférés itt.
- Forrás: Platón adatintelligencia.