Tere Habr!
В Käesolevas artiklis arutlesime, miks võib osutuda vajalikuks juhuslike arvude genereerimine osalejatele, kes üksteist ei usalda, millised nõuded esitatakse sellistele juhuslike numbrite generaatoritele ja kaalusime kahte lähenemisviisi nende rakendamiseks.
Artikli selles osas vaatleme lähemalt teist lähenemist, mis kasutab läve allkirju.
Natuke krüptograafiat
Selleks, et mõista, kuidas läviallkirjad töötavad, peate mõistma veidi põhilist krüptograafiat. Kasutame kahte mõistet: skalaarid või lihtsalt numbrid, mida tähistame väiketähtedega (x, y) ja elliptilise kõvera punktid, mida tähistame suurtähtedega.
Lävesignatuuride põhitõdede mõistmiseks ei pea te mõistma elliptiliste kõverate toimimist, välja arvatud mõned põhilised asjad.
-
Elliptilise kõvera punkte saab liita ja korrutada skalaariga (skalaariga korrutamist tähistame kui xG, kuigi märge Gx kasutatakse sageli ka kirjanduses). Skalaariga liitmise ja korrutamise tulemus on punkt elliptilisel kõveral.
-
Teades ainult asja mõtet G ja selle korrutis skalaariga xG ei saa arvutada x.
Kasutame ka polünoomi mõistet p(x) kraadi k-1. Eelkõige kasutame polünoomide järgmist omadust: kui teame väärtust p(x) iga k erinev x (ja meil pole selle kohta rohkem teavet p(x)), saame arvutada p(x) kellegi teise jaoks x.
Huvitav on see, et iga polünoomi puhul p(x) ja mingi punkt kõveral Gtähenduse teadmine p(x)G iga k erinevaid tähendusi x, saame ka arvutada p(x)G iga x.
See on piisav teave lävesignatuuride toimimise ja nende kasutamise kohta juhuslike arvude genereerimiseks.
Juhuslike arvude generaator lävesignatuuridel
Ütleme nii n osalejad tahavad luua juhusliku arvu ja me tahame, et kõik osaleksid k neid oli piisavalt, et tekitada number, aga nii et ründajad, kes kontrollivad k-1 või vähem osalejat ei suutnud genereeritud arvu ennustada ega mõjutada.
Oletame, et on olemas selline polünoom p(x) kraadi k-1, mida esimene osaleja teab p (1), teab teine p(2), ja nii edasi (n- teab p(n)). Samuti eeldame, et mingi etteantud punkti puhul G igaüks teab p(x)G kõigi väärtuste jaoks x. Me helistame p(i) "erakomponent" iosaleja (sest ainult iosaleja tunneb teda) ja p(i)G "avalik komponent" i-th osaleja (sest kõik osalejad teavad teda). Nagu mäletate, teadmised p(i)G taastamiseks ei piisa p(i).
Sellise polünoomi loomine nii, et ainult i-Esimene osaleja ja keegi teine ei teadnud tema privaatkomponenti - see on protokolli kõige keerulisem ja huvitavam osa ning me analüüsime seda allpool. Oletame praegu, et meil on selline polünoom ja kõik osalejad teavad oma privaatseid komponente.
Kuidas saame sellist polünoomi kasutada juhusliku arvu genereerimiseks? Alustuseks vajame stringi, mida pole varem generaatori sisendiks kasutatud. Plokiahela puhul viimase ploki räsi h on hea kandidaat sellisele liinile. Laske osalejatel luua juhuslik arv kasutades h nagu seeme. Osalejad konverteerivad kõigepealt h kõvera punktini, kasutades mis tahes eelmääratletud funktsiooni:
H = skalaarpunktini (h)
Siis iga osaleja i arvutab ja avaldab Hi = p(i)H, mida nad saavad teha, sest nad teavad p(i) ja H. Avalikustamine Hma ei luba teistel osalejatel privaatkomponenti taastada iosaleja ja seetõttu saab plokist plokki kasutada ühte privaatkomponentide komplekti. Seega tuleb allpool kirjeldatud kallist polünoomi genereerimise algoritmi täita vaid üks kord.
Millal k osalejatele tehti lahkamine Hi = p(i)H, igaüks oskab arvutada Hx = p(x)H kõigi jaoks x tänu polünoomide omadusele, mida arutasime viimases osas. Praegu arvutavad kõik osalejad H0 = p(0)H, ja see on saadud juhuslik arv. Pange tähele, et keegi ei tea p(0), ja seega ainus viis arvutada p(0)H – see on interpolatsioon p(x)H, mis on võimalik ainult siis, kui k väärtused p(i)H teatud. Iga väiksema koguse avamine p(i)H kohta ei anna mingit infot p(0)H.
Ülaltoodud generaatoril on kõik omadused, mida me tahame: ainult ründajad kontrollivad k-Ühel või vähemal osalejal puudub teave ega mõju järeldusele, samas kui see on k osalejad saavad arvutada saadud arvu ja selle mis tahes alamhulga k osalejad jõuavad sama seemne puhul alati sama tulemuseni.
On üks probleem, mida me eespool hoolikalt vältisime. Interpolatsiooni toimimiseks on oluline, et väärtus Hi, mille iga osaleja avaldas i see oli tõesti sama p(i)H. Kuna mitte keegi peale i-th osaleja ei tea p(i), mitte keegi peale i-osaleja ei saa seda kontrollida Hi tegelikult arvutatud õigesti ja ilma krüptograafilise õigsuse tõendita Hi ründaja võib avaldada mis tahes väärtuse kui Tere, ja suvaliselt mõjutada juhuslike arvude generaatori väljundit:
Esimese osaleja saadetud H_1 erinevad väärtused viivad erineva tulemuseni H_0
Õigsuse tõestamiseks on vähemalt kaks võimalust Hi, käsitleme neid pärast polünoomi genereerimise analüüsimist.
Polünoomide põlvkond
Viimases osas eeldasime, et meil on selline polünoom p(x) kraadi k-1 et osaleja i teab p(i), ja kellelgi teisel pole selle väärtuse kohta teavet. Järgmises jaotises vajame seda ka mõne etteantud punkti jaoks G kõik teadsid p(x)G kõigi jaoks x.
Selles jaotises eeldame, et igal osalejal on kohalik privaatvõti xi, nii, et kõik teavad vastavat avalikku võtit Xi.
Üks võimalik polünoomi genereerimise protokoll on järgmine:
-
Iga osaleja i loob lokaalselt suvalise polünoomi pi(x) aste k-1. Seejärel saadavad nad iga osaleja j väärtus pi(j), krüpteeritud avaliku võtmega Xj. Seega ainult i-th и j-th osaleja teab pi(j). Osaleja i teatab ka avalikult pi(j)G kõigi jaoks j pärit 1 kuni k kaasa arvatud.
-
Kõik osalejad kasutavad valimisel teatud konsensust k osalejad, kelle polünoome kasutatakse. Kuna mõned osalejad võivad olla võrguühenduseta, ei saa me oodata, kuni kõik n osalejad avaldavad polünoomid. Selle sammu tulemuseks on komplekt Z mis koosneb vähemalt k etapis (1) loodud polünoomid.
-
Osalejad veenduvad, et väärtusi nad tunnevad pi(j) vastavad avalikult väljakuulutatule pi(j)G. Pärast seda sammu Z ainult polünoomid, mille puhul edastatakse eraviisiliselt pi(j) vastavad avalikult väljakuulutatule pi(j)G.
-
Iga osaleja j arvutab selle privaatkomponendi p(j) summana pi(j) kõigi jaoks i в Z. Iga osaleja arvutab ka kõik väärtused p(x)G summana pi(x)G kõigi i jaoks в Z.
Pange tähele, et p(x) – see on tõesti polünoom k-1, sest see on indiviidi summa pi(x), millest igaüks on astme polünoom k-1. Seejärel pange tähele, et kuigi iga osaleja j teab p(j), kohta neil infot pole p(x) eest x ≠ j. Tõepoolest, selle väärtuse arvutamiseks peavad nad kõike teadma pi(x), ja nii kaua kui osaleja j ei tea vähemalt ühte valitud polünoomidest, neil pole selle kohta piisavalt teavet p(x).
See on kogu polünoomi genereerimise protsess, mida oli vaja viimases jaotises. Ülaltoodud 1., 2. ja 4. sammude teostus on üsna ilmne. Kuid samm 3 pole nii triviaalne.
Täpsemalt peame suutma tõestada, et see on krüpteeritud pi(j) vastavad tõesti avaldatutele pi(j)G. Kui me ei suuda seda tõestada, siis ründaja i võib hoopis prügi saata pi(j) osalejale j, ja osaleja j ei suuda saada tegelikku tähendust pi(j), ja ei saa selle privaatkomponenti arvutada.
On olemas krüptograafiline protokoll, mis võimaldab teil luua täiendava sõnumi tõendi(j), nii et mis tahes osaleja, kellel on mingi väärtus e, samuti tõend(j) и pi(j)G, saab seda kohapeal kontrollida e - see on tõesti pi(j), krüptitud osaleja võtmega j. Kahjuks on selliste tõendite maht uskumatult suur ja arvestades, et see on vajalik avaldada O (nk) Selliseid tõendeid ei saa sel eesmärgil kasutada.
Selle asemel, et seda tõestada pi(j) vastab pi(j)G saame polünoomi genereerimise protokollis eraldada väga suure aja, mille jooksul kõik osalejad kontrollivad vastuvõetud krüpteeritud pi(j), ja kui dekrüpteeritud sõnum ei vasta avalikkusele pi(j)G, avaldavad nad krüptograafilise tõendi selle kohta, et saadud krüpteeritud sõnum on vale. Tõesta, et sõnum ei vastab pi(G) palju lihtsam kui tõestada, et see sobib. Tuleb märkida, et see eeldab, et iga osaleja peab esinema veebis vähemalt korra selliste tõendite loomiseks määratud aja jooksul ja tugineb eeldusele, et kui nad sellise tõendi avaldavad, jõuavad need sama määratud aja jooksul kõigi teiste osalejateni.
Kui osaleja ei ilmunud selle aja jooksul võrku ja tal oli vähemalt üks vale komponent, siis see konkreetne osaleja ei saa enam numbrite genereerimisel osaleda. Protokoll töötab siiski, kui see on vähemalt olemas k osalejad, kes said äsja õiged komponendid või suutsid ettenähtud aja jooksul jätta tõendi ebakorrektsuse kohta.
H_i õigsuse tõendid
Viimane osa, mida tuleb arutada, on see, kuidas tõestada avaldamise õigsust Hmina, nimelt see Hi = p(i)H, avamata p(i).
Pidagem meeles, et väärtused H, G, p(i)G avalik ja kõigile teada. Vastuvõtmise operatsioon p(i) teades p(i)G и G nimetatakse diskreetseks logaritmiks või dlog, ja me tahame tõestada, et:
dlog(p(i)G, G) = dlog(Hi, H)
ilma avalikustamiseta p(i). Selliste tõestuste jaoks on olemas näiteks konstruktsioonid.
Selle kujundusega on iga osaleja koos Hi saadab projektijärgse õigsuse tõendi.
Kui juhuslik arv on genereeritud, peavad seda sageli kasutama teised osalejad kui need, kes selle genereerisid. Sellised osalejad peavad koos numbriga saatma kõik Hi ja sellega seotud tõendid.
Uudishimulik lugeja võib küsida: kuna lõplik juhuslik arv on H0 ja p(0)G – See on avalik teave, miks me vajame iga inimese kohta tõendeid Hi, miks mitte saata selle asemel tõend
dlog(p(0)G, G) = dlog(H0, H)
Probleem on selles, et sellist tõendit ei saa Schnorri protokolli kasutades luua, sest keegi ei tea selle väärtust p (0), mis on vajalik tõestuse loomiseks, ja veelgi enam, kogu juhuslike arvude generaator põhineb sellel, et keegi ei tea seda väärtust. Seetõttu on vaja kõiki väärtusi Hi ja nende individuaalsed tõendid õigsuse tõendamiseks H0.
Kui aga elliptiliste kõverate punktidega tehti mõni tehe, mis on semantiliselt sarnane korrutamisega, on õigsuse tõend H0 oleks triviaalne, me lihtsalt veenduksime selles
H0 x G = p(0)G × H
Kui valitud kõver toetab , see tõestus töötab. Sel juhul H0 ei ole ainult juhuslike arvude generaatori väljund, mida saab kontrollida iga asjatundja G, H и p(0)G. H0 on ka allkiri sõnumil, mida kasutati seemnena, mis kinnitab seda k и n osalejad kirjutasid sellele sõnumile alla. Seega, kui seeme - on ploki räsi plokiahela protokollis, siis H0 on nii mitme signatuur plokil kui ka väga hea juhuslik arv.
Kokkuvõttes
See artikkel on osa tehnilisest ajaveebi seeriast . NEAR on plokiahela protokoll ja platvorm detsentraliseeritud rakenduste arendamiseks, rõhuasetusega arendamise lihtsusele ja kasutusmugavusele lõppkasutajate jaoks.
Protokollikood on avatud, meie teostus on kirjutatud Rustis, see on leitav .
Saate vaadata, kuidas NEAR-i arendus välja näeb, ja katsetada veebipõhises IDE-s .
Kõiki uudiseid saate jälgida vene keeles aadressil ja , ja inglise keeles ametlikus .
Varsti näeme!
Allikas: www.habr.com