Cinga ngemeko apho kufuneka ukhusele ivault yebhanki. Kuthathwa njengento engenakuthinteleka ngaphandle kwesitshixo, osinikwa ngosuku lokuqala lomsebenzi. Injongo yakho kukugcina ngokukhuselekileyo isitshixo.

Masithi uthatha isigqibo sokugcina isitshixo kuwe ngamaxesha onke, ukunika ukufikelela kwindawo yokugcina njengoko kufuneka. Kodwa uya kuqonda ngokukhawuleza ukuba isisombululo esinjalo asilinganisi kakuhle ekusebenzeni, kuba ubukho bakho bomzimba bufunekayo rhoqo xa uvula indawo yokugcina. Kuthekani ngeholide owawuthenjiswe ngayo? Ukongeza, lo mbuzo uyoyikeka ngakumbi: kuthekani ukuba ulahlekelwe isitshixo sakho kuphela?

Ngeholide yakho engqondweni, uthatha isigqibo sokwenza ikopi yesitshixo kwaye unikezele komnye umsebenzi. Nangona kunjalo, uyaqonda ukuba oku akufanelekile. Ngokuphinda kabini inani lezitshixo, uphinda kabini amathuba okubiwa kwezitshixo.

Ngokuphelelwa lithemba, utshabalalisa ikopi kwaye uthathe isigqibo sokwahlula isitshixo sokuqala phakathi. Ngoku, ungacinga ukuba abantu ababini abathembekileyo abanamaqhekeza abalulekileyo kuya kufuneka babekho ngokwasemzimbeni ukuze baqokelele isitshixo kwaye bavule ivault. Oku kuthetha ukuba isela kufuneka libe iziqwenga ezibini, nto leyo enzima ngokuphindwe kabini kunokweba isitshixo esinye. Nangona kunjalo, ngokukhawuleza uyaqonda ukuba esi sikimu asingcono kakhulu kunesitshixo esinye, kuba ukuba umntu ulahlekelwa isiqingatha sesitshixo, isitshixo esipheleleyo asikwazi ukufunyanwa.

Ingxaki ingasombululwa ngoluhlu lwezitshixo ezongezelelweyo kunye nezitshixo, kodwa le ndlela iya kufuna ngokukhawuleza много izitshixo kunye nezitshixo. Uthatha isigqibo sokuba uyilo olufanelekileyo luya kuba kukwabelana ngesitshixo ukuze ukhuseleko lungathembeli ngokupheleleyo kumntu omnye. Kwakhona ugqiba ekubeni kufuneka kubekho umqobo wenani leeqhekeza ukuze ukuba isiqwenga esinye silahlekile (okanye ukuba umntu uya ekhefini), isitshixo sonke sihlala sisebenza.

Indlela yokwabelana ngemfihlo

Olu hlobo lwesikimu solawulo oluphambili lwalucingelwa ngu-Adi Shamir kwi-1979 xa epapasha umsebenzi wakhe "Ukwabelana njani ngeMfihlo". Eli nqaku licacisa ngokufutshane oko kubizwa ngokuba ithreshold scheme yokwahlula ixabiso eliyimfihlo (elifana neqhosha le-cryptographic) kwi iinxalenye. Emva koko, nini kwaye kuphela xa ubuncinane из iinxalenye zihlanganiswe, unokubuyisela ngokulula imfihlo .

Ukusuka kumbono wokhuseleko, ipropati ebalulekileyo yesi sikimu kukuba umhlaseli akafanele azi nantoni na ngaphandle kokuba ubuncinane iinxalenye. Nobukho amalungu akufuneki anike naluphi na ulwazi. Siyibiza le propati ukhuseleko lwesemantic.

I-polynomial interpolation

Iskimu se-Shamir threshold yakhiwe malunga nombono i-polynomial interpolation. Ukuba awuqhelananga nale ngcamango, ilula kakhulu. Enyanisweni, ukuba ukhe wazoba amanqaku kwigrafu waza wawadibanisa nemigca okanye iigophe, sele usebenzile!

Ngamanqaku amabini unokuzoba inani elingenamkhawulo weepolynomials zesidanga 2. Ukukhetha enye kuphela kubo, udinga inqaku lesithathu. Umfanekiso: Wikipedia

Cinga ngepolynomial enedigri yokuqala, . Ukuba ufuna ukucwangcisa lo msebenzi kwigrafu, mangaphi amanqaku owafunayo? Kulungile, siyazi ukuba lo ngumgca womsebenzi owenza umgca kwaye udinga amanqaku amabini ubuncinane. Okulandelayo, qwalasela umsebenzi wepolynomial kunye nesidanga sesibini, . Lo ngumsebenzi wequadratic, ngoko ke ubuncinane amanqaku amathathu ayafuneka ukwenza igrafu. Kuthekani ngepolynomial enedigri yesithathu? Ubuncinci amanqaku amane. Kwaye njalo njalo njalo.

Eyona nto ipholileyo malunga nale propati kukuba, ngokunikezelwa kweqondo lomsebenzi we-polynomial kwaye ubuncinci amanqaku, sinokufumana amanqaku ongezelelweyo kulo msebenzi wepolynomial. Sibiza i-extrapolation yala manqaku ongezelelweyo i-polynomial interpolation.

Ukwenza imfihlo

Usenokuba sele uqaphele ukuba kulapho iqhinga likaShamir elikrelekrele lingena khona. Masithethe imfihlo yethu - yi le . Sinokujika ukuya kwindawo kwigrafu kwaye uze nomsebenzi wepolynomial kunye nesidanga , eyanelisayo le ngongoma. Masikhumbule oko iya kuba ngumda wethu wamaqhekeza afunekayo, ngoko ke ukuba sibeka umda kwiiqhekeza ezintathu, kufuneka sikhethe umsebenzi wepolynomial kunye nesidanga sesibini.

Ipolynomi yethu iya kuba nefom phi и — iinombolo ezichanekileyo ezikhethwe ngokungakhethiyo. Sakha ipolynomial enedigri , apho i-coefficient yamahhala  - Le mfihlelo yethu , kwaye nganye kwezi zilandelayo Imiqathango kukho i-coefficient ye-positive ekhethwe ngokungakhethiyo. Ukuba sibuyela kumzekelo wokuqala kwaye sicinge ukuba , ngoko sifumana umsebenzi .

Kweli nqanaba sinokuvelisa amaqhekeza ngokudibanisa amanani awodwa kwi phi (kuba yimfihlo yethu). Kulo mzekelo, sifuna ukusasaza iziqwenga ezine ngomda wesithathu, ngoko ke sivelisa ngokungenamkhethe amanqaku. kwaye uthumele inqaku elinye kumntu ngamnye kubantu abane abathembekileyo, abagcini besitshixo. Kwakhona siyabazisa abantu oko , ekubeni oku kuthathwa njengolwazi lukawonke-wonke kwaye luyimfuneko ekubuyiseleni kwakhona .

Ukufumana kwakhona imfihlelo

Sele sixubushe ingqikelelo yepolynomial interpolation kunye nendlela ephantsi kweskim somda we-Shamir. . Xa nabaphi na abathathu kwabane trustee bafuna ukubuyisela , zifuna nje ukutolika enamanqaku ayo awodwa. Ukwenza oku, banokumisela iingongoma zabo kwaye ubale iLagrange interpolation polynomial usebenzisa le fomula ilandelayo. Ukuba udweliso lwenkqubo lucace ngakumbi kuwe kunemathematika, ngoko ke i-pi ingumsebenzi for, ephindaphinda zonke iziphumo, kwaye sigma yi for, eyongeza yonke into.

e singayisombulula ngolu hlobo kwaye sibuyisele umsebenzi wethu wokuqala wepolynomial:

Kuba siyayazi loo nto , ukuchacha kwenziwe ngokulula:

Ukusebenzisa i-arithmetic engakhuselekanga

Nangona sisebenzise ngempumelelo ingcamango esisiseko kaShamir , sishiyeke nengxaki esingakhange siyihoye kude kube ngoku. Umsebenzi wethu wepolynomial usebenzisa i-arithmetic epheleleyo engakhuselekanga. Qaphela ukuba kwindawo nganye eyongezelelweyo umhlaseli ayifumanayo kwigrafu yomsebenzi wethu, kukho amathuba ambalwa kwamanye amanqaku. Ungakubona oku ngamehlo akho xa uceba inani elonyukayo lamanqaku omsebenzi wepolynomial usebenzisa inani elipheleleyo le-arithmetic. Oku akunamveliso kwinjongo yethu yokhuseleko echaziweyo, kuba umhlaseli kufuneka azi nto kwaphela de abenobuncinci amaqhekeza.

Ukubonisa indlela ebuthathaka ngayo i-integer arithmetic circuit, cinga ngemeko apho umhlaseli wafumana amanqaku amabini. kwaye uyalwazi ulwazi loluntu ukuba . Ngolu lwazi anokuthi agqibe , ilingana nezimbini, kwaye iplagi kumaxabiso aziwayo kwifomula и .

Umhlaseli angafumana ke , ukubala :

Ekubeni siye sachaza njengeenombolo ezichanekileyo ezikhethwe ngokungakhethiyo, kukho inani eliqingqiweyo elinokwenzeka . Ukusebenzisa olu lwazi, umhlaseli unokugqiba , kuba nantoni na enkulu kune-5 iya kwenza embi. Oku kubonakala kuyinyani kuba sizimisele

Umhlaseli unokubala amaxabiso anokwenzeka , endaweni в :

Ngeenketho eziqingqiweyo ze kuyacaca ukuba kulula kangakanani ukukhetha nokujonga amaxabiso . Kukho iindlela ezintlanu kuphela apha.

Ukusombulula ingxaki ngezibalo ezingakhuselekanga

Ukuphelisa obu buthathaka, u-Shamir ucebisa ukusebenzisa i-arithmetic yemodyuli, ukubuyisela phezu phi и — iseti yawo onke amanani aphambili.

Masikhumbule ngokukhawuleza ukuba i-arithmetic yemodyuli isebenza njani. Iwotshi enezandla yinto eqhelekileyo. Usebenzisa iwotshi leyo . Nje ukuba isandla seyure sidlule kwishumi elinesibini, sibuyela kwenye. Ipropathi enomdla yale nkqubo kukuba ngokujonga nje iwotshi, asinakukwazi ukufumanisa ukuba zingaphi iinguqu ezenziwe yiyure. Nangona kunjalo, ukuba siyazi ukuba isandla seyure sidlulile i-12 amaxesha amane, sinokugqiba ngokupheleleyo inani leeyure ezidlulile usebenzisa ifomula elula. phi  ngumahluli wethu (apha ),  ngumlingani (kangaphi xa isahluli singena kwinani loqobo ngaphandle kwentsalela, apha ), kunye  yintsalela, eqhele ukubuyisela umnxeba womsebenzisi wemodulo (apha ). Ukwazi onke la maxabiso kusivumela ukuba sisombulule i-equation , kodwa ukuba siyayiphosa i-coefficient, asisoze sikwazi ukubuyisela ixabiso lokuqala.

Sinokubonisa indlela oku kuphucula ngayo ukhuseleko lwenkqubo yethu ngokusebenzisa inkqubo kumzekelo wethu wangaphambili kunye nokusebenzisa . Umsebenzi wethu omtsha wepolynomial , kunye namanqaku amatsha . Ngoku abagcini abaphambili banokuphinda basebenzise i-polynomial interpolation ukwakha kwakhona umsebenzi wethu, ngeli xesha kuphela ukongezwa kunye nokusebenza kophindaphindo kufuneka kukhatshwe kukuncitshiswa kwemodyuli. (umz ).

Sisebenzisa lo mzekelo mtsha, masicinge ukuba umhlaseli ufunde ezimbini kula manqaku matsha, , kunye nolwazi loluntu . Ngeli xesha, umhlaseli, ngokusekelwe kulo lonke ulwazi analo, uvelisa imisebenzi elandelayo, apho  yiseti yazo zonke ii-positive integers, kunye imele imodyuli yomlinganiso .

Ngoku umhlaseli wethu ufumana kwakhona , ukubala :

Emva koko uyazama kwakhona , endaweni в :

Ngesi sihlandlo unengxaki enzulu. Amaxabiso alahlekileyo efomula , и . Ekubeni kukho inani elingapheliyo lokudityaniswa kwezi ziguquko, akakwazi ukufumana naluphi na ulwazi olongezelelweyo.

Iingqwalasela zoKhuseleko

Icebo likaShamir lokwabelana ngokufihlakeleyo licebisa ukhuseleko kwimbono yethiyori yolwazi. Oku kuthetha ukuba imathematika ixhathisa nkqu nomhlaseli onamandla angenamkhawulo wekhompyutha. Nangona kunjalo, isekethe isenemiba emininzi eyaziwayo.

Ngokomzekelo, iskimu sikaShamir asidali amaqhekeza kufuneka ahlolwe, oko kukuthi, abantu banokubonisa ngokukhululekileyo amaqhekeza omgunyathi kwaye baphazamise ukufunyanwa kwemfihlo echanekileyo. Umgcini weqhekeza elichasayo onenkcazelo eyaneleyo unokude avelise elinye iqhekeza ngokutshintsha ngokubona kwakho. Le ngxaki isonjululwe kusetyenziswa izicwangciso zokwabelana eziyimfihlo eziqinisekisiweyo, njengecebo likaFeldman.

Enye ingxaki kukuba ubude baso nasiphi na isiqwenga silingana nobude bemfihlo ehambelanayo, ngoko ubude bemfihlo kulula ukububona. Le ngxaki inokusonjululwa ngokungenamsebenzi padding imfihlo enamanani arbitral ukuya kubude obusisigxina.

Okokugqibela, kubalulekile ukuqaphela ukuba iinkxalabo zethu zokhuseleko zinokudlulela ngaphaya koyilo ngokwalo. Kwizicelo ze-cryptographic zehlabathi zokwenyani, kuhlala kukho isoyikiso sohlaselo lwetshaneli esecaleni apho umhlaseli ezama ukukhupha ulwazi oluluncedo kwixesha lokwenziwa kwesicelo, i-caching, crash, njl. Ukuba oku kuyinkxalabo, kufuneka kuqwalaselwe ngokucokisekileyo ngexesha lophuhliso ekusebenziseni amanyathelo okukhusela afana nemisebenzi kunye nokujonga ixesha eliqhubekayo, ukuthintela imemori ukuba igcinwe kwidiski, kunye nenani lezinye izinto ezicatshangelwayo ezingaphaya kobubanzi beli nqaku.

Isiboniso

phezu kweli phepha Kukho umboniso osebenzisanayo weskimu sikaShamir sokwabelana ngokufihlakeleyo. Umboniso osekelwe kwithala leencwadi sss-js, yona ngokwayo izibuko leJavaScript yenkqubo edumileyo iisms. Qaphela ukuba kubalwa amaxabiso amakhulu , и ingathatha ixesha.

umthombo: www.habr.com