Posible al da ausazko zenbakiak sortzea elkarrengan konfiantzarik ez badugu? 2. zatia

Aupa Habr!

В Lehenengo zatia Artikulu honetan, elkarrengan fidatzen ez diren parte-hartzaileentzat zergatik izan litekeen ausazko zenbakiak sortzea beharrezkoa den eztabaidatu dugu, ausazko zenbaki-sorgailu horientzako zein baldintza planteatzen diren eta haien ezarpenerako bi ikuspegi aztertu ditugu.

Artikuluaren zati honetan, atalasearen sinadurak erabiltzen dituen beste ikuspegi bat gehiago aztertuko dugu.

Kriptografia pixka bat

Atalaseen sinadurak nola funtzionatzen duten ulertzeko, oinarrizko kriptografia apur bat ulertu behar duzu. Bi kontzeptu erabiliko ditugu: eskalarrak, edo besterik gabe zenbakiak, letra xehez adieraziko ditugunak (x, y) eta kurba eliptikoko puntuak, letra larriz adieraziko ditugunak.

Atalaseen sinaduren oinarriak ulertzeko, ez duzu kurba eliptikoen funtzionamendua ulertu beharrik, oinarrizko gauza batzuk baino:

1. Kurba eliptiko bateko puntuak eskalar batez batu eta biderkatu egin daitezke (eskalarez biderketa gisa adieraziko dugu xG, nahiz eta notazioa Gx literaturan ere askotan erabilia). Eskalar baten batuketaren eta biderketaren emaitza kurba eliptikoko puntu bat da.

2. Puntua bakarrik jakitea G eta bere produktua eskalar batekin xG ezin da kalkulatu x.

Polinomio kontzeptua ere erabiliko dugu p(x) gradu k-1. Bereziki, polinomioen propietate hau erabiliko dugu: balioa ezagutzen badugu p(x) edozeinentzat k ezberdinak x (eta ez dugu informazio gehiago p(x)), kalkula dezakegu p(x) beste edonorentzat x.

Interesgarria da edozein polinomiotarako p(x) eta kurbako punturen bat Gesanahia jakitea p(x)G edozeinentzat k esanahi desberdinak x, kalkula dezakegu ere p(x)G edozeinentzat x.

Informazio nahikoa da atalaseen sinadurak nola funtzionatzen duten eta ausazko zenbakiak sortzeko nola erabili.

Ausazko zenbaki-sorgailua atalasearen sinaduretan

Esan dezagun hori n parte hartzaileek ausazko zenbaki bat sortu nahi dute, eta edonork parte hartzea nahi dugu k kopuru bat sortzeko nahikoa zeuden, baina kontrolatzen duten erasotzaileek k-Parte-hartzaile 1 edo gutxiagok ezin izan dute sortutako kopurua aurreikusi edo eragin.

Demagun halako polinomio bat dagoela p(x) gradu k-1 lehenengo parte hartzaileak dakiena p (1), bigarrenak badaki p (2), eta abar (n-thek daki p(n)). Hori ere suposatzen dugu aurrez zehaztutako puntu baterako G denek daki p(x)G balio guztientzat x. deituko dugu p(i) "osagai pribatua" igarren parte-hartzailea (soilik igarren partaideak ezagutzen du), eta p(i)G "osagai publikoa" i-garren partaidea (parte hartzaile guztiek ezagutzen dutelako). Gogoratzen duzun bezala, ezagutza p(i)G ez da nahikoa berreskuratzeko p(i).

Halako polinomio bat sortzea horrela bakarrik i-Lehen parte-hartzaileak eta inork ez zuen bere osagai pribatua ezagutzen - hau da protokoloaren zatirik konplexuena eta interesgarriena, eta jarraian aztertuko dugu. Oraingoz, demagun polinomio hori dugula eta parte-hartzaile guztiek beren osagai pribatuak ezagutzen dituztela.

Nola erabil dezakegu halako polinomio bat ausazko zenbaki bat sortzeko? Hasteko, aurretik sorgailurako sarrera gisa erabili ez den kate bat behar dugu. Blockchain baten kasuan, azken blokearen hash-a h hautagai ona da halako lerro baterako. Utzi parte-hartzaileek ausazko zenbaki bat sortu nahi dutela erabiliz h hazia bezala. Parte-hartzaileak lehenbizi bihurtzen dira h Kurbako puntu batera aurrez zehaztutako edozein funtzio erabiliz:

H = eskalarToPoint(h)

Ondoren, parte hartzaile bakoitza i kalkulatu eta argitaratzen du Hi = p(i)H, zer egin dezakete badakitelako p(i) eta H. dibulgazioa HEz dut onartzen beste parte-hartzaileek osagai pribatua leheneratzen igarren parte-hartzailea, eta, beraz, osagai pribatuen multzo bat erabil daiteke blokez bloke. Beraz, behean deskribatzen den polinomioen sorkuntzako algoritmo garestiak behin bakarrik exekutatu behar da.

Noiz k parte-hartzaileei autopsia egin zitzaien Hi = p(i)H, denek kalkula dezakete Hx = p(x)H guztientzat x azken atalean aztertu dugun polinomioen propietateari esker. Momentu honetan, parte-hartzaile guztiek kalkulatzen dute H0 = p(0)H, eta hau da ondoriozko zenbaki aleatorioa. Kontuan izan inork ez dakiela p (0), eta, beraz, kalkulatzeko modu bakarra p(0)H – hau interpolazioa da p(x)H, denean bakarrik posible dena k balioak p(i)H ezagunak. Kantitate txikiagoa irekitzea p(i)H ez du inongo informaziorik ematen p(0)H.

Goiko sorgailuak nahi ditugun propietate guztiak ditu: erasotzaileak soilik kontrolatzea k-1 parte-hartzaileek edo gutxiagok ez dute ondorioan informaziorik edo eraginik, baina edozeinek k parte-hartzaileek ondoriozko kopurua eta edozein azpimultzo kalkula ditzakete k parte hartzaileak beti emaitza berdinera iritsiko dira hazi berarentzat.

Goian arretaz saihestu dugun arazo bat dago. Interpolazioak funtziona dezan, garrantzitsua da balioa HParte-hartzaile bakoitzak argitaratu zuen i i benetan berdina zen p(i)H. Inork izan ezik i-garren parte hartzaileak ez daki p(i), inor ez ezik i-parte hartzaileak ezin du hori egiaztatu Hi benetan behar bezala kalkulatuta, eta zuzentasunaren froga kriptografikorik gabe HErasotzaile batek edozein balio gisa argitara dezake Hi, eta modu arbitrarioan eragin ausazko zenbaki-sorgailuaren irteeran:

Lehenengo parte-hartzaileak bidalitako H_1-ren balio ezberdinek H_0 emaitza desberdinak sortzen dituzte

Zuzentasuna frogatzeko bi modu daude gutxienez Hi, polinomioaren sorrera aztertu ondoren kontuan hartuko ditugu.

Polinomioen sorrera

Azken atalean halako polinomio bat dugula suposatu dugu p(x) gradu k-1 parte-hartzailea dela i He daki p(i), eta beste inork ez du balio honi buruzko informaziorik. Hurrengo atalean ere hori beharko dugu aurrez zehaztutako puntu baterako G denek zekiten p(x)G guztientzat x.

Atal honetan parte-hartzaile bakoitzak lokalean gako pribaturen bat duela suposatuko dugu xi, hala nola, denek ezagutzen dute dagokion gako publikoa Xi.

Polinomioak sortzeko protokolo posible bat honako hau da:

1. Parte-hartzaile bakoitza i lokalean polinomio arbitrario bat sortzen du pi(x) gradua k-1. Ondoren, parte hartzaile bakoitza bidaltzen dute j balioa pi(j), gako publikoarekin zifratua Xj. Horrela bakarrik i-garren и j-garren parte hartzaileak badaki pi (j). Parte-hartzailea i publikoki ere iragartzen du pi(j)G guztientzat j tik 1 to k biak barne.

2. Parte-hartzaile guztiek adostasun batzuk erabiltzen dituzte aukeratzeko k polinomioak erabiliko dituzten parte-hartzaileak. Parte-hartzaile batzuk lineaz kanpo egon daitezkeenez, ezin dugu denak arte itxaron n parte hartzaileek polinomioak argitaratuko dituzte. Urrats honen emaitza multzo bat da Z gutxienez osatua k (1) urratsean sortutako polinomioak.

3. Parte-hartzaileek ezagutzen dituzten balioak ziurtatzen dituzte pi(j) publikoki iragarritakoari dagozkio pi(j)G. Urrats honen ostean Z pribatuki transmititzen diren polinomioak soilik pi(j) publikoki iragarritakoari dagozkio pi(j)G.

4. Parte-hartzaile bakoitza j bere osagai pribatua kalkulatzen du p(j) batura gisa pi(j) guztientzat i в Z. Parte-hartzaile bakoitzak ere balio guztiak kalkulatzen ditu p(x)G batura gisa pi(x)G i guztientzat в Z.

Kontuan izan p(x) – benetan polinomio bat da k-1, norbanakoaren batura baita pi(x), eta horietako bakoitza graduko polinomio bat da k-1. Ondoren, kontuan izan parte-hartzaile bakoitzak j He daki p(j), ez dute informaziorik p(x) egiteko x ≠ j. Izan ere, balio hori kalkulatzeko, dena jakin behar dute pi(x), eta betiere parte-hartzailea j aukeratutako polinomioetako bat gutxienez ez du ezagutzen, ez dute informazio nahikorik p(x).

Hau da azken atalean behar zen polinomioen sorkuntza prozesu osoa. Goiko 1., 2. eta 4. urratsek nahiko argia dute ezarpena. Baina 3. urratsa ez da hain hutsala.

Zehazki, enkriptatutako hori frogatu ahal izan behar dugu pi(j) benetan argitaratutakoei dagokie pi(j)G. Ezin badugu frogatu, erasotzailea i ordez zaborra bidal dezake pi(j) parte-hartzaileari j, eta parte-hartzailea j ezin izango du benetako balioa lortu pi(j), eta ezin izango du bere osagai pribatua kalkulatu.

Mezu gehigarri bat sortzeko aukera ematen duen protokolo kriptografiko bat dago frogai(j), halako edozein parte-hartzaile, balioren bat izatea e, baita froga (j) и pi(j)G, lokalean egiazta dezake hori e - Benetan da pi(j), parte-hartzailearen gakoarekin zifratuta j. Zoritxarrez, froga horien tamaina izugarri handia da, eta argitaratzea beharrezkoa dela kontuan hartuta O(nk) Ebidentzia horiek ezin dira horretarako erabili.

Hori frogatu beharrean pi(j) соответствует pi(j)G polinomioen sorrerako protokoloan denbora-tarte oso luzea esleitu dezakegu, parte-hartzaile guztiek jasotako enkriptatutakoa egiaztatzen duena. pi(j), eta deszifratutako mezua publikoarekin bat ez badator pi(j)G, jasotako mezu enkriptatua okerra dela dioen froga kriptografikoa argitaratzen dute. Froga ezazu mezua dela ez соответствует pi(G) bat datorrela frogatzea baino askoz errazagoa. Kontuan izan behar da horrek parte-hartzaile bakoitza linean agertzea eskatzen duela froga horiek sortzeko emandako denboran gutxienez behin, eta froga hori argitaratzen badute, emandako denbora berean gainontzeko partaide guztiei helduko zaiela suposatzen duela.

Denbora tarte horretan parte-hartzaile bat ez bada sarean agertu eta gutxienez osagai oker bat izan badu, orduan parte-hartzaile jakin horrek ezin izango du parte hartu zenbaki-sorkuntzan. Protokoloak, hala ere, oraindik ere funtzionatuko du, baldin badago behintzat k osagai zuzenak jaso berri dituzten edo emandako denboran okerraren frogak uztea lortu duten parte-hartzaileak.

H_i-ren zuzentasunaren frogak

Aztertu beharreko azken zatia argitaratutakoaren zuzentasuna nola frogatu da Hi, hots, hori Hi = p(i)H, ireki gabe p(i).

Gogora dezagun baloreak H, G, p(i)G publikoa eta guztiontzat ezaguna. Eragiketa jaso p(i) jakitea p(i)G и G logaritmo diskretua deritzona, edo dlog, eta hori frogatu nahi dugu:

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

ezagutarazi gabe p(i). Halako frogak egiteko eraikuntzak existitzen dira, adibidez Schnorr Protokoloa.

Diseinu honekin, parte-hartzaile bakoitzak, batera Hi diseinuaren arabera zuzenaren froga bat bidaltzen du.

Ausazko zenbaki bat sortu ondoren, askotan sortu dutenek ez diren parte-hartzaileek erabili behar dute. Halako partaideek, zenbakiarekin batera, guztiak bidali behar dituzte Hi eta erlazionatutako frogak.

Irakurle jakintsu batek galde dezake: azken ausazko zenbakia baita H0, eta p(0)G – Hau informazio publikoa da, zergatik behar dugu froga banako bakoitzarentzat Hi, zergatik ez bidali horren ordez froga

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

Arazoa da froga hori ezin dela sortu Schnorr Protokoloa erabiliz, inork ez baitu balioa ezagutzen p (0), froga sortzeko beharrezkoa, eta, gainera, ausazko zenbaki-sorgailu osoa balio hori inork ez dakienean oinarritzen da. Beraz, beharrezkoa da balio guztiak edukitzea Hi eta zuzentasuna frogatzeko haien banakako frogak H0.

Hala ere, semantikoki biderketaren antzekoa den kurba eliptikoetako puntuetan eragiketaren bat balego, zuzentasunaren froga H0 hutsala izango litzateke, hori ziurtatuko genuke besterik gabe

H0 × G = p(0)G × H

Hautatutako kurbak onartzen badu kurba eliptikoen parekatzeak, froga honek funtzionatzen du. Kasu honetan H0 ez da ausazko zenbaki-sorgailu baten irteera bakarrik, eta hori dakien edozein parte-hartzailek egiaztatu dezake G,H и p(0)G. H0 hazi gisa erabili zen mezuaren sinadura ere bada, hori baieztatzen duena k и n parte hartzaileek mezu hau sinatu dute. Horrela, bada hazia - blokearen hash-a da blockchain protokoloan, orduan H0 Bloke bateko sinadura anitzekoa eta ausazko zenbaki oso ona da.

Ondorioz

Artikulu hau blog teknikoen serie baten parte da NEAR. NEAR aplikazio deszentralizatuak garatzeko blockchain protokoloa eta plataforma bat da, azken erabiltzaileentzako garapen erraztasunean eta erabiltzeko erraztasunean azpimarratuz.

Protokolo kodea irekita dago, gure inplementazioa Rust-en idatzita dago, aurki daiteke Hemen.

NEAR-en garapena nolakoa den ikusi eta lineako IDEan esperimentatu dezakezu Hemen.

Albiste guztiak errusieraz jarrai ditzakezu hemen telegrama taldea eta taldea VKontakte-n, eta ingelesez ofizialean Twitter.

Laster arte!

Iturria: www.habr.com