Kas on võimalik genereerida juhuslikke numbreid, kui me üksteisele ei usalda? Osa 2

Tere, Habr!

Uues esimeses osas artiklites arutasime, miks võib olla vajalik genereerida juhuslikke numbreid osalistele, kes ei usalda üksteist, millised nõuded sellistele juhuslike numbrite generaatoritele esitatakse ning kaaluti kahte lähenemist nende rakendamiseks.

Selles artikli osas vaatleme üksikasjalikult veel ühte lähenemist, mis kasutab läve allkirju.

Veidi krüptograafia

Selleks, et mõista, kuidas läve allkirjad töötavad, on vajalik vähene arusaam põhilistest krüptograafia mõistetest. Kasutame kahte kontseptsiooni: skalaare ehk lihtsalt numbreid, mida tähistame väikeste tähtedega (x, y) ja punkte elliptilisel kõveral, mida tähistame suurte tähtedega.

Läve allkirjade põhialuste mõistmiseks ei pea üldse aru saama, kuidas elliptilised kõverad toimivad, välja arvatud mõned põhiasjad:

1. Elliptilise kõvera punkte saab liita ja skalaari külge korrutada (skalaari külge korrutamist tähistame kui xG, kuigi sümboolikat Gx kasutatakse ka tihti kirjanduses). Liitmise ja skalaari külge korrutamise tulemus on punkt elliptilisel kõveral.

2. Teades ainult punkti G ja selle korrutist skalaari xG ei saa arvestada x.

Kasutame samuti polünoomi kontseptsiooni p(x) kraadi k-1. Eelkõige kasutame järgmist polünoomide omadust: kui teame väärtust p(x) igaühe jaoks k erinev x (ja ei oma rohkem teavet p(x)), saame arvestada p(x) iga teisega x.

Huvitav on, et iga polünoomi p(x) ja mingi punkti kohta kõveral, teades väärtust Gp(x)G erinevate väärtuste igaühe jaoks k , on võimalik ka arvestada xigaga erinevate väärtuste Seda teavet on piisavalt, et süveneda üksikasjadesse, kuidas läve allkirjad töötavad ja kuidas neid kasutada juhuslike numbrite genereerimiseks. x.

Läve allkirjadega juhuslike numbrite generaator

Oletame, et

osalisi soovivad genereerida juhusliku numbri ja tahame, et ükskõik milline n neist oleks piisav numbri genereerimiseks, kuid et kurjategijad, kes kontrollivad k -1 või vähem osalisi, ei saaks ennustada või mõjutada genereeritud numbrit. kOletame, et eksisteerib selline polünoom

-1, et esimene osaline teab p(x) kraadi kp(1) , teine teabp(2), ja nii edasi ( -ndal on infonp(n) ). Oletame ka, et mingi eelnevalt määratletud punkti korralteavad kõik G kõigi väärtuste kohta erinevate väärtuste kõikide väärtuste jaoks x. Me nimetame p(i) „privaatseks komponendiks“ i-ndast osalisest (sest ainult i-ne osaline teab seda), ja p(i)G „avalikuks komponendiks“ i-ndast osalisest (sest kõik osalised teavad seda). Nagu te mäletate, teadmine p(i)G ei ole piisav, et taastada p(i).

Sellise polünoomi loomine, et ainult i--ne osaline ja keegi teine ei teaks oma privaatset komponenti – see on protokolli kõige keerulisem ja huvitavam osa, ja me käsitleme seda allpool. Oletame, et meil on selline polünoom, ja kõik osalised teavad oma privaatseid komponente.

Kuidas me saame kasutada sellist polünoomi, et genereerida juhuslik number? Esmalt vajame mingit stringi, mis pole varem sissepääsuks genereerijale kasutatud. Blokaadi puhul on eelmise blokki hash h — hea kandidaat selliseks stringiks. Oletame, et osalised tahavad luua juhuslikku numbrit, kasutades h kui seemet. Esmalt konverteerivad osalised h punktiks kõveral, kasutades mõnda eelnevalt määratud funktsiooni:

H = scalarToPoint(h)

Siis arvutab ja avaldab iga osaline i Hi = p(i)H, mida nad saavad teha, sest nad teavad p(i) ja H. i avamine ei võimalda teistel osalistel taastada privaatset komponenti -ndast osalisest, ja seetõttu saab sama privaatsete komponentide komplekti kasutada bloki kaupa. Seega tuleb allpool kirjeldatud kulukas polünoomi loomise algoritm teostada ainult üks kord. Hosalised avasid ikõik saavad arvutada

Kui k x = mida nad saavad teha, sest nad teavad p(x)H Hkõigi polünoomide omaduse tõttu, millest me eelnevas osas rääkisime. Sel hetkel arvutavad kõik osalised H0 = p(0)H, x ja see ongi tulemuslik juhuslik number. Pange tähele, et keegi ei tea p(0), ja seega on ainus viis arvutada p(0)H – see on interpolatsioon p(x)H, mida on võimalik teha ainult siis, kui väärtusi p(i)H k teatakse. Iga väiksema arvu avamine ei anna mingit teavet p(0)H-st. ei anna mingit teavet Ülaltoodud generaator omab kõiki omadusi, mida me soovime: kurjategijad, kes kontrollivad ainult k-

1 osalist või vähem, ei oma mingit teavet ega mõju väljundile, samal ajal kui igasugused osalised saavad arvutada tulemuslikku numbrit ning iga osaliste alamhulk jõuab alati sama tulemuse juurde sama seemne jaoks.1 osalejat või vähem ei oma mingit teavet ega mõju tulemusele, samas kui igasugused k osalejad saavad arvutada tulemuse ja iga alamhulk k osalejatest jõuab alati sama tulemus sama seemne jaoks.

On üks probleem, mida me eelnevalt ettevaatlikult vältisime. Et interpoleerimine toimiks, on oluline, et väärtus Hi, mille iga osaleja on avaldanud, i oleks tõeliselt võrdne p(i)H. Kuna keegi peale i-ndat osalejat ei tea p(i), ei saa keegi peale i--nda osaleja kontrollida, et Hi on tõeliselt õigesti arvutatud, ja ilma mingi krüptograafilise tõendi õiguse kohta, Hvõib kurjategija avaldada mistahes väärtuse kui Hi, ja suvaliselt mõjutada juhuslike numbrite generaatori väljundit.:

Erinevad H_1 väärtused, mida esimene osaleja saadab, toovad kaasa erinevad lõpp-H_0-d.

On vähemalt kaks viisi tõestada õigust Hi, neid käsitleme pärast polünoomi genereerimise arutamist.

Polünoomi genereerimine

Eelmisel lõigul eeldasime, et meil on selline polünoom p(x) kraadi k-1, et osaleja i kuidas seda teha. Ja seepärast käitub Google ühes suhtes väga targalt: lubab Androidi inimestel teha kõike omamoodi. p(i), ja keegi teine ei oma selle väärtuse kohta mingit teavet. Järgmises lõigus peame samuti arvestama, et mõnes eelnevalt määratud punktis G kõik teavad erinevate väärtuste H0 = p(0)H, x.

Selles lõigus eeldame, et igal osalejal on kohalikult mingi privaatvõti xi, ni, et kõik teavad vastavat avalikku võtit Xi.

Üks võimalik polünoomi genereerimise protokoll on järgmine:

1. Iga osaleja i loodab kohalikult suvalise polünoomi pi(x) järku k-1. Seejärel saadavad nad igale osalejale j väärtuse pi(j), mis on krüpteeritud avaliku võtmega Xj. Nii et ainult i-j-nda ja - osaleja teabj-nda i(j). Osaleja pteeb samuti avalikult teada i pi(j)G kaasa arvatud. H0 = p(0)H, j alates 1 kuni k Kõik osalejad kasutavad mingit konsensust, et valida

2. osalejad, kelle polünoome kasutatakse. Kuna mõned osalejad võivad olla väljaspool võrku, ei saa me oodata, kuni kõik k osalejad avaldavad polünoome. Selle sammu tulemus on hulk n mis koosneb vähemalt Z polünoomidest, mis loodi sammus (1) k Osalejad veenduvad, et neile tuntud väärtused.

3. i(j) vastavad avalikult teada antud ppi(j)G. Pärast seda sammu peaksid jääma vaid polünoomid, mille privaatselt edastatud arvutab oma privaatkomponendi Z p(j) ppi(j)G. Pärast seda sammu peaksid jääma vaid polünoomid, mille privaatselt edastatud

4. Iga osaleja j nagu summa i(j) kõigi . Iga osaleja arvutab samuti kõik väärtused ppi(x)G kõikide i jaoks. i ja Zp(x) – erinevate väärtuste . Iga osaleja arvutab samuti kõik väärtused see on tõeliselt polünoom järku ja Z.

Pange tähele, et k-1, sest see on eraldi i(x), millest igaüks on polünoom astmega k-1. pseega on see summa eraldi k-1. See, while each participant j kuidas seda teha. Ja seepärast käitub Google ühes suhtes väga targalt: lubab Androidi inimestel teha kõike omamoodi. p(j), they have no information about p(x) jaoks x ≠ j. Indeed, to compute this value, they need to know all pi(x), and as long as the participant j doesn't know at least one of the selected polynomials, they lack sufficient information about p(x).

This is the entire polynomial generation process that was required in the previous section. Steps 1, 2, and 4 above have a quite clear implementation. However, step 3 is not so trivial.

Specifically, we need to be able to prove that the encrypted pi(j) indeed corresponds to the published Pärast seda sammu peaksid jääma vaid polünoomid, mille privaatselt edastatud If we cannot prove this, an attacker i could send garbage instead of pi(j) to the participant j, and the participant j would not be able to obtain the actual value pi(j), and would not be able to calculate their private component..

There is a cryptographic protocol that allows you to create an additional message proofi(j), such that any participant, having some value e, as well as proofi(j) ja pi(j)G, can locally verify that e – this is indeed pi(j), encrypted with participant's key j. Unfortunately, the size of such proof is incredibly large, and considering that it is necessary to publish O(nk) such proofs, they cannot be used for this purpose.

Instead of proving that pi(j) vastab pi(j)G we can in the polynomial generation protocol allocate a very large interval of time, during which all participants check the obtained encrypted pi(j), and if the decrypted message does not match the public pi(j)G, they publish a cryptographic proof that the encrypted message they received is incorrect. Proving that the message ei vastab pi(G) is much easier than proving that it corresponds. It should be noted that this requires each participant to appear in the network at least once during the time allocated for creating such proofs and relies on the assumption that if they published such proof, it will reach all other participants within the same allocated time.

If a participant did not appear in the network during this time period, and they indeed had at least one incorrect component, then this particular participant will not be able to participate in further number generation. The protocol, however, will still function if there is at least k osalejatest, kes kas just said õiged komponendid või suutsid jätta tõestuse vale kohta ettenähtud ajas.

H_i õiguse tõestused

Viimane osa, mida arutada, on see, kuidas tõestada avaldatud korrektset Hi, nimelt, et mida nad saavad teha, sest nad teavad ilma avamata. p(i).

Käidame meeles, et väärtused H, G, p(i)G on avalikud ja tuntud kõigile. Saamist teo p(i) teades p(i)G ja G nimetatakse diskreetseks logaritmiks, või dlog, ja me tahame tõestada, et:

dlog(p(i)G, G) = dlog(Hi, H)

ilma avaldamiseta. p(i)Selliste tõestuste jaoks on olemas konstruktsioonid, näiteks Schnorr protokoll..

Sellise konstruktsiooniga saadab iga osaleja koos Hi tõestuse õiguse järgi konstruktsiooni.

Kui juhuslik number on genereeritud, tuleb seda tihti kasutada osalejatele, kes ei ole selle genereerinud. Sellistele osalejatele tuleb koos numbriga saata kõik Hi ja seotud tõestused.

Uuriv lugeja võib küsida: kuna lõplik juhuslik number on H0 ja p(0)G – see on avalik teave, siis miks on vajalik tõestus iga eraldi jaoks Hi, miks mitte saata tõestust selle osas, et

dlog(p(0)G, G) = dlog(H.0, H)

Probleem on selles, et Schnorr protokolli abil ei saa luua sellist tõestust, sest keegi ei tea väärtust p(0),mida on vajalik tõestuse loomiseks, ning veelgi enam, kogu juhuslike numbrite generaator põhineb sellel, et keegi ei tea seda väärtust. Seetõttu on vajalik omada kõiki väärtusi Hi ja nende individuaalseid tõestusi, et tõestada õigust. H0.

Kuid kui eliptiliste kõverate punktidel oleks mingisugune tegu, mis on semantiliselt sarnane korrutamisega, siis oleks õiguse tõestamine H0 olnud triviaalne, me lihtsalt kindlustaksime, et

H0 × G = p(0)G × H.

Kui valitud kõver toetab elliptic curve pairings,siis töötab selline tõestus. Sellisel juhul H0 on mitte ainult juhuslike numbrite generaatori väljund, mida saab kontrollida iga osaleja, kes teab G, H, ja p(0)G. H0 on samuti allkiri sõnumis, mida kasutati seemnena, kinnitades, et k ja n osalejad allkirjastasid selle sõnumi. Seega, kui seeme – on ploki hash plokiahela protokollis, siis H0 - on samaaegselt mitme allkiri plokis ja väga hea juhuslik number.

Kokkuvõtteks

See artikkel on osa tehniliste artiklite seeriast blogis. NEAR. NEAR – see on plokiahel protokoll ja platvorm detsentraliseeritud rakenduste arendamiseks, mille rõhk on arendamise lihtsusel ja lõppkasutajate kasutusmugavusel.

Protokolli kood on avatud, meie teostus on kirjutatud Rustis, seda saab leida siit.

Vaata, kuidas NEAR-i arendus välja näeb ja eksperimentida saad veebipõhises IDE-s siin.

Kõiki uudiseid vene keeles saab jälgida grupis Telegramis ja grupis Vkontakte, ja inglise keeles ametlikus Twitteris.

Jõuame taas kokku!

Allikas: habr.com