Nahana ka boemo boo u hlokang ho boloka polokelo ea banka. E nkoa e sa khonehe ka ho feletseng ntle le senotlolo, seo u se fuoang letsatsing la pele la mosebetsi. Sepheo sa hau ke ho boloka senotlolo ka mokhoa o sireletsehileng.
Ha re re u etsa qeto ea ho boloka senotlolo ho uena ka linako tsohle, ho fana ka phihlello ea polokelo ha ho hlokahala. Empa u tla hlokomela ka potlako hore tharollo e joalo ha e sebetse hantle, hobane ho ba teng ha hao 'meleng hoa hlokahala nako le nako ha u bula polokelo. Ho thoe’ng ka phomolo eo u neng u e tšepisitsoe? Ho phaella moo, potso e tšosa le ho feta: ho thoe'ng haeba u lahlehetsoe ke senotlolo sa hau feela?
U hopotse matsatsi a hau a phomolo, u etsa qeto ea ho etsa kopi ea senotlolo ebe u e beha ho mosebeletsi e mong. Leha ho le joalo, ua utloisisa hore sena le sona ha se hantle. Ka ho imena habeli palo ea linotlolo, u boetse u habeli menyetla ea ho utsoa linotlolo.
Ka ho tsieleha, u senya koporo ebe u etsa qeto ea ho arola senotlolo sa pele ka halofo. Joale, u ne u tla nahana hore batho ba babeli ba tšeptjoang ba nang le likhechana tsa bohlokoa ba tla tlameha ho ba teng ho bokella senotlolo le ho bula vault. Sena se bolela hore lesholu le lokela ho utsoa likotoana tse peli, e leng ntho e boima ka makhetlo a mabeli ho feta ho utsoa senotlolo se le seng. Leha ho le joalo, haufinyane u hlokomela hore morero ona ha o molemo haholo ho feta senotlolo se le seng, hobane haeba motho a lahleheloa ke halofo ea senotlolo, senotlolo se feletseng se ke ke sa fumanoa.
Bothata bo ka rarolloa ka letoto la linotlolo le linotlolo tse eketsehileng, empa mokhoa ona o tla hloka kapele много linotlolo le linotlolo. U etsa qeto ea hore moralo o nepahetseng e tla ba ho arolelana senotlolo e le hore ts'ireletso e se ke ea itšetleha ka ho felletseng ho motho a le mong. U boetse u etsa qeto ea hore ho tlameha ho be le moeli oa palo ea likhechana e le hore haeba sekhechana se le seng se lahleha (kapa haeba motho a ea phomolong), senotlolo sohle se lula se sebetsa.
Mokhoa oa ho arolelana lekunutu
Mofuta ona oa leano la bohlokoa la taolo o ile oa nahanoa ke Adi Shamir ka 1979 ha a phatlalatsa mosebetsi oa hae . Sengoliloeng se hlalosa ka bokhutšoanyane se bitsoang 
threshold scheme bakeng sa ho arola ka nepo boleng ba lekunutu (joalo ka senotlolo sa cryptographic) ho likarolo. Joale, neng le ha feela bonyane ho tswa likarolo li bokane, u ka tsosolosa sephiri habonolo .
Ho ea ka pono ea ts'ireletso, thepa ea bohlokoa ea morero ona ke hore mohlaseli ha aa lokela ho tseba letho ntle le haeba bonyane a na le likarolo. Esita le boteng likarolo ha lia lokela ho fana ka tlhahisoleseling efe kapa efe. Re bitsa thepa ena tshireletso ya semantic.
Polynomial interpolation
Sekema sa Shamir threshold e ahiloeng ho potoloha mohopolo polynomial interpolation. Haeba u sa tloaelane le khopolo ena, ha e le hantle e bonolo haholo. Ha e le hantle, haeba u kile ua toroea lintlha kerafong ebe u li kopanya le mela kapa li-curve, u se u li sebelisitse!
Ka lintlha tse peli u ka hula palo e sa lekanyetsoang ea polynomials ea tekanyo ea 2. Ho khetha e le 'ngoe feela ho bona, u hloka ntlha ea boraro. Setšoantšo:
Nahana ka polynomial e nang le degree ea pele, . Haeba u batla ho rala tšebetso ena kerafong, u hloka lintlha tse kae? Ho lokile, rea tseba hore ona ke tšebetso ea linear e etsang mola ka hona e hloka bonyane lintlha tse peli. E latelang, nahana ka mosebetsi oa polynomial o nang le degree ea bobeli, . Ona ke ts'ebetso ea quadratic, kahoo bonyane lintlha tse tharo lia hlokahala ho rala kerafo. Ho thoe'ng ka polynomial e nang le degree ea boraro? Bonyane lintlha tse 'nè. Le joalo-joalo.
Ntho e hlileng e pholileng ka thepa ena ke hore, ho fanoe ka tekanyo ea mosebetsi oa polynomial le bonyane lintlha, re ka fumana lintlha tse eketsehileng bakeng sa mosebetsi ona oa polynomial. Re bitsa extrapolation ea lintlha tsena tse eketsehileng polynomial interpolation.
Ho etsa lekunutu
E ka 'na eaba u se u hlokometse hore ke hona moo morero o bohlale oa Shamir o kenang teng. Ha re bue lekunutu la rona - sena ke . Re ka reteleha ho isa ntlheng e hodima kerafo le ho tla le mosebetsi oa polynomial o nang le degree , e khotsofatsang ntlha ena. A re hopoleng seo e tla ba monyako oa likhechana tse hlokahalang, kahoo haeba re beha moeli ho likhechana tse tharo, re tlameha ho khetha mosebetsi oa polynomial ka tekanyo ea bobeli.
Polynomial ea rona e tla ba le foromo kae и - linomoro tse ntle tse khethiloeng ka mokhoa o sa reroang. Re ntse re haha polynomial e nang le degree , moo coefficient ea mahala - Sena ke sephiri sa rona , le bakeng sa e ’ngoe le e ’ngoe ea tse latelang ho na le coefficient e ntle e khethiloeng ka mokhoa o sa reroang. Haeba re khutlela mohlaleng oa pele mme re nka hore , ebe re fumana mosebetsi .
Ka nako ena re ka hlahisa likhechana ka ho hokahanya linomoro tse ikhethang ho kae (hobane ke sephiri sa rona). Mohlaleng ona, re batla ho aba likhechana tse 'ne ka moeli oa tse tharo, kahoo re hlahisa lintlha ka mokhoa o sa reroang. ’me u romele ntlha e le ’ngoe ho e mong le e mong oa batho ba bane ba tšepahalang, bahlokomeli ba senotlolo. Re boetse re tsebisa batho seo , kaha sena se nkoa e le boitsebiso ba sechaba 'me sea hlokahala bakeng sa ho hlaphoheloa .
Ho fumana lekunutu
Re se re buisane ka mohopolo oa ho kenella ha polynomial le hore na o theha moralo oa Shamir joang. . Ha ba bang ba bararo ho ba bane ba trustee batla busetsa , li hloka feela ho fapanyetsana ka lintlha tsa eona tse ikhethang. Ho etsa sena, ba ka khetha lintlha tsa bona 'me u bale Lagrange interpolation polynomial u sebelisa foromo e latelang. Haeba lenaneo le hlakile ho uena ho feta lipalo, joale pi e hlile e sebetsa for, e atisang liphetho tsohle, 'me sigma e for, e eketsang tsohle.
ka re ka e rarolla tjena mme ra khutlisa ts'ebetso ea rona ea mantlha ea polynomial:
Kaha re tseba seo , ho hlaphoheloa e entsoe habonolo:
Ho sebelisa lipalo tse felletseng tse sa bolokehang
Leha re sebelisitse mohopolo oa mantlha oa Shamir ka katleho , re sala le bothata boo re sa kang ra bo hlokomoloha ho fihlela joale. Mosebetsi oa rona oa polynomial o sebelisa lipalo tse felletseng tse sa bolokehang. Hlokomela hore sebakeng se seng le se seng sa tlatsetso eo mohlaseli a e fumanang kerafong ea ts'ebetso ea rona, ho na le menyetla e fokolang bakeng sa lintlha tse ling. U ka bona sena ka mahlo a hau ha u rera palo e ntseng e eketseha ea lintlha bakeng sa mosebetsi oa polynomial u sebelisa lipalo tse felletseng. Sena ha se na thuso ho sepheo sa rona sa ts'ireletso se boletsoeng, hobane mohlaseli ha aa lokela ho tseba letho ho fihlela bonyane ba na le likaroloana.
Ho bontša hore na potoloho ea lipalo e fokola hakae, nahana ka boemo boo ho bona mohlaseli a ileng a fumana lintlha tse peli. mme o tseba lesedi la setjhaba seo . Ho tsoa boitsebisong bona a ka khona ho nahana , e lekanang le tse peli, 'me u kenye litekanyetso tse tsejoang ka har'a foromo и .
Joale mohlaseli a ka fumana , ho bala :
Kaha re hlalositse joalo ka lipalo tse ntle tse khethiloeng ka mokhoa o sa reroang, ho na le palo e lekanyelitsoeng ea ho khoneha . Ka ho sebelisa boitsebiso bona, mohlaseli a ka etsa qeto , kaha eng kapa eng e kholo ho feta 5 e tla etsa mpe. Sena se bonahala e le 'nete kaha re entse qeto
Joale mohlaseli a ka bala litekanyetso tse ka khonehang ho nkela sebaka в :
Ka likhetho tse fokolang bakeng sa hoa hlaka hore na ho bonolo hakae ho khetha le ho hlahloba litekanyetso . Ho na le likhetho tse hlano feela mona.
Ho rarolla bothata ka lipalo tse sa bolokehang
Ho felisa ts'oaetso ena, Shamir o fana ka maikutlo a ho sebelisa lipalo tsa modular, ho nkela sebaka mabapi le kae и - sehlopha sa linomoro tsohle tsa mantlha.
Ha re hopole ka potlako hore na modular arithmetic e sebetsa joang. Oache e nang le matsoho ke khopolo e tloaelehileng. O sebelisa oache ke hore . Hang ha letsoho la hora le feta leshome le metso e mmedi, le kgutlela ho nngwe. Ntho e thahasellisang ea tsamaiso ena ke hore feela ka ho sheba oache, re ke ke ra fumana hore na letsoho la hora le entse liphetoho tse kae. Leha ho le joalo, haeba re tseba hore letsoho la hora le fetile ka makhetlo a 12 ka makhetlo a mane, re ka tseba ka ho feletseng palo ea lihora tse fetileng re sebelisa mokhoa o bonolo. kae ke karohano ea rona (mona ), ke coefficient (ke makhetlo a makae karohano e kenang nomorong ea mantlha ntle le masalla, mona ), le ke karolo e setseng, eo hangata e khutlisetsang mohala oa modulo (mona ). Ho tseba litekanyetso tsena kaofela ho re lumella ho rarolla equation bakeng sa , empa haeba re lahleheloa ke coefficient, re ke ke ra khona ho tsosolosa boleng ba pele.
Re ka bonts'a hore na sena se ntlafatsa ts'ireletso ea morero oa rona joang ka ho sebelisa leano ho mohlala oa rona o fetileng le ho sebelisa . Mosebetsi oa rona o mocha oa polynomial , le lintlha tse ncha . Hona joale bahlokomeli ba ka sehloohong ba ka boela ba sebelisa tlhaloso ea polynomial ho tsosolosa mosebetsi oa rona, feela lekhetlong lena ts'ebetso ea ho eketsa le ho atisa ho tsamaea le ho fokotsa modulo. (bap ).
Ha re sebelisa mohlala ona o mocha, ha re nke hore mohlaseli o ithutile lintlha tse peli ho tsena tse ncha, , le litaba tsa sechaba . Lekhetlong lena, mohlaseli, ho itšetlehile ka boitsebiso bohle boo a nang le bona, o hlahisa mesebetsi e latelang, hokae ke sete ea kaofela positive integers, le e emela modulus coefficient .
Joale mohlaseli oa rona o fumana hape , ho bala :
Ebe o leka hape ho nkela sebaka в :
Lekhetlong lena o na le bothata bo tebileng. Foromo e haellang , и . Kaha ho na le palo e sa lekanyetsoang ea metsoako ea mefuta ena, a ke ke a fumana boitsebiso leha e le bofe bo eketsehileng.
Mehopolo ea Tšireletso
Morero oa ho arolelana lekunutu oa Shamir o fana ka maikutlo tšireletseho ho tsoa ntlheng ea teori ea tlhahisoleseling. Sena se bolela hore lipalo li hanana le motho ea hlaselang ea nang le matla a sa lekanyetsoang a komporo. Leha ho le joalo, potoloho ena e ntse e na le litaba tse ’maloa tse tsejoang.
Ka mohlala, morero oa Shamir ha o thehe likotoana tse lokelang ho hlahlojoa, ke hore, batho ba ka hlahisa likhechana tsa bohata ka bolokolohi 'me ba kena-kenana le ho tsosolosoa ha sephiri se nepahetseng. Mohlokomeli ea tletseng bora ea nang le boitsebiso bo lekaneng a ka ba a hlahisa sekhechana se seng ka ho se fetola ka boikhethelo ba hao. Bothata bona bo rarolloa ka ho sebelisa merero e netefalitsoeng ea ho arolelana lekunutu, joalo ka morero oa Feldman.
Bothata bo bong ke hore bolelele ba sekhechana leha e le sefe bo lekana le bolelele ba sephiri se tsamaisanang le sona, kahoo bolelele ba sephiri bo bonolo ho tseba. Bothata bona bo ka rarolloa ka mokhoa o sa reng letho padding sephiri se nang le dinomoro tse sa tsitsang ho fihlela bolelele bo tsitsitseng.
Qetellong, ke habohlokoa ho hlokomela hore mathata a rona a tšireletso a ka fetela ka nģ'ane ho moralo ka boeona. Bakeng sa lits'ebetso tsa 'nete tsa lefats'e, hangata ho na le ts'okelo ea litlhaselo tsa liteishene tse lehlakoreng moo mohlaseli a lekang ho ntša lintlha tsa bohlokoa ho tsoa nakong ea ts'ebetso ea kopo, caching, ho oa, joalo-joalo. Haeba sena se tšoenyehile, ho lokela ho nahanoa ka hloko nakong ea nts'etsopele ea ho sebelisa mehato ea ts'ireletso joalo ka ts'ebetso le ts'ebetso ea nako e sa khaotseng, ho thibela mohopolo hore o se ke oa bolokoa ho disk, le lintlha tse ling tse 'maloa tse fetang boholo ba sengoloa sena.
Tsebiso
mabapi le Ho na le pontšo e kopanetsoeng ea morero oa ho arolelana lekunutu oa Shamir. Pontšo e thehiloeng laebraring , eo ka boeona e leng kou ea JavaScript ea lenaneo le tsebahalang . Hlokomela hore ho bala lipalo tse kholo , и ho ka nka nako.
Source: www.habr.com