Is dit moontlik om ewekansige getalle te genereer as ons mekaar nie vertrou nie? Deel 2

Haai Habr!

В die eerste deel In hierdie artikel het ons bespreek hoekom dit nodig mag wees om ewekansige getalle te genereer vir deelnemers wat mekaar nie vertrou nie, watter vereistes vir sulke ewekansige getalgenerators gestel word, en twee benaderings tot die implementering daarvan oorweeg.

In hierdie deel van die artikel gaan ons nader kyk na 'n ander benadering wat drempelhandtekeninge gebruik.

Bietjie kriptografie

Om te verstaan ​​hoe drempelhandtekeninge werk, moet jy 'n bietjie basiese kriptografie verstaan. Ons sal twee konsepte gebruik: skalare, of bloot syfers, wat ons met kleinletters sal aandui (x, y) en punte op die elliptiese kromme, wat ons met hoofletters sal aandui.

Om die basiese beginsels van drempelhandtekeninge te verstaan, hoef jy nie te verstaan ​​hoe elliptiese krommes werk nie, behalwe 'n paar basiese dinge:

1. Punte op 'n elliptiese kurwe kan opgetel en vermenigvuldig word met 'n skalaar (ons sal vermenigvuldiging met 'n skalaar aandui as xG, hoewel die notasie Gx ook dikwels in die literatuur gebruik). Die resultaat van optelling en vermenigvuldiging met 'n skalaar is 'n punt op 'n elliptiese kromme.

2. Weet net die punt G en sy produk met 'n skalaar xG kan nie bereken word nie x.

Ons sal ook die konsep van 'n polinoom gebruik p (x) grade k-1. Ons sal veral die volgende eienskap van polinome gebruik: as ons die waarde ken p (x) vir enige k verskillende x (en ons het nie meer inligting oor nie p (x)), kan ons bereken p (x) vir enigiemand anders x.

Dit is interessant dat vir enige polinoom p (x) en 'n punt op die kurwe Gdie betekenis te ken p(x)G vir enige k verskillende betekenisse x, kan ons ook bereken p(x)G vir enige x.

Dit is genoeg inligting om te delf in die besonderhede van hoe drempelhandtekeninge werk en hoe om dit te gebruik om ewekansige getalle te genereer.

Willekeurige getalgenerator op drempelhandtekeninge

Kom ons sê dit n deelnemers wil 'n ewekansige nommer genereer, en ons wil hê enigiemand moet deelneem k daar was genoeg van hulle om 'n nommer te genereer, maar sodat die aanvallers wat beheer k-1 of minder deelnemers kon nie die gegenereerde getal voorspel of beïnvloed nie.

Gestel daar is so 'n polinoom p (x) grade k-1 wat die eerste deelnemer weet p (1), weet die tweede een p(2), en so aan (n-die weet p(n)). Ons neem ook aan dat vir 'n voorafbepaalde punt G almal weet p(x)G vir alle waardes x. Ons sal bel PI) "privaat komponent" ide deelnemer (omdat slegs idie de deelnemer ken haar), en p(i)G "openbare komponent" i-de deelnemer (omdat alle deelnemers haar ken). Soos jy onthou, kennis p(i)G nie genoeg om te herstel nie PI).

Die skep van so 'n polinoom sodat slegs i-Die eerste deelnemer en niemand anders het sy private komponent geken nie - dit is die mees komplekse en interessante deel van die protokol, en ons sal dit hieronder ontleed. Kom ons neem vir eers aan dat ons so 'n polinoom het en alle deelnemers ken hul private komponente.

Hoe kan ons so 'n polinoom gebruik om 'n ewekansige getal te genereer? Om mee te begin, benodig ons 'n string wat nie voorheen as toevoer na die kragopwekker gebruik is nie. In die geval van 'n blokketting, die hash van die laaste blok h is 'n goeie kandidaat vir so 'n lyn. Laat deelnemers 'n ewekansige getal wil skep deur h soos saad. Deelnemers bekeer eers h na 'n punt op die kromme deur enige voorafbepaalde funksie te gebruik:

H = scalarToPoint(h)

Dan elke deelnemer i bereken en publiseer Hi = p(i)H, wat kan hulle doen omdat hulle weet p(i) en H. Openbaarmaking Hek laat nie ander deelnemers toe om die private komponent te herstel nie iste deelnemer, en daarom kan een stel private komponente van blok tot blok gebruik word. Die duur polinoomgenereringsalgoritme wat hieronder beskryf word, hoef dus net een keer uitgevoer te word.

Wanneer k deelnemers is nadoodse ondersoek Hi = p(i)H, almal kan bereken Hx = p(x)H vir alle x danksy die eienskap van polinome wat ons in die laaste afdeling bespreek het. Op hierdie oomblik bereken alle deelnemers H0 = p(0)H, en dit is die gevolglike ewekansige getal. Neem asseblief kennis dat niemand weet nie p(0), en dus die enigste manier om te bereken p(0)H – dit is interpolasie p(x)H, wat slegs moontlik is wanneer k waardes p(i)H bekend. Maak enige kleiner hoeveelheid oop p(i)H verskaf geen inligting oor p(0)H.

Die kragopwekker hierbo het al die eienskappe wat ons wil hê: aanvallers wat slegs beheer k-1 deelnemers of minder het geen inligting of invloed op die gevolgtrekking nie, terwyl enige k deelnemers kan die gevolglike getal bereken, en enige subset van k deelnemers sal altyd tot dieselfde resultaat vir dieselfde saad kom.

Daar is een probleem wat ons hierbo noukeurig vermy het. Vir interpolasie om te werk, is dit belangrik dat die waarde Hi wat deur elke deelnemer gepubliseer is i dit was regtig dieselfde p(i)H. Aangesien niemand behalwe i-de deelnemer weet nie PI), niemand behalwe i-die deelnemer kan dit nie verifieer nie Hi eintlik korrek bereken, en sonder enige kriptografiese bewys van korrektheid Hek 'n aanvaller kan enige waarde publiseer as Hi, en die uitset van die ewekansige getalgenerator arbitrêr te beïnvloed:

Verskillende waardes van H_1 wat deur die eerste deelnemer gestuur word, lei tot verskillende gevolglike H_0

Daar is ten minste twee maniere om korrektheid te bewys Hek, ons sal hulle oorweeg nadat ons die generering van die polinoom ontleed het.

Polinoomgenerering

In die laaste afdeling het ons aangeneem dat ons so 'n polinoom het p (x) grade k-1 dat die deelnemer i hy weet PI), en niemand anders het enige inligting oor hierdie waarde nie. In die volgende afdeling sal ons dit ook nodig hê vir een of ander voorafbepaalde punt G almal het geweet p(x)G vir alle x.

In hierdie afdeling sal ons aanvaar dat elke deelnemer plaaslik een of ander privaat sleutel het XI, sodanig dat almal die ooreenstemmende publieke sleutel ken Xi.

Een moontlike polinoomgenereringsprotokol is soos volg:

1. Elke deelnemer i plaaslik 'n arbitrêre polinoom skep pi(x) graad k-1. Hulle stuur dan elke deelnemer j waarde pi(j), geïnkripteer met publieke sleutel Xj. Slegs dus i-ste и j-ste deelnemer weet pi(j). Deelnemer i kondig ook in die openbaar aan pi(j)G vir alle j van 1 aan k inklusief.

2. Alle deelnemers gebruik een of ander konsensus om te kies k deelnemers wie se polinome gebruik sal word. Aangesien sommige deelnemers dalk vanlyn is, kan ons nie wag tot almal nie n deelnemers sal polinome publiseer. Die resultaat van hierdie stap is 'n stel Z bestaande uit ten minste k polinome geskep in stap (1).

3. Deelnemers maak seker dat die waardes wat hulle ken pi(j) stem ooreen met publiek aangekondig pi(j)G. Na hierdie stap in Z slegs polinome waarvoor privaat oorgedra word pi(j) stem ooreen met publiek aangekondig pi(j)G.

4. Elke deelnemer j sy private komponent bereken p(j) as 'n som pi(j) vir almal i в Z. Elke deelnemer bereken ook alle waardes p(x)G as 'n som pi(x)G vir alle i в Z.

Let asseblief daarop dat p(x) – dit is regtig 'n polinoom k-1, want dit is die som van die individu pi(x), wat elk 'n polinoom van graad is k-1. Let dan op dat terwyl elke deelnemer j hy weet p(j), hulle het geen inligting oor p (x) vir x ≠ j. Om hierdie waarde te bereken, moet hulle inderdaad alles weet pi(x), en solank die deelnemer j ten minste een van die geselekteerde polinome ken nie, het hulle nie voldoende inligting oor nie p(x).

Dit is die hele polinoomgenereringsproses wat in die laaste afdeling nodig was. Stap 1, 2 en 4 hierbo het 'n redelik voor die hand liggende implementering. Maar stap 3 is nie so triviaal nie.

Spesifiek, ons moet in staat wees om dit geïnkripteer te bewys pi(j) stem werklik ooreen met die gepubliseerde pi(j)G. As ons dit nie kan bewys nie, die aanvaller i mag eerder vullis stuur pi(j) aan deelnemer j, en deelnemer j sal nie die werklike waarde kan kry nie pi(j), en sal nie die private komponent daarvan kan bereken nie.

Daar is 'n kriptografiese protokol wat jou toelaat om 'n bykomende boodskap te skep bewysi(j), sodanig dat enige deelnemer, wat waarde het e, asook bewys (j) и pi(j)G, kan dit plaaslik verifieer e - dit is regtig pi(j), geïnkripteer met die deelnemer se sleutel j. Ongelukkig is die omvang van sulke bewyse ongelooflik groot, en gegewe dat dit nodig is om te publiseer O(nk) Sulke bewyse kan nie vir hierdie doel gebruik word nie.

In plaas daarvan om dit te bewys pi(j) соответствует pi(j)G ons kan 'n baie lang tydperk toewys in die polinoomgenereringsprotokol, waartydens alle deelnemers die ontvang-enkripteer kontroleer pi(j), en as die ontsyferde boodskap nie met die publiek ooreenstem nie pi(j)G, hulle publiseer 'n kriptografiese bewys dat die geënkripteerde boodskap wat hulle ontvang het, verkeerd is. Bewys dat die boodskap geen соответствует pi(G) baie makliker as om te bewys dat dit ooreenstem. Daar moet kennis geneem word dat dit vereis dat elke deelnemer ten minste een keer aanlyn moet verskyn gedurende die tyd wat toegeken is om sulke bewyse te skep, en staatmaak op die aanname dat indien hulle so 'n bewys publiseer, dit alle ander deelnemers in dieselfde toegelate tyd sal bereik.

Indien 'n deelnemer gedurende hierdie tydperk nie aanlyn verskyn het nie, en hy het wel ten minste een verkeerde komponent gehad, dan sal daardie betrokke deelnemer nie aan verdere nommergenerering kan deelneem nie. Die protokol sal egter steeds funksioneer as daar ten minste is k deelnemers wat óf pas die korrekte komponente ontvang het óf daarin geslaag het om bewyse van onjuistheid binne die toegelate tyd te laat.

Bewyse van korrektheid van H_i

Die laaste deel wat nog bespreek moet word, is hoe om die korrektheid van gepubliseerde te bewys Hek, naamlik dit Hi = p(i)H, sonder oopmaak PI).

Laat ons onthou dat die waardes H, G, p(i)G publiek en bekend aan almal. Ontvang operasie PI) weet p(i)G и G genoem diskrete logaritme, of hond, en ons wil bewys dat:

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

sonder openbaarmaking PI). Konstruksies vir sulke bewyse bestaan ​​byvoorbeeld Schnorr-protokol.

Met hierdie ontwerp, elke deelnemer, saam met Hi stuur 'n bewys van korrektheid volgens die ontwerp.

Sodra 'n ewekansige getal gegenereer is, moet dit dikwels gebruik word deur ander deelnemers as diegene wat dit gegenereer het. Sulke deelnemers, saam met die nommer, moet almal stuur Hi en verwante bewyse.

'n Nuuskierige leser kan vra: aangesien die finale ewekansige getal is H0, en p(0)G – Dit is publieke inligting, hoekom het ons bewyse nodig vir elke individu Hek, hoekom stuur nie eerder bewys dat dit

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

Die probleem is dat so 'n bewys nie geskep kan word deur die Schnorr-protokol te gebruik nie, want niemand weet wat die waarde is nie p (0), wat nodig is om die bewys te skep, en wat meer is, die hele ewekansige getalgenerator is gebaseer op die feit dat niemand hierdie waarde ken nie. Daarom is dit nodig om al die waardes te hê Hi en hul individuele bewyse om korrektheid te bewys H0.

As daar egter een of ander bewerking op punte op elliptiese krommes was wat semanties soortgelyk is aan vermenigvuldiging, is die bewys van korrektheid H0 triviaal sou wees, sou ons eenvoudig seker maak dat

H0 × G = p(0)G × H

As die gekose kromme ondersteun elliptiese kromme parings, hierdie bewys werk. In hierdie geval H0 is nie net die uitset van 'n ewekansige getalgenerator nie, wat geverifieer kan word deur enige deelnemer wat weet G,H и p(0)G. H0 is ook 'n handtekening op die boodskap wat as 'n saad gebruik is, wat dit bevestig k и n deelnemers het hierdie boodskap onderteken. Dus, as saad - is die hash van die blok in die blockchain-protokol, dan H0 is beide 'n multi-handtekening op 'n blok en 'n baie goeie ewekansige getal.

Ten slotte

Hierdie artikel is deel van 'n tegniese blogreeks NEAR. NEAR is 'n blockchain-protokol en platform vir die ontwikkeling van gedesentraliseerde toepassings met die klem op gemak van ontwikkeling en gemak van gebruik vir eindgebruikers.

Die protokolkode is oop, ons implementering is in Rust geskryf, dit kan gevind word hier.

Jy kan sien hoe ontwikkeling onder NEAR lyk, en jy kan eksperimenteer in die aanlyn IDE hier.

Jy kan al die nuus in Russies volg in groep in telegram en groep op VKontakte, en in Engels in die amptelike Twitter.

О скорых встреч!

Bron: will.com