Hey Habr!
Π Ato amin'ity lahatsoratra ity dia niresaka momba ny antony mety ilaina ny mamorona isa kisendrasendra ho an'ny mpandray anjara izay tsy mifampatoky, inona no fepetra apetraka ho an'ny mpamokatra nomerao kisendrasendra toy izany, ary mandinika fomba roa amin'ny fampiharana azy ireo.
Amin'ity ampahany amin'ny lahatsoratra ity dia hijery akaiky kokoa ny fomba fiasa hafa mampiasa sonia tokonam-baravarana isika.
kriptografika kely
Mba hahatakarana ny fomba fiasan'ny sonia tokonam-baravarana dia mila mahazo kriptografika fototra kely ianao. Hampiasa hevitra roa isika: scalars, na isa tsotra, izay holazaintsika amin'ny litera kely (x, y) ary manondro ny curve elliptic, izay holazaintsika amin'ny litera lehibe.
Mba hahatakarana ny fototry ny sonia tokonam-baravarana dia tsy mila mahatakatra ny fomba fiasan'ny curve elliptic ianao, ankoatra ny zavatra fototra vitsivitsy:
-
Ny teboka amin'ny curve elliptic dia azo ampiana sy ampitomboina amin'ny scalar (dia manondro ny fampitomboana amin'ny scalar toy ny xG, na dia eo aza ny fanamarihana Gx matetika ampiasaina amin'ny literatiora). Ny vokatry ny fanampiana sy fampitomboana amin'ny scalar dia teboka iray amin'ny curve elliptic.
-
Tsy mahalala afa-tsy ny hevitra G ary ny vokatra amin'ny scalar xG tsy azo kajy x.
Hampiasa ny hevitry ny polynomial koa isika p(x) fiakarana k-1. Amin'ny ankapobeny dia hampiasa ity fananana polynomial manaraka ity isika: raha fantatsika ny sandany p(x) na inona na inona k samy hafa x (ary tsy manana fampahalalana bebe kokoa momba ny p(x)), afaka manao kajy isika p(x) ho an'ny hafa x.
Mahaliana fa ho an'ny polynomial rehetra p(x) ary teboka iray amin'ny curve Gmahafantatra ny dikany p(x)G na inona na inona k dikany samihafa x, afaka manao kajy koa isika p(x)G na inona na inona x.
Fampahalalana ampy handinihana ny antsipirihan'ny fomba fiasan'ny sonia tokonam-baravarana sy ny fomba fampiasana azy ireny hamoronana isa kisendrasendra.
Mpamorona laharana kisendrasendra amin'ny sonia tokonam-baravarana
Andeha atao hoe n te hamorona isa kisendrasendra ny mpandray anjara, ary tianay na iza na iza handray anjara k ampy tamin'izy ireo namokatra isa, fa ny mpanafika izay mifehy k- Ny mpandray anjara 1 na vitsy dia tsy afaka maminavina na mitaona ny isa vokarina.
Eritrereto hoe misy polynomial toy izany p(x) fiakarana k-1 izay fantatry ny mpandray anjara voalohany t (1), fantatry ny faharoa p(2), sy ny sisa (n-th mahalala p(n)). Heverintsika koa fa ho an'ny teboka voafaritra mialoha G fantatry ny rehetra p(x)G ho an'ny soatoavina rehetra x. Hiantso izahay p(i) "Component privΓ©e" iny mpandray anjara (satria ihany imahafantatra azy ny mpandray anjara faharoa), ary p(i)G "Component public" i-ny mpandray anjara (satria fantatry ny mpandray anjara rehetra). Araka ny tsaroanao, fahalalana p(i)G tsy ampy hamerenana p(i).
Mamorona polynomial toy izany ka izay ihany i-Ny mpandray anjara voalohany ary tsy nisy olon-kafa nahafantatra ny singa manokana - ity no ampahany sarotra sy mahaliana indrindra amin'ny protocol, ary hodinihintsika eto ambany. Amin'izao fotoana izao, andao atao hoe manana polynomial toy izany isika ary fantatry ny mpandray anjara rehetra ny singa manokana.
Ahoana no ahafahantsika mampiasa polynomial toy izany mba hamoronana isa kisendrasendra? Hanombohana dia mila tady izay mbola tsy nampiasaina ho fampidirana ho an'ny mpamokatra. Raha ny blockchain, ny hash amin'ny sakana farany h dia kandida tsara ho an'ny tsipika toy izany. Avelao ny mpandray anjara te hamorona isa kisendrasendra mampiasa h toy ny voa. Miova fo aloha ny mpandray anjara h mankany amin'ny teboka iray amin'ny curve amin'ny fampiasana asa efa voafaritra mialoha:
H = scalarToPoint(h)
Avy eo ny mpandray anjara tsirairay i kajy sy mamoaka Aho = p(i)H, inona no azony atao satria fantany p(i) sy H. Disclosure Htsy avelako hamerina ny singa manokana ny mpandray anjara hafa iny mpandray anjara, ary noho izany dia azo ampiasaina isaky ny sakana iray ny singa manokana iray. Noho izany, ny algorithm famokarana polynomial lafo vidy voalaza etsy ambany dia tsy maintsy tanterahina indray mandeha ihany.
rehefa k natao autopsie ny mpandray anjara Aho = p(i)H, afaka manao kajy ny rehetra Hx = p(x)H ho an'ny rehetra x noho ny fananana polynomial izay noresahinay tamin'ny fizarana farany. Amin'izao fotoana izao, ny mpandray anjara rehetra dia manao kajy H0 = p(0)H, ary ity no isa kisendrasendra vokatr'izany. Marihina fa tsy misy mahalala p(0), ary noho izany ny hany fomba kajy p(0)H β interpolation izany p(x)H, izay azo atao ihany rehefa k soatoavina p(i)H fantatra. Manokatra izay isa kely kokoa p(i)H tsy manome vaovao momba ny p(0)H.
Ny mpamokatra etsy ambony dia manana ny fananana rehetra tadiavintsika: ny mpanafika ihany no mifehy k-Ny mpandray anjara 1 na latsaka dia tsy manana fampahalalana na fiantraikany amin'ny famaranana, raha misy k ny mpandray anjara dia afaka manao kajy ny isan'ny vokatra, ary ny ampahany amin'ny k ny mpandray anjara dia ho tonga amin'ny vokatra mitovy foana ho an'ny voa iray ihany.
Misy olana iray nosorohanay tsara tetsy ambony. Mba hiasa ny interpolation dia zava-dehibe ny sandany Hi izay navoakan'ny mpandray anjara tsirairay i tena mitovy ihany p(i)H. Satria tsy misy afa-tsy i-Tsy fantatry ny mpandray anjara p(i), tsy misy afa-tsy i-tsy afaka manamarina izany ny mpandray anjara Hi tena kajy marina, ary tsy misy porofo kriptografika ny marina Hny mpanafika dia afaka mamoaka ny sandany toy ny Hi, ary miantraika amin'ny kisendrasendra ny vokatra avy amin'ny mpamokatra isa kisendrasendra:
Ny sanda samihafa amin'ny H_1 nalefan'ny mpandray anjara voalohany dia mitarika amin'ny H_0 vokatra hafa
Misy fomba roa farafahakeliny hanaporofoana ny fahamarinana Hi, handinika azy ireo isika rehefa avy mandinika ny taranaka polynomial.
Taranaka polynomial
Ao amin'ny fizarana farany dia nihevitra izahay fa manana polynomial toy izany p(x) fiakarana k-1 fa ny mpandray anjara i mahalala p(i), ary tsy misy olon-kafa manana vaovao momba io sanda io. Ao amin'ny fizarana manaraka dia mila izany koa isika amin'ny teboka voafaritra mialoha G fantatry ny rehetra p(x)G ho an'ny rehetra x.
Amin'ity fizarana ity dia hihevitra isika fa ny mpandray anjara tsirairay eo an-toerana dia manana fanalahidy manokana xi, mba hahafantaran'ny rehetra ny fanalahidin'ny daholobe mifanaraka amin'izany Xi.
Ny protocol generation polynomial iray dia toy izao manaraka izao:
-
Ny mpandray anjara tsirairay i eo an-toerana dia mamorona polynomial arbitraire pi(x) maridrefy k-1. Mandefa ny mpandray anjara tsirairay avy izy ireo j izay midika hoe pi(j), miafina amin'ny fanalahidin'ny daholobe Xj. Noho izany ihany i-faha ΠΈ j-faha fantatry ny mpandray anjara pi (j). Mpandray anjara i manambara ampahibemaso ihany koa pi(j)G ho an'ny rehetra j ΠΎΡ 1 Π΄ΠΎ k inclusive.
-
Ny mpandray anjara rehetra dia mampiasa marimaritra iraisana hisafidianana k mpandray anjara izay mampiasa polynomial. Koa satria mety ho ivelan'ny Internet ny mpandray anjara sasany, dia tsy afaka miandry ny rehetra izahay n ny mpandray anjara dia hamoaka polynomials. Ny vokatr'ity dingana ity dia napetraka Z ahitana farafaharatsiny k polynomial noforonina amin'ny dingana (1).
-
Ny mpandray anjara dia manome antoka fa ny soatoavina fantany pi(j) mifanaraka amin'ny fanambarana ampahibemaso pi(j)G. Aorian'ity dingana ity Z polynomial ihany no nampitaina manokana pi(j) mifanaraka amin'ny fanambarana ampahibemaso pi(j)G.
-
Ny mpandray anjara tsirairay j kajy ny singa manokana p(j) ho fitambarana pi(j) ho an'ny rehetra i Π² Z. Ny mpandray anjara tsirairay koa dia manisa ny soatoavina rehetra p(x)G ho fitambarana pi(x)G ho an'ny i Π² Z.
Mariho fa p(x) - tena polynomial izany k-1, satria ny fitambaran'ny tsirairay pi(x), izay samy misy polynomial de digree k-1. Avy eo, mariho fa ny mpandray anjara tsirairay j mahalala p(j), tsy manana vaovao momba izany izy ireo p(x) ho an'ny x β j. Raha te hanao kajy io sanda io tokoa izy ireo dia mila mahafantatra ny zava-drehetra pi(x), ary raha mbola ny mpandray anjara j tsy mahafantatra na iray aza amin'ireo polynomial voafantina, tsy manana fampahalalana ampy momba p(x).
Izany no dingana famokarana polynomial manontolo izay ilaina amin'ny fizarana farany. Ny dingana 1, 2 ary 4 etsy ambony dia manana fampiharana mazava tsara. Saingy ny dingana 3 dia tsy dia kely loatra.
Amin'ny ankapobeny, mila afaka manaporofo isika fa voafehy pi(j) tena mifanitsy amin'ireo navoaka pi(j)G. Raha tsy afaka manaporofo izany isika, ilay mpanafika i mety mandefa fako kosa pi(j) ho mpandray anjara j, ary mpandray anjara j tsy ho azo ny tena dikany pi(j), ary tsy ho afaka kajy ny singa manokana.
Misy protocole cryptographic ahafahanao mamorona hafatra fanampiny porofoi(j), ka misy mpandray anjara, manana sanda e, Π° ΡΠ°ΠΊΠΆΠ΅ porofo (j) ΠΈ pi(j)G, afaka manamarina izany eo an-toerana e - tena izy pi(j), encrypted miaraka amin'ny fanalahidin'ny mpandray anjara j. Indrisy anefa, ny haben'ny porofo toy izany dia lehibe tsy mampino, ary nomena fa ilaina ny famoahana O(nk) Tsy azo ampiasaina amin'izany tanjona izany ny porofo toy izany.
Raha tokony hanaporofo izany pi (j) mifanandrify amin'ny pi(j)G dia afaka manokana fotoana lava be ao amin'ny protocol generation polynomial, izay ahafahan'ny mpandray anjara rehetra manamarina ny voaray pi(j), ary raha tsy mifanandrify amin'ny besinimaro ny hafatra voavaha pi(j)G, namoaka porofo kriptografika izy ireo fa diso ny hafatra voarakotra azony. Porofoy fa ny hafatra tsy mifanandrify amin'ny pi(G) mora kokoa noho ny manaporofo fa mifanaraka. Marihina fa izany dia mitaky ny mpandray anjara tsirairay hiseho an-tserasera farafahakeliny indray mandeha mandritra ny fotoana voatondro hamoronana porofo toy izany, ary miankina amin'ny fiheverana fa raha mamoaka porofo toy izany izy ireo dia ho tonga amin'ny mpandray anjara hafa rehetra ao anatin'ny fotoana voatondro mitovy.
Raha toa ka tsy niseho an-tserasera ny mpandray anjara iray nandritra io vanim-potoana io, ary nanana singa iray diso izy, dia tsy afaka mandray anjara amin'ny famoronana isa fanampiny io mpandray anjara manokana io. Na izany aza, ny protocol dia mbola miasa raha misy farafaharatsiny k mpandray anjara izay na vao nahazo ny singa marina na nahavita nametraka porofon'ny tsy mety tao anatin'ny fotoana voatondro.
Porofon'ny fahamarinan'ny H_i
Ny ampahany farany mbola hodinihina dia ny fomba hanaporofoana ny fahamarinan'ny navoaka Hi, izany hoe Aho = p(i)H, tsy misy fisokafana p(i).
Aoka hotsaroantsika fa ny soatoavina H, G, p(i)G ampahibemaso sy fantatry ny rehetra. Raiso fandidiana p(i) Tsy Mahalala Tsara p(i)G ΠΈ G antsoina hoe logarithm discrete, na dlog, ary tianay hanaporofo fa:
dlog(p(i)G, G) = dlog(Hi, H)
tsy misy fampahafantarana p(i). Misy fanorenana ho an'ny porofo toy izany, ohatra.
Miaraka amin'ity famolavolana ity, ny mpandray anjara tsirairay, miaraka amin'ny Hi mandefa porofon'ny fahamarinana araka ny famolavolana.
Raha vantany vao voaforona ny isa kisendrasendra dia matetika mila ampiasain'ny mpandray anjara ankoatra ireo namorona azy io. Ny mpandray anjara toy izany, miaraka amin'ny isa, dia tsy maintsy mandefa ny rehetra Hi ary porofo mifandray.
Mety hanontany ny mpamaky iray manontany hoe: satria ny isa kisendrasendra farany dia H0, ary p(0)G β Fampahafantarana ho an'ny daholobe izany, nahoana isika no mila porofo ho an'ny tsirairay Hi, maninona raha mandefa porofo fa
dlog(p(0)G, G) = dlog(H0, H)
Ny olana dia ny porofo toy izany dia tsy azo noforonina amin'ny alΓ lan'ny Schnorr Protocol satria tsy misy mahalala ny sandany t (0), ilaina mba hamoronana ny porofo, ary ny tena zava-dehibe, ny isa kisendrasendra manontolo mpamokatra dia mifototra amin'ny zava-misy fa tsy misy mahalala izany sanda izany. Noho izany dia ilaina ny manana ny soatoavina rehetra Hi ary ny porofon'izy ireo manokana hanaporofoana ny fahamarinany H0.
Na izany aza, raha misy hetsika sasany amin'ny teboka amin'ny curve elliptic izay mitovy amin'ny fampitomboana, ny porofon'ny marina H0 ho tsinontsinona, ataontsika antoka fotsiny izany
H0 Γ G = p(0)G Γ H
Raha manohana ny curve voafantina , mandaitra io porofo io. Raha izany dia H0 dia tsy ny vokatra avy amin'ny mpamokatra isa kisendrasendra fotsiny, izay azo hamarinin'ny mpandray anjara rehetra mahalala G,H ΠΈ p(0)G. H0 koa dia sonia amin'ny hafatra izay nampiasaina ho voa, manamafy izany k ΠΈ n nanao sonia ity hafatra ity ny mpandray anjara. Noho izany, raha voa - dia ny hash ny sakana ao amin'ny protocol blockchain, avy eo H0 dia sady sonia marobe amin'ny sakana no isa kisendrasendra tena tsara.
Ho famaranana
Ity lahatsoratra ity dia ampahany amin'ny andiany bilaogy teknika . NEAR dia protocole blockchain sy sehatra ho an'ny fampivoarana ny rindranasa itsinjaram-pahefana miaraka amin'ny fanamafisana ny fanamorana ny fampivoarana sy ny fampiasana ho an'ny mpampiasa farany.
Ny kaody protocol dia misokatra, ny fampiharana ataontsika dia voasoratra amin'ny Rust, azo jerena .
Azonao atao ny mahita ny fivoaran'ny NEAR ary manao fanandramana amin'ny IDE an-tserasera .
Azonao atao ny manaraka ny vaovao rehetra amin'ny teny Rosiana amin'ny ary ao , ary amin'ny teny anglisy amin'ny ofisialy .
Mandra-pihaona!
Source: www.habr.com