Vitalik Buterin kautta Vitalik Buterin blogi
Tämä on peili postista osoitteessa https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
Liipaisuvaroitus: matemaattinen.
Yksi tärkeimmistä salausprimitiiveistä eri rakenteiden takana, mukaan lukien deterministiset kynnysallekirjoitukset, zk-SNARKit ja muut yksinkertaisemmat nollatietotodisteet, on elliptisen käyrän pariliitos. Elliptisten käyrien pariliitokset (tai "bilineaariset kartat") ovat uusi lisäys 30 vuoden mittaiseen elliptisten käyrien käytön historiaan kryptografisissa sovelluksissa, mukaan lukien salaus ja digitaaliset allekirjoitukset. pariliitokset esittelevät eräänlaisen "salatun kertolaskun", mikä laajentaa huomattavasti elliptiseen käyrään perustuvien protokollien mahdollisuuksia. Tämän artikkelin tarkoituksena on perehtyä elliptisten käyrien pariliitoksiin yksityiskohtaisesti ja selittää niiden toiminta.
Sinun ei odoteta ymmärtävän kaikkea, kun luet sen ensimmäisen kerran tai edes kymmenennellä kerralla; nämä asiat ovat todella vaikeita. Mutta toivottavasti tämä artikkeli antaa sinulle ainakin jonkinlaisen käsityksen siitä, mitä konepellin alla tapahtuu.
Elliptiset käyrät itsessään ovat hyvin ei-triviaali aihe, joka on ymmärrettävä, ja tässä artikkelissa oletetaan yleensä, että tiedät kuinka ne toimivat. Jos et, suosittelen tätä artikkelia tässä alukkeena: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/. Lyhyesti voidaan todeta, että elliptisen käyrän salakirjoitus sisältää matemaattisia objekteja, joita kutsutaan "pisteiksi" (nämä ovat kirjaimellisia kaksiulotteisia pisteitä, joissa on (�,�)-koordinaatit), erityisillä kaavoilla niiden lisäämiseksi ja vähentämiseksi (eli �=:n koordinaattien laskemiseksi). �+�), ja voit myös kertoa pisteen kokonaisluvulla (eli �⋅�=�+�+…+�, vaikka se on paljon nopeampikin laskea, jos � on iso).
Tältä pisteen lisääminen näyttää graafisesti.
On olemassa erityinen piste, jota kutsutaan "pisteeksi äärettömyydessä" (�), joka vastaa nollaa pistearitmetiikassa; se on aina niin �+�=�. Käyrällä on myös "tilata"; on olemassa luku �, joka �⋅�=� mille tahansa �lle (ja tietysti �⋅(�+1)=�,�⋅(7⋅�+5)=�⋅5 ja niin edelleen). On myös jokin yleisesti sovittu "generaattoripiste" �, jonka ymmärretään jossain mielessä edustavan numeroa 1. Teoriassa mikä tahansa käyrän piste (paitsi �) voi olla �; Tärkeintä on, että � on standardoitu.
Pariliitokset menevät askeleen pidemmälle, sillä niiden avulla voit tarkistaa tietynlaisia monimutkaisempia yhtälöitä elliptisen käyrän pisteissä – esimerkiksi jos �=�⋅�,�=�⋅� ja �=�⋅�, voit tarkistaa, onko tai ei �⋅�=�, vain �,� ja � syötteinä. Tämä saattaa tuntua siltä, että elliptisten käyrien perusturvatakuut ovat murtumassa, sillä tietoa �sta vuotaa pelkästään P:n tiedosta, mutta käy ilmi, että vuoto on hyvin hillitty – erityisesti päätöksenteko Diffie Hellman -ongelma on helppoa, mutta laskennallinen Diffie Hellman -ongelma (tietäen � ja � yllä olevassa esimerkissä, tietojenkäsittely �=�⋅�⋅�) ja diskreetti logaritmiongelma (palautuvat � alkaen �) jäävät laskennallisesti mahdottomaksi (ainakin, jos ne olivat ennen).
Kolmas tapa tarkastella, mitä pariliitokset tekevät, ja yksi, joka on ehkä valaisevin useimmissa tarkastelemissamme käyttötapauksissa, on se, että jos tarkastelet elliptisiä käyräpisteitä yksisuuntaisina salattuina numeroina (eli ���� ���(�)=�⋅�=�), kun taas perinteinen elliptisen käyrän matematiikka antaa sinun tarkistaa lineaarinen lukujen rajoitukset (esim. jos �=�⋅�,�=�⋅� ja �=�⋅�, tarkistus 5⋅�+7⋅�=11⋅� on ihan oikeesti tarkistamalla, että 5⋅�+7⋅�=11⋅�), pariliitokset antavat sinun tarkistaa neliömäinen rajoitukset (esim. tarkistus �(�,�)⋅�(�,�⋅5)=1 on ihan oikeesti tarkistamalla, että �⋅�+5=0). Ja neliön asteikkoon siirtyminen riittää, jotta voimme työskennellä determinististen kynnystunnusten, asteen aritmeettisten ohjelmien ja kaiken muun hyvän kanssa.
Mikä nyt on tämä hauska �(�,�)-operaattori, jonka esittelimme yllä? Tämä on pariliitos. Matemaatikot kutsuvat sitä joskus myös a bilineaarinen kartta; sana "bilineaarinen" tarkoittaa tässä periaatteessa, että se täyttää rajoitukset:
�(�,�+�)=�(�,�)⋅�(�,�)
�(�+�,�)=�(�,�)⋅�(�,�)
Huomaa, että + ja ⋅ voivat olla mielivaltaisia operaattoreita; kun luot upeita uudenlaisia matemaattisia objekteja, abstrakti algebra ei välitä kuinka + ja ⋅ ovat määritelty, kunhan ne ovat yhdenmukaisia tavallisilla tavoilla, esim. �+�=�+�,(�⋅�)⋅�=�⋅(�⋅�) ja (�⋅�)+(�⋅�)=(�+�)⋅�.
Jos �, �, � ja � olisivat yksinkertaisia numerot, niin yksinkertaisen parin muodostaminen on helppoa: voimme tehdä �(�,�)=2��. Sitten voimme nähdä:
�(3,4+5)=23⋅9=227
�(3,4)⋅�(3,5)=23⋅4⋅23⋅5=212⋅215=227
Se on bilineaarinen!
Tällaiset yksinkertaiset pariliitokset eivät kuitenkaan sovellu kryptografiaan, koska objektit, joita ne käsittelevät, ovat yksinkertaisia kokonaislukuja ja niitä on liian helppo analysoida. kokonaislukujen avulla on helppo jakaa, laskea logaritmeja ja tehdä monia muita laskutoimituksia; yksinkertaisilla kokonaisluvuilla ei ole käsitettä "julkinen avaime" tai "yksisuuntainen funktio". Lisäksi edellä kuvatun pariliitoksen avulla voit siirtyä taaksepäin – tietäen � ja tietäen �(�,�), voit yksinkertaisesti laskea jaon ja logaritmin määrittääksesi �. Haluamme matemaattisia objekteja, jotka ovat mahdollisimman lähellä "mustia laatikoita", joissa voit lisätä, vähentää, kertoa ja jakaa, mutta älä tee muuta. Tässä tulevat käyttöön elliptiset käyrät ja elliptisten käyrien parit.
Osoittautuu, että on mahdollista tehdä bilineaarinen kartta elliptisten käyräpisteiden yli – eli keksiä funktio �(�,�), jossa tulot � ja � ovat elliptisiä käyräpisteitä ja jossa lähtö on ns. (��)12-elementti (ainakin tässä tarkasteltavassa tapauksessa; yksityiskohdat vaihtelevat käyrän yksityiskohdista riippuen, lisää tästä myöhemmin), mutta sen taustalla oleva matematiikka on melko monimutkaista.
Ensin katetaan ensiluokkaiset kentät ja laajennuskentät. Aikaisemmin tässä viestissä oleva melko elliptinen käyrä näyttää tältä vain, jos oletetaan, että käyräyhtälö on määritelty käyttämällä tavallisia reaalilukuja. Kuitenkin, jos käytämme salauksessa tavallisia reaalilukuja, voit käyttää logaritmeja "palataksesi taaksepäin", ja kaikki katkeaa; lisäksi numeroiden tallentamiseen ja esittämiseen tarvittavan tilan määrä voi kasvaa mielivaltaisesti. Siksi käytämme sen sijaan numeroita a:ssa pääkenttä.
Alkukenttä koostuu joukosta lukuja 0,1,2…�−1, jossa � on alkuluku, ja eri operaatiot määritellään seuraavasti:
�+�:(�+�) % �
�⋅�:(�⋅�) % �
�−�:(�−�) % �
�/�:(�⋅��−2) % �
Periaatteessa kaikki matematiikka tehdään modulo � (katso tätä johdannosta modulaariseen matematiikkaan). Jako on erikoistapaus; normaalisti 32 ei ole kokonaisluku, ja tässä halutaan käsitellä vain kokonaislukuja, joten yritämme sen sijaan löytää luvun � siten, että �⋅2=3, missä ⋅ tietysti viittaa modulaariseen kertolaskuun, kuten edellä on määritelty. Kiitokset Fermatin pieni lause, yllä näkyvä eksponentiotemppu tekee tehtävänsä, mutta on myös nopeampi tapa tehdä se käyttämällä Laajennettu euklidinen algoritmi. Oletetaan �=7; tässä muutama esimerkki:
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
Jos pelaat tämänkaltaisella matematiikalla, huomaat, että se on täysin johdonmukainen ja täyttää kaikki tavalliset säännöt. Kaksi viimeistä esimerkkiä yllä osoittavat, kuinka (�/�)⋅�=�; voit myös nähdä, että (�+�)+�=�+(�+�),(�+�)⋅�=�⋅�+�⋅� ja kaikki muut tuntemasi ja rakastamasi lukion algebralliset identiteetit jatkuvat pitää myös paikkansa. Todellisuudessa elliptisissa käyrissä pisteet ja yhtälöt lasketaan yleensä alkukentissä.
Nyt puhutaan laajennuskenttiä. Olet todennäköisesti jo nähnyt laajennuskentän aiemmin; yleisin matematiikan oppikirjoissa kohtaamasi esimerkki on kompleksilukujen kenttä, jossa reaalilukujen kenttä on "laajennettu" lisäelementillä −1=�. Pohjimmiltaan laajennuskentät toimivat ottamalla olemassa oleva kenttä, "keksimällä" sitten uuden elementin ja määrittämällä kyseisen elementin ja olemassa olevien elementtien välisen suhteen (tässä tapauksessa �2+1=0) varmistaen, että tämä yhtälö ei pidä paikkaansa. mille tahansa numerolle, joka on alkuperäisessä kentässä, ja tarkastellaan alkuperäisen kentän ja juuri luomasi uuden elementin kaikkien lineaaristen yhdistelmien joukkoa.
Voimme tehdä myös prime-kenttien laajennuksia; Voimme esimerkiksi laajentaa alkukenttää mod7, jota kuvailimme yllä �:lla, ja sitten voimme tehdä:
(2+3�)+(4+2�)=6+5�
(5+2�)+3=1+2�
(6+2�)⋅2=5+4�
4�⋅(2+�)=3+�
Tämä viimeinen tulos voi olla hieman vaikea selvittää; siellä tapahtui niin, että jaoimme tuotteen ensin 4�⋅2+4�⋅�, mikä antaa 8�−4, ja sitten koska työskentelemme mod7-matematiikalla, josta tulee �+3. Jakamiseksi teemme:
�/�:(�⋅�(�2−2)) % �
Huomaa, että Fermatin pienen lauseen eksponentti on nyt �2 �:n sijaan, vaikka jälleen kerran, jos haluamme olla tehokkaampia, voimme sen sijaan laajentaa laajennettua euklidista algoritmia suorittamaan työn. Huomaa, että ��2-1=1 mille tahansa �lle tässä kentässä, joten kutsumme �2-1:tä "kentän kertovan ryhmän järjestykseksi".
Tosilukujen kanssa Algebran peruslause varmistaa, että neliöllinen laajennus, jota kutsumme kompleksiluvuiksi, on "täydellinen" - et voi laajentaa sitä enempää, koska minkä tahansa matemaattisen suhteen (ainakin algebrallisen kaavan määrittämän matemaattisen suhteen), jonka voit keksiä jonkin uuden elementin välillä � ja olemassa olevat kompleksiluvut, on mahdollista keksiä ainakin yksi kompleksiluku, joka jo täyttää tämän suhteen. Alkukenttien kanssa meillä ei kuitenkaan ole tätä ongelmaa, joten voimme mennä pidemmälle ja tehdä kuutiolaajennuksia (jossa jonkin uuden elementin � ja olemassa olevien kenttäelementtien välinen matemaattinen suhde on kuutioyhtälö, joten 1,� ja �2 ovat kaikki lineaarisesti toisistaan riippumattomat), korkeamman asteen laajennukset, laajennusten laajennukset jne. Ja juuri tämän tyyppisten supercharged modulaaristen kompleksilukujen varaan elliptisten käyrien parit rakentuvat.
Niille, jotka ovat kiinnostuneita näkemään tarkan matematiikan, joka liittyy kaikkien näiden toimintojen kirjoittamiseen koodiin, prime kentät ja kenttälaajennukset on toteutettu täällä: https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py
Nyt elliptisten käyrien pariliitoksiin. Elliptisen käyrän pariliitos (tai pikemminkin erityinen pariliitoksen muoto, jota tarkastelemme tässä; on myös muita pariliitoksia, vaikka niiden logiikka on melko samanlainen) on kartta �2×�1→��, jossa:
- �1 on elliptinen käyrä, jossa pisteet täyttävät yhtälön muodossa �2=�3+� ja jossa molemmat koordinaatit ovat ��:n elementtejä (eli ne ovat yksinkertaisia lukuja, paitsi että aritmetiikka tehdään modulo jollakin alkuluvulla)
- �2 on elliptinen käyrä, jossa pisteet täyttävät saman yhtälön kuin �1, paitsi missä koordinaatit ovat (��)12:n elementtejä (eli ne ovat supervarattuja kompleksilukuja, joista puhuimme edellä; määrittelemme uuden "maagisen luvun". ” �, joka määritellään 12. asteen polynomilla, kuten �12−18⋅�6+82=0)
- �� on objektityyppi, johon elliptisen käyrän tulos menee. Käyrissä, joita tarkastelemme, �� on (��)12 (sama ahdettu kompleksiluku kuin �2:ssa)
Pääominaisuus, joka sen on täytettävä, on bilineaarisuus, mikä tässä yhteydessä tarkoittaa, että:
- �(�,�+�)=�(�,�)⋅�(�,�)
- �(�+�,�)=�(�,�)⋅�(�,�)
On olemassa kaksi muuta tärkeää kriteeriä:
- Tehokas laskettavuus (esim. voimme tehdä helpon pariliitoksen yksinkertaisesti ottamalla kaikkien pisteiden diskreetit logaritmit ja kertomalla ne yhteen, mutta tämä on laskennallisesti yhtä vaikeaa kuin elliptisen käyrän kryptografian rikkominen, joten sitä ei lasketa)
- Ei-degeneraatio (tottakai, voisit vain määritellä �(�,�)=1, mutta se ei ole erityisen hyödyllinen pariliitos)
Joten miten teemme tämän?
Pariliitosfunktioiden toiminnan taustalla oleva matematiikka on melko hankalaa ja sisältää melko paljon kehittynyttä algebraa, joka menee jopa pidemmälle kuin olemme tähän mennessä nähneet, mutta annan yleiskuvan. Ensinnäkin meidän on määriteltävä käsite a jakaja, periaatteessa vaihtoehtoinen tapa esittää funktioita elliptisen käyrän pisteissä. Funktion jakaja laskee periaatteessa funktion nollat ja äärettömät. Katsotaanpa muutamia esimerkkejä nähdäksesi, mitä tämä tarkoittaa. Korjataan jokin kohta �=(��,��) ja harkitaan seuraavaa funktiota:
�(�,�)=�−��
Jakaja on [�]+[−�]−2⋅[�] (hakasulkuja käytetään kuvaamaan sitä tosiasiaa, että tarkoitamme pisteen � läsnäolo funktion nollien ja äärettömyyden joukossa, ei itse piste P; [�]+[�] on emme sama asia kuin [�+�]). Perustelut ovat seuraavat:
- Funktio on yhtä suuri kuin nolla kohdassa �, koska � is ��, joten �−��=0
- Funktio on yhtä kuin nolla kohdassa −�, koska −� ja � jakavat saman �-koordinaatin
- Funktio menee äärettömään kuten � menee äärettömyyteen, joten sanomme, että funktio on yhtä kuin ääretön kohdassa �. On tekninen syy, miksi tämä ääretön on laskettava kahdesti, joten � lisätään "kertoimella" −2 (negatiivinen, koska se on ääretön eikä nolla, kaksi tämän kaksoislaskennan vuoksi).
Tekninen syy on suunnilleen tämä: koska käyrän yhtälö on �3=�2+�,� menee äärettömään "1.5 kertaa nopeammin" kuin �, jotta �2 pysyisi �3:n perässä; Näin ollen, jos lineaarinen funktio sisältää vain �, se esitetään kerrannaisuuden 2 äärettömänä, mutta jos se sisältää �, se esitetään monikertaisuuden 3 äärettömänä.
Harkitse nyt "viivafunktiota":
��+��+�=0
Missä �, � ja � on valittu huolellisesti niin, että viiva kulkee pisteiden � ja � kautta. Koska elliptisen käyrän yhteenlasku toimii (katso kaavio yläosassa), tämä tarkoittaa myös, että se kulkee −�−�:n läpi. Ja se nousee äärettömyyteen riippuen sekä �:stä että �sta, joten jakajasta tulee [�]+[�]+[−�−�]−3⋅[�].
Tiedämme, että jokainen "rationaalinen funktio" (eli funktio, joka on määritetty käyttämällä vain äärellistä lukua +,−,⋅ ja / operaatioita pisteen koordinaateille) vastaa yksiselitteisesti jotain jakajaa vakiolla kertomiseen asti (esim. jos kahdella funktiolla � ja � on sama jakaja, niin �=�⋅� jollekin vakiolle �).
Minkä tahansa kahden funktion � ja � jakaja �⋅� on yhtä suuri kuin funktion � jakaja plus funktion � jakaja (matematiikan oppikirjoissa näet (�⋅�)=(�)+(�)), joten esimerkiksi jos �(�,�)=��−�, niin (�3)=3⋅[�]+3⋅[−�]−6⋅[�]; � ja −� on "kolminkertaistettu" sen tosiasian vuoksi, että �3 lähestyy nollaa näissä pisteissä "kolme kertaa niin nopeasti" tietyssä matemaattisessa mielessä.
Huomaa, että on olemassa lause, joka sanoo, että jos "poistat hakasulkeet" funktion jakajasta, pisteiden summan tulee olla �([�]+[�]+[−�−�]−3⋅[ �] sopii selvästi, kuten �+�−�−�−3⋅�=�), ja mikä tahansa jakaja, jolla on tämä ominaisuus, on funktion jakaja.
Nyt olemme valmiita tarkastelemaan Tate-pareja. Tarkastellaan seuraavia toimintoja, jotka on määritelty niiden jakajien kautta:
- (��)=�⋅[�]−�⋅[�], missä � on �1:n kertaluku, eli. �⋅�=� mille tahansa �lle
- (��)=�⋅[�]−�⋅[�]
- (�)=[�+�]−[�]−[�]+[�]
Katsotaanpa nyt tuotetta ��⋅��⋅��. Jakaja on:
�⋅[�]−�⋅[�]+�⋅[�]−�⋅[�]+�⋅[�+�]−�⋅[�]−�⋅[�]+�]⋅[�]
Mikä yksinkertaistaa siististi:
�⋅[�+�]−�⋅[�]
Huomaa, että tämä jakaja on täsmälleen samaa muotoa kuin jakaja �� ja �� yllä. Siksi ��⋅��⋅��=��+�.
Nyt otamme käyttöön menettelyn, jota kutsutaan "lopulliseksi eksponentioimiseksi", jossa otamme yllä olevien funktioidemme tuloksen (��,�� jne.) ja nostamme sen potenssiin �=(�12−1)/�, missä �12−1 on kertovan ryhmän järjestys (��)12:ssa (eli Kaikki �∈(��)12,�(�12−1)=1). Huomaa, että jos käytät tätä eksponentiota mihin tahansa tulokseen, jolla on jo korotettu potenssiin �, saat eksponentioarvon �12−1, joten tuloksesta tulee 1. Näin ollen lopullisen eksponentioinnin jälkeen �� kumoutuu ja saamme ���⋅���=( ��+�)�. Sinussa on jonkin verran bilineaarisuutta.
Jos nyt haluat tehdä funktion, joka on bilineaarinen molemmissa argumenteissa, sinun on mentävä pelottavampaan matematiikkaan, jossa sen sijaan, että otat arvon suoraan, otat �� jakaja, ja sieltä koko "Tate-parisuhde" tulee. Saadaksesi lisää tuloksia, sinun on käsiteltävä sellaisia käsitteitä kuin "lineaarinen ekvivalenssi" ja "Weilin vastavuoroisuus", ja kaninreikä jatkuu sieltä. Löydät lisää luettavaa kaikesta tästä tätä ja tätä.
Tate-pariliitoksen muokatun version toteuttamiseksi, jota kutsutaan optimaaliseksi Ate-paritukseksi, katso tästä. Koodi toteuttaa Millerin algoritmi, jota tarvitaan tosiasiallisesti laskettaessa ��.
Huomaa, että se tosiasia, että tällaiset pariliitokset ovat mahdollisia, on hieman sekalainen siunaus: toisaalta se tarkoittaa, että kaikki protokollat, joita voimme tehdä pariliitoksilla, ovat mahdollisia, mutta se tarkoittaa myös sitä, että meidän on oltava varovaisempia elliptisten käyrien suhteen. käytämme.
Jokaisella elliptisellä käyrällä on arvo nimeltä an upotusaste; olennaisesti pienin � siten, että ��−1 on �:n kerrannainen (missä � on kentässä käytetty alkuluku ja � on käyrän järjestys). Yllä olevissa kentissä �=12 ja perinteisessä ECC:ssä käytetyissä kentissä (ts. joissa emme välitä pariliitoksista) upotusaste on usein äärimmäisen suuri, jopa siihen pisteeseen, että pariliitoksia on mahdotonta laskea; Mutta jos emme ole varovaisia, voimme luoda kenttiä, joissa �=4 tai jopa 1.
Jos � = 1, niin elliptisten käyrien "diskreetin logaritmin" ongelmaa (olennaisesti toipuminen � tietäen vain pisteen �=�⋅�, ongelma, joka sinun on ratkaistava elliptisen käyrän yksityisen avaimen "särkemiseksi") voidaan vähentää. samanlaiseen matemaattiseen ongelmaan ��, jossa tehtävästä tulee paljon helpompi (tätä kutsutaan MOV-hyökkäys); Käyttämällä käyriä, joiden upotusaste on 12 tai korkeampi, varmistetaan, että tämä vähennys ei ole käytettävissä tai että diskreetin lokiongelman ratkaiseminen pariliitostuloksista on vähintään yhtä vaikeaa kuin yksityisen avaimen palauttaminen julkisesta avaimesta "normaalilla tavalla" (ts. laskennallisesti mahdotonta). Älä huoli; kaikki vakiokäyrän parametrit on tarkistettu perusteellisesti tämän ongelman varalta.
Pysy kuulolla matemaattisten selitysten saamiseksi zk-SNARKien toiminnasta pian.
Erityiset kiitokset Christian Reitwiessnerille, Ariel Gabizonille (Zcashilta) ja Alfred Menezesille arvioinnista ja korjausten tekemisestä.
- SEO-pohjainen sisällön ja PR-jakelu. Vahvista jo tänään.
- PlatoData.Network Vertical Generatiivinen Ai. Vahvista itseäsi. Pääsy tästä.
- PlatoAiStream. Web3 Intelligence. Tietoa laajennettu. Pääsy tästä.
- PlatoESG. hiili, CleanTech, energia, ympäristö, Aurinko, Jätehuolto. Pääsy tästä.
- PlatonHealth. Biotekniikan ja kliinisten kokeiden älykkyys. Pääsy tästä.
- BlockOffsets. Ympäristövastuun omistuksen nykyaikaistaminen. Pääsy tästä.
- Lähde: Platon Data Intelligence.