Funga nezvechiitiko chaunoda kuchengetedza bhangi vault. Inotaridzirwa isingapindiki pasina kiyi, iyo yaunopiwa pazuva rekutanga rebasa. Chinangwa chako ndechekuchengetedza kiyi.

Ngatiti iwe wafunga kuchengeta kiyi newe nguva dzese, uchipa mukana wekuchengetedza sezvinodiwa. Asi iwe uchakurumidza kuona kuti mhinduro yakadaro haina kukwira zvakanaka mukuita, nekuti kuvepo kwako kwemuviri kunodiwa pese paunovhura chengetedzo. Zvakadini nezororo rawakavimbiswa? Mukuwedzera, mubvunzo unotonyanya kutyisa: ko kana iwe ukarasikirwa nekiyi yako chete?

Uine zororo rako mupfungwa, unofunga kuita kopi yekiyi uye woiisa kune mumwe mushandi. Nekudaro, iwe unonzwisisa kuti izvi hazvina kunaka kana. Nekupeta kaviri nhamba yemakiyi, iwe zvakare kaviri mikana yekuba kiyi.

Mukupererwa, unoparadza duplicate uye wofunga kupatsanura kiyi yepakutanga nepakati. Zvino, iwe ungafunga kuti vanhu vaviri vanovimbwa vane zvimedu zvakakosha vaizofanira kunge varipo kuti vatore kiyi uye vavhure vault. Izvi zvinoreva kuti mbavha inoda kuba zvidimbu zviviri, izvo zvakaoma zvakapetwa kaviri kupfuura kuba kiyi imwe chete. Nekudaro, iwe unokurumidza kuona kuti chirongwa ichi hachina nani kupfuura kiyi imwe chete, nekuti kana mumwe munhu akarasikirwa nehafu kiyi, kiyi yakazara haigone kudzoserwa.

Dambudziko rinogona kugadziriswa nekutevedzana kwemamwe makiyi uye makiyi, asi nzira iyi ichakurumidza kuda много kiyi nemakiyi. Iwe unosarudza kuti dhizaini yakakodzera ingave yekugovera kiyi kuitira kuti chengetedzo isavimbe nemunhu mumwe chete. Iwewo unogumisa kuti panofanira kuva nechikumbaridzo chehuwandu hwezvidimbu kuitira kuti kana chimwe chidimbu chikarasika (kana kana munhu akaenda kuzororo), kiyi yose inoramba ichishanda.

Kugovana sei chakavanzika

Iri rudzi rwekiyi manejimendi chirongwa chakafungwa nezvacho naAdi Shamir muna 1979 paakaburitsa basa rake "Kugovana Sei Chakavanzika". Nyaya yacho inotsanangura muchidimbu zvinonzi pachikumbaridzo chirongwa chekugovanisa kukosha kwakavanzika (senge cryptographic kiyi) kupinda zvikamu. Zvadaro, rini uye chete riini kubva zvikamu zvakaunganidzwa, unogona kudzorera chakavanzika nyore nyore .

Kubva pakuona kwekuchengetedza, chinhu chakakosha chechirongwa ichi ndechekuti munhu anorwisa haafanire kuziva chero chinhu kunze kwekunge aine zvishoma. zvikamu. Kunyange kuvapo zvikamu hazvifanirwe kupa chero ruzivo. Tinodaidza pfuma iyi semantic kuchengeteka.

Polynomial interpolation

Shamir chikumbaridzo chirongwa yakavakirwa papfungwa polynomial interpolation. Kana usiri kujairana nepfungwa iyi, iri nyore chaizvo. Muchokwadi, kana iwe wakambodhirowa mapoinzi pagirafu wobva waabatanidza nemitsara kana macurves, watoishandisa!

Kuburikidza nemapoinzi maviri unogona kudhirowa nhamba isingaperi yemapolynomials edhigirii 2. Kuti usarudze imwe chete kubva kwavari, unoda poindi yechitatu. Mufananidzo: Wikipedia

Funga nezve polynomial ine degree rekutanga, . Kana iwe uchida kuronga basa iri pagirafu, mapoinzi mangani aunoda? Zvakanaka, tinoziva kuti iri ibasa remutsara rinoumba mutsara uye saka rinoda zvingangoita mapoinzi maviri. Tevere, funga nezve polynomial basa nedhigirii rechipiri, . Iri ibasa requadratic, saka anokwana mapoinzi matatu anodiwa kuronga girafu. Zvakadini nezve polynomial ine degree rechitatu? Zvibodzwa zvina. Uye zvichingodaro zvichingodaro.

Chinhu chaicho chinotonhorera pamusoro pechinhu ichi ndechekuti, kupihwa dhigirii repolynomial basa uye zvirinani mapoinzi, tinogona kutora mamwe mapoinzi eiyi polynomial basa. Tinodaidza kuti extrapolation yeaya mapoinzi ekuwedzera polynomial interpolation.

Kuita chakavanzika

Iwe unogona kunge watoona kuti apa ndipo panouya zano raShamir rakangwara. Ngatitaure zvakavanzika zvedu - ichi chi . Tinogona kutendeuka kusvika pane imwe girafu uye uuye nebasa repolynomial rine degree , izvo zvinogutsa pfungwa iyi. Ngatikuyeuchidzei izvozvo ichava chikumbaridzo chedu chezvidimbu zvinodiwa, saka kana tikaisa chikumbaridzo kune zvimedu zvitatu, tinofanira kusarudza basa repolynomial rine dhigirii rechipiri.

Yedu polynomial ichava nefomu kupi и - akasarudzwa zvisina tsarukano nhamba yakanaka. Isu tiri kungogadzira polynomial ine degree , uko iyo yemahara coefficient  - Ichi ndicho chakavanzika chedu , uye kune imwe neimwe yeanotevera mazwi pane akasarudzwa zvisina kurongwa positive coefficient. Kana tikadzokera kumuenzaniso wekutanga uye tofunga izvozvo , tobva tawana basa .

Panguva ino tinogona kugadzira zvimedu nekubatanidza unique integers in kupi (nekuti ndicho chakavanzika chedu). Mumuenzaniso uyu, tinoda kugovera zvimedu zvina nechikumbaridzo chevatatu, saka isu tinongogadzira mapoinzi. uye tumira pfungwa imwe kune mumwe nemumwe wevanhu vana vanovimbwa, vachengeti vekiyi. Tinozivisawo vanhu izvozvo , sezvo izvi zvichionekwa seruzivo rwevanhu uye zvakakosha pakupora .

Kuwanazve chakavanzika

Isu takambokurukura pfungwa yekududzirwa kwepolynomial uye kuti inotsikirira sei pachikumbaridzo cheShamir. . Kana chero vatatu vevana tirastii vanoda kudzoreredza , dzinongoda kupindirana chete nemapoinzi ayo akasiyana. Kuti vaite izvi, vanogona kusarudza pfungwa dzavo uye kuverenga iyo Lagrange interpolation polynomial uchishandisa inotevera fomula. Kana hurongwa hwakajeka kwauri kupfuura masvomhu, saka pi inonyanya kushanda for, iyo inowedzera mibairo yese, uye sigma iri for, iyo inowedzera zvinhu zvose.

pa tinogona kuzvigadzirisa sezvizvi uye kudzosera yedu yekutanga polynomial basa:

Nokuti tinoziva izvozvo , kupora zvaitwa zviri nyore:

Kushandisa nhamba isina kuchengetedzwa arithmetic

Kunyangwe isu takabudirira kushandisa zano rekutanga raShamir , tasara nedambudziko ratakambofuratira kusvika zvino. Basa redu repolynomial rinoshandisa nhamba isina kuchengetedzwa arithmetic. Ziva kuti pane yega yega yekuwedzera iyo anorwiswa anowana pagirafu rebasa redu, kune mashoma mikana yemamwe mapoinzi. Iwe unogona kuona izvi nemeso ako pachako paunoronga nhamba inowedzera yemapoinzi ebasa repolynomial uchishandisa integer arithmetic. Izvi zvinopesana nechinangwa chedu chekuchengetedza chakataurwa, nekuti munhu anorwisa haafanire kuziva chinhu kudzamara vawana zvidimbu.

Kuti uratidze kusimba kwakaita nhamba yakazara yemasvomhu, funga nezvechiitiko apo murwi akawana mapoinzi maviri. uye anoziva ruzivo rweveruzhinji izvo . Kubva pane ruzivo urwu anogona kufungidzira , yakaenzana nembiri, uye plug mune dzinozivikanwa kukosha mufomula и .

Anorwisa anogona kuwana , kuverenga :

Sezvo takatsanangura sekusarudzwa zvisina kurongeka zvakanaka nhamba, pane nhamba shoma yezvinobvira . Achishandisa ruzivo urwu, anorwisa anogona kufungidzira , sezvo chero chinhu chikuru kupfuura 5 chichaita negative. Izvi zvinova zvechokwadi sezvo isu takasarudza

Murwi anogona kuzoverenga zvinokwanisika kutsiva в :

Nezvisarudzo zvishoma zve zvinova pachena kuti zviri nyore sei kusarudza uye kutarisa maitiro . Pane sarudzo shanu chete pano.

Kugadzirisa dambudziko nenhamba isina kuchengetedzwa arithmetic

Kubvisa kusagadzikana uku, Shamir anokurudzira kushandisa modular arithmetic, kutsiva pamusoro kupi и - iyo seti yeese nhamba huru.

Ngatiyeukei nekukurumidza kuti modular arithmetic inoshanda sei. Wachi ine maoko ipfungwa yakajairika. Anoshandisa wachi kureva . Pakarepo nguva yeawa ichipfuura gumi nembiri, inodzokera kune imwe. Chinhu chinonakidza chegadziriro iyi ndechekuti nekungotarisa wachi, hatigone kuona kuti mabhindauko mangani akaitwa neawa. Nekudaro, kana tichiziva kuti awa yapfuura ka12 kana, tinogona kunyatsoona nhamba yemaawa apfuura tichishandisa nzira iri nyore. kupi  ndiye divisor yedu (pano ),  ndiyo coefficient (kangani iyo divisor inopinda munhamba yekutanga isina inosara, pano ), a  ndiyo yasara, iyo inowanzo dzorera modulo opareta kufona (pano ) Kuziva zvese izvi zvakakosha zvinotitendera kugadzirisa iyo equation , asi kana tikapotsa coefficient, hatizombokwanisi kudzorera kukosha kwepakutanga.

Tinogona kuratidza kuti izvi zvinovandudza sei kuchengetedzwa kwechirongwa chedu nekushandisa chirongwa kumuenzaniso wedu wekare uye kushandisa . Yedu itsva polynomial basa , uye pfungwa itsva . Iye zvino vachengeti vakakosha vanogona zvakare kushandisa polynomial kududzira kuvakazve basa redu, chete panguva ino kuwedzera uye kuwanda kwekuita kunofanirwa kuperekedzwa nekuderedza modulo. (semuenzaniso ).

Tichishandisa uyu muenzaniso mutsva, ngatifungei kuti murwi akadzidza maviri emapoinzi matsva aya, , uye ruzivo rweruzhinji . Panguva ino, anorwisa, zvichienderana neruzivo rwese rwaanarwo, anoburitsa mabasa anotevera, kupi  ndiyo seti yezvose zvakanaka nhamba, uye inomiririra modulus coefficient .

Iye zvino murwi wedu anowana zvakare , kuverenga :

Anobva aedza zvakare kutsiva в :

Panguva ino ane dambudziko guru. Formula inoshaya kukosha , и . Sezvo kune nhamba isingagumi yezvibatanidzwa zvezvisiyana izvi, haakwanisi kuwana chero ruzivo rwekuwedzera.

Chengetedzo Kufunga

Shamir's secret sharing scheme inoratidzira chengetedzo kubva pamaonero edzidziso yeruzivo. Izvi zvinoreva kuti masvomhu anoshingirira kunyangwe kune anorwisa ane unlimited computing power. Zvisinei, dunhu richine nyaya dzakawanda dzinozivikanwa.

Semuenzaniso, chirongwa cheShamir hachigadziri zvimedu zvinofanira kuongororwa, kureva kuti, vanhu vanogona kupa pachena zvimedu zvekunyepedzera uye kukanganisa kudzoreredzwa kwechakavanzika chaicho. Muchengeti wechidimbu ane utsinye ane ruzivo rwakakwana anogona kutogadzira chimwe chidimbu nekuchinja pakufunga kwako. Dambudziko iri rinogadziriswa uchishandisa zvirongwa zvekugovana zvakavanzika zvinogoneka, zvakadai sechirongwa chaFeldman.

Rimwe dambudziko nderekuti kureba kwechero chidimbu kwakaenzana nehurefu hwechakavanzika chinowirirana, saka kureba kwechakavanzika kuri nyore kuziva. Dambudziko iri rinogona kugadziriswa nezvisina basa padding chakavanzika nenhamba dzemadiro kusvika pakureba yakatarwa.

Chekupedzisira, zvakakosha kuti ticherechedze kuti zvichemo zvedu zvekuchengetedza zvinogona kuwedzera kupfuura dhizaini pachayo. Kune chaiyo-yenyika cryptographic application, pane kazhinji kutyisidzira kwekurwiswa kwepadivi-chiteshi apo anorwisa anoedza kuburitsa ruzivo rwakakosha kubva panguva yekushandisa application, caching, kubondera, nezvimwe. Kana ichi chiri kunetseka, kunyatsotariswa kunofanirwa kupihwa panguva yekuvandudza kushandisa matanho ekudzivirira senge mabasa uye nguva dzose-kutarisa-nguva, kudzivirira ndangariro kubva pakuchengetwa kudhisiki, uye akati wandei mamwe mafungidziro ari kunze kwechikamu chechinyorwa ichi.

Dhemo

pamusoro peji ino Pane ratidziro inopindirana yechirongwa chaShamir chekugovana zvakavanzika. Kuenzanisira kunobva muraibhurari sss-js, iyo pachayo inzvimbo yeJavaScript yepurogiramu yakakurumbira MIBVUNZO. Ziva kuti kuverenga hukuru hukuru , и zvinogona kutora nguva.

Source: www.habr.com