Hey Habr!
В Di vê gotarê de, me nîqaş kir ku çima dibe ku hewce be ku ji bo beşdarên ku ji hev bawer nakin hejmarên bêserûber biafirînin, çi hewcedariyên ji bo hilberînerên jimareyên bêserûber têne pêşandan, û ji bo pêkanîna wan du nêzîkatî nirxand.
Di vê beşa gotarê de, em ê nêzîkatiyek din a ku îmzayên sînor bikar tîne binihêrin.
Piçek şîfrekirin
Ji bo ku hûn fêm bikin ka îmzeyên sînor çawa dixebitin, hûn hewce ne ku hûn şîfreyek bingehîn a piçûk fam bikin. Em ê du têgînan bikar bînin: scalars, an tenê hejmar, ku em ê bi tîpên piçûk destnîşan bikin (x, y) û xalên li ser qerta eliptîk, ku em ê bi tîpên mezin diyar bikin.
Ji bo têgihîştina bingehên îmzeyên sînor, hûn ne hewce ne ku hûn fêm bikin ka kavilên eliptîk çawa dixebitin, ji bilî çend tiştên bingehîn:
-
Xalên li ser xêzeke elîptîk dikarin bi scalarekê werin zêdekirin û pirkirin (em ê pirkirina bi pîvanek wekî xG, tevî ku nîşan Gx di wêjeyê de jî gelek caran tê bikaranîn). Encama zêdekirin û pirkirina bi scalar xalek li ser kelekek eliptîk e.
-
Tenê xalê dizanin G û berhema wê bi skalar xG nayê hesibandin x.
Em ê têgeha pirnomî jî bikar bînin p(x) dersan k-1. Bi taybetî, em ê taybetmendiya jêrîn a pirnomîlan bikar bînin: heke em nirxê bizanibin p(x) ji bo her k cuda x (û bêtir agahdarî li ser me tune p(x)), em dikarin hesab bikin p(x) ji bo kesekî din x.
Balkêş e ku ji bo her polynomial p(x) û hin xal li ser kewê Gwateya dizanin p(x)G ji bo her k wateyên cuda x, em jî dikarin hesab bikin p(x)G ji bo her x.
Ev agahdarî bes e ku meriv hûrguliyên li ser ka çawa îmzeyên bordûmanê dixebitîne û meriv wan çawa bikar tîne da ku hejmarên rasthatî çêbike.
Afirînerê hejmarên rasthatî li ser îmzayên sînor
Em vê bêjin n beşdaran dixwazin hejmareke rasthatî biafirînin, û em dixwazin her kes beşdar bibe k têra wan hebûn ku hejmarek çêbibin, lê ji ber ku êrîşkarên ku kontrol dikin k-1 an kêmtir beşdaran nikarîbûn pêşbînî bike an bandorê li ser hejmara hatî çêkirin bike.
Bifikirin ku pirnomîlek weha heye p(x) dersan k-1 ya ku beşdarê yekem dizane p (1), yê duyem dizane p(2), wate ya vê çîye (n-th dizane p(n)). Em di heman demê de texmîn dikin ku ji bo hin xalên pêşwextkirî G her kes dizane p(x)G ji bo hemû nirxan x. Em ê bang bikin p(i) "beşa taybet" ibeşdarê th (ji ber ku tenê ibeşdarê th wê nas dike), û beraz "Pêkhateya giştî" i-Beşdarê -mîn (ji ber ku hemî beşdar wê nas dikin). Wekî ku tê bîra we, zanîn beraz têra restorekirinê nake p(i).
Çêkirina pirnomîlek wisa ku tenê i-Beşdarê yekem û kesek din pêkhateya wî ya taybet nizanibû - ev beşa herî tevlihev û balkêş a protokolê ye, û em ê li jêr analîz bikin. Heya nuha, em bihesibînin ku me polînomek wusa heye û hemî beşdar beşên xwe yên taybet dizanin.
Em çawa dikarin pirnomîlek weha bikar bînin da ku jimareyek rasthatî çêkin? Ji bo destpêkê, em hewceyê hin rêzek e ku berê wekî têketina jeneratorê nehatibe bikar anîn. Di doza zincîra blokê de, haşa bloka paşîn h ji bo xeteke wiha namzetek baş e. Bila beşdar bixwazin ku bi karanîna jimareyek random biafirînin h wek tovê. Beşdar pêşî veguherînin h heya nuqteyek li ser kewê bi karanîna fonksiyonek pêşwextkirî:
H = scalarToPoint(h)
Piştre her beşdar i hesab dike û diweşîne Silav = p(i)H, ew dikarin çi bikin ji ber ku ew dizanin p(i) û H. Kişivî Hez rê nadim ku beşdarên din beşa taybet vegerînin ibeşdarê th, û ji ber vê yekê yek komek pêkhateyên taybet dikare ji blokê heta blokê were bikar anîn. Bi vî rengî, algorîtmaya hilberîna polînomî ya biha ya ku li jêr hatî destnîşan kirin tenê hewce ye ku carekê were darve kirin.
Dema ku k beşdaran otopsî kirin Silav = p(i)H, her kes dikare hesab bike Hx = = p(x)H ji bo hemî x bi saya taybetmendiya pirnomîlan a ku me di beşa dawî de behs kir. Di vê gavê de, hemî beşdaran hesab dikin H0 = p(0)H, û ev hejmara rasthatî ya encam e. Ji kerema xwe not bikin ku kes nizane p(0), û ji ber vê yekê tenê riya hesabkirinê ye p(0)H - ev navberkirin e p(x)H, ku tenê dema ku gengaz e k nirxên p(i)H tê zanîn. Vekirina hejmarek piçûktir p(i)H di derbarê de ti agahî nade p(0)H.
Generatorê jorîn hemî taybetmendiyên ku em dixwazin hene: êrîşkar tenê kontrol dikin k-1 beşdaran an hindiktir ti agahdarî an bandorek li ser encamnameyê tune, dema ku hebe k beşdar dikarin hejmara encam, û her binkeyek ji bihejmêrin k beşdar dê her dem ji bo heman tovê bigihîjin heman encamê.
Pirsgirêkek heye ku me li jor bi baldarî jê dûr xist. Ji bo ku interpolation kar bike, girîng e ku nirx Hi ku ji aliyê her beşdarekî ve hat weşandin i bi rastî jî wisa bû p(i)H. Ji ber ku tu kes ji bilî i-Beşdar nizane p(i), kes ji bilî i-Beşdar nikare wê verast bike Hi bi rastî rast tê hesab kirin, û bêyî ku delîlek rastdariyê ya krîptografîk Hez êrîşkar dikarim her nirxek wekî weşan bikim Merheba, û bi kêfî bandorê li derana hilberînerê hejmarên bêserûber dike:
Nirxên cihêreng ên H_1 ku ji hêla beşdarê yekem ve hatî şandin rê li ber encamên cûda yên H_0 vedike
Bi kêmanî du rê hene ku rastdariyê îspat bikin Hez, piştî ku em nifşê pirnomiyê analîz bikin, em ê wan bifikirin.
Nifşa Polynomial
Di beşa paşîn de me texmîn kir ku me pirnomîlek wusa heye p(x) dersan k-1 ku beşdar i dizane p(i), û kesek din di derbarê vê nirxê de agahdarî tune. Di beşa paşîn de em ê ji bo hin xalên pêşwext jî hewce bikin G her kesî dizanibû p(x)G ji bo hemî x.
Di vê beşê de em ê texmîn bikin ku her beşdarek herêmî xwedan mifteyek taybet e xi, wisa ku her kes mifteya giştî ya têkildar dizane Xi.
Yek protokola hilberîna polînomî ya gengaz wiha ye:
-
Her beşdar i herêmî pirnomîlek keyfî diafirîne pi(x) derece k-1. Dûv re ew her beşdarek dişînin j wateya pi (j), bi mifteya giştî hatî şîfrekirin Xj. Bi vî awayî tenê i-ый и j-ый beşdar dizanin pi(j). Beşdar i jî bi raya giştî re radigihîne pi(j)G ji bo hemî j ji 1 ber k tevhev.
-
Hemî beşdar ji bo hilbijartinê hin lihevhatin bikar tînin k beşdarên ku polynomials dê bên bikaranîn. Ji ber ku dibe ku hin beşdar negirêdayî bin, em nikarin li benda her kesî bisekinin n beşdar dê polînomiyan biweşînin. Encama vê gavê set e Z bi kêmanî pêk tê k polynomialên ku di gavê (1) de hatine afirandin.
-
Beşdar piştrast dikin ku nirxên ku ew dizanin pi (j) bi gelemperî ve hatî ragihandin re têkildar e pi(j)G. Piştî vê gavê Z tenê polynomialên ku ji bo wan bi taybetî têne şandin pi (j) bi gelemperî ve hatî ragihandin re têkildar e pi(j)G.
-
Her beşdar j pêkhateya wê ya taybet hesab dike p(j) wek hev pi(j) ji bo hemûyan i в Z. Her beşdar jî hemî nirxan hesab dike p(x)G wek hev pi(x)G ji bo hemû i в Z.
not bikin ku p(x) - bi rastî pirnomîlek e k-1, ji ber ku ew berhevoka kesane ye pi(x), ku her yek ji wan polînomîlek derece ye k-1. Dûv re, bala xwe bidin ku dema ku her beşdar j dizane p(j), agahiya wan tune ye p(x) bo x ≠ j. Bi rastî, ji bo hesabkirina vê nirxê, ew hewce ne ku her tiştî bizanibin pi(x), û heta ku beşdar j bi kêmanî yek ji pirnomîlên hilbijartî nizane, di derheqê wan de agahdariya têr tune p(x).
Ev tevahiya pêvajoya nifşa polînomî ye ku di beşa paşîn de hewce bû. Pêngavên 1, 2 û 4 li jor pêkanînek pir eşkere heye. Lê gava 3 ne ew qas piçûk e.
Bi taybetî, pêdivî ye ku em karibin wê şîfrekirî îspat bikin pi(j) bi rastî bi yên hatine weşandin re têkildar e pi(j)G. Ger em nikaribin îspat bikin, êrîşkar i dibe ku li şûna wê zibil bişîne pi(j) ji beşdaran re j, û beşdar j dê nikaribin nirxa rastîn bistînin pi (j), û dê nikaribe beşê wê yê taybet hesab bike.
Protokolek krîptografîk heye ku dihêle hûn peyamek zêde biafirînin delîli (j), wusa ku her beşdar, xwediyê hin nirxek e e, navîn delîl (j) и pi(j)G, dikare wê bi herêmî verast bike e - ew bi rastî pi (j), bi mifteya beşdaran ve hatî şîfre kirin j. Mixabin, mezinahiya delîlên weha pir mezin e, û ji ber ku pêdivî ye ku were weşandin O(nk) Delîlên weha ji bo vê armancê nayê bikar anîn.
Li şûna ku îspat bike pi(j) peyda dike pi(j)G em dikarin demek pir mezin di protokola hilberîna polînomî de veqetînin, ku tê de hemî beşdaran şîfreya wergirtî kontrol dikin. pi (j), û heke peyama deşîfrekirî bi raya giştî re têkildar nebe pi(j)G, ew delîlek krîptografîk diweşînin ku peyama şîfrekirî ya ku wan wergirtiye nerast e. Îspat bike ku peyam ne peyda dike beraz) pir hêsantir ji îsbatkirina ku ew li hev dike. Pêdivî ye ku were zanîn ku ev yek hewce dike ku her beşdar bi kêmanî carekê di dema ku ji bo afirandina delîlên weha hatî veqetandin de xuya bibe serhêl, û xwe dispêre vê texmînê ku heke ew delîlek weha biweşînin, ew ê di heman wextê diyarkirî de bigihîje hemî beşdarên din.
Ger di vê heyamê de beşdarek serhêl derneketibe, û bi kêmî ve pêkhateyek wî ya nerast hebe, wê hingê ew beşdarê taybetî dê nikaribe beşdarî hilberîna hejmarê ya din bibe. Lêbelê, heke bi kêmanî hebe, protokol dê hîn jî kar bike k beşdarên ku tenê hêmanên rast wergirtine an jî karîbûn di dema diyarkirî de delîlên xeletiyê bihêlin.
Delîlên rastbûna H_i
Beşa paşîn a ku dê were nîqaş kirin ev e ku meriv çawa rastbûna weşandinê îsbat dike Hez, ango ew Silav = p(i)H, bê vekirin p(i).
Bila ji bîr mekin ku nirxên H, G, p(i)G giştî û ji her kesî re tê zanîn. Operasyonê bistînin p(i) zanîn beraz и G jê re logarîtma veqetandî, an dlog, û em dixwazin îsbat bikin ku:
dlog(p(i)G, G) = dlog(Hi, H)
bê eşkerekirin p(i). Avakirinên ji bo delîlên weha hene, wek nimûne.
Bi vê sêwiranê re, her beşdar, bi Hi li gorî sêwiranê delîlek rast dişîne.
Dema ku jimareyek rasthatî were çêkirin, ew pir caran hewce dike ku ji hêla beşdaran ve ji bilî yên ku ew çêkirine were bikar anîn. Divê beşdarên weha, digel hejmarê, hemî bişînin Hi û delîlên têkildar.
Xwendevanek lêkolîner dikare bipirse: ji ber ku hejmara rasthatî ya dawî ye H0, û p(0)G - Ev agahdariya gelemperî ye, çima em ji bo her kesek delîlan hewce ne Hez, çima delîlek ku li şûna wê naşînim
dlog(p(0)G, G) = dlog(H0, H)
Pirsgirêk ev e ku delîlek wusa bi karanîna Protokola Schnorr nayê afirandin ji ber ku kes nirxê nizane p (0), ji bo afirandina delîlê pêwîst e, û ya din jî, tevahiya hilberînerê hejmarên rasthatî li ser vê rastiyê ye ku kes vê nirxê nizane. Ji ber vê yekê pêwîstî bi hemû nirxan heye Hi û delîlên wan ên kesane ji bo îsbatkirina rastdariyê H0.
Lêbelê, heke li ser xalên li ser kevokên elîptîk hin operasyon hebûn ku ji hêla semantîk ve dişibin pirjimariyê, belgeya rastbûnê ye. H0 dê bêkêmasî be, em ê bi tenê wê piştrast bikin
H0 G = p(0)G × H
Heke kulika hilbijartî piştgirî dike , ev delîl dixebite. Di vê rewşê de H0 ne tenê hilbera hilberînerek hejmarê rasthatî ye, ku dikare ji hêla her beşdarek ku dizane ve were verast kirin. G, H и p(0)G. H0 jî li ser peyama ku wekî tov hatî bikar anîn îmzeyek e, ku wê piştrast dike k и n beşdaran ev peyam îmze kirin. Bi vî awayî, eger tov - di protokola blokê de hash blokê ye, wê hingê H0 hem pir-îmzayek li ser blokê ye û hem jî hejmareke rasthatî ya pir baş e.
Di encamê de
Ev gotar beşek ji rêzek blogek teknîkî ye . NEAR protokol û platformek blokek e ku ji bo pêşkeftina serîlêdanên nenavendî bi giranî li ser asaniya pêşkeftinê û hêsaniya karanîna ji bo bikarhênerên dawîn e.
Koda protokolê vekirî ye, pêkanîna me di Rust de hatî nivîsandin, ew dikare were dîtin .
Hûn dikarin bibînin ka pêşkeftina NEAR çawa xuya dike û di IDE-ya serhêl de biceribînin .
Hûn dikarin hemû nûçeyên bi rûsî li ser bişopînin û di , û bi Îngilîzî di fermî de .
Demek nêzik te bibînim!
Source: www.habr.com