Cabangela isimo lapho udinga ukuvikela i-vault yasebhange. Kubhekwa njengokungenakunqotshwa ngokuphelele ngaphandle kokhiye, owunikezwa ngosuku lokuqala lomsebenzi. Umgomo wakho uwukugcina ngokuphephile ukhiye.
Ake sithi unquma ukugcina ukhiye kuwe ngaso sonke isikhathi, unikeze ukufinyelela kusitoreji njengoba kudingeka. Kodwa uzobona ngokushesha ukuthi isisombululo esinjalo asilingani kahle ekusebenzeni, ngoba ubukhona bakho bomzimba buyadingeka njalo lapho uvula isitoreji. Kuthiwani ngeholide owathenjiswa yona? Ngaphezu kwalokho, umbuzo uyesabisa nakakhulu: kuthiwani uma ulahlekelwe ukhiye wakho kuphela?
Ucabanga ngeholide lakho, unquma ukwenza ikhophi yokhiye bese uwuphathisa esinye isisebenzi. Nokho, uyaqonda ukuthi nalokhu akufanelekile. Ngokuphinda kabili inani lokhiye, uphinda kabili amathuba okuntshontshwa kokhiye.
Ngokudangala, ucekela phansi impinda bese unquma ukuhlukanisa ukhiye wangempela phakathi. Manje, ungacabanga ukuthi abantu ababili abathenjwayo abanezingcezu ezibalulekile kuzofanele babe khona ngokoqobo ukuze baqoqe ukhiye futhi bavule igumbi elingaphansi. Lokhu kusho ukuthi isela lidinga ukweba izingcezu ezimbili, okunzima ngokuphindwe kabili ukweba ukhiye owodwa. Kodwa-ke, ngokushesha uyabona ukuthi lolu hlelo alungcono kakhulu kunokhiye owodwa, ngoba uma othile elahlekelwa ukhiye oyingxenye, ukhiye ogcwele awukwazi ukutholwa.
Inkinga ingaxazululwa ngochungechunge lwezikhiye ezengeziwe nezingidi, kodwa le ndlela izodinga ngokushesha ΠΌΠ½ΠΎΠ³ΠΎ okhiye nezingidi. Unquma ukuthi idizayini efanelekile izoba ukwabelana ngokhiye ukuze ukuphepha kunganciki ngokuphelele kumuntu oyedwa. Futhi uphethe ngokuthi kufanele kube nomkhawulo othile wenani lezingcezu ukuze uma ucezu olulodwa lulahlekile (noma uma umuntu eya eholidini), wonke ukhiye uhlale usebenza.
Indlela yokwabelana ngemfihlo
Lolu hlobo lohlelo lokuphatha olubalulekile lwacatshangwa ngu-Adi Shamir ngo-1979 lapho eshicilela umsebenzi wakhe . Isihloko sichaza kafushane lokho okuthiwa 
i-threshold scheme yokuhlukanisa ngempumelelo inani eliyimfihlo (elifana nokhiye we-cryptographic). izingxenye. Khona-ke, nini futhi nini kuphela okungenani kusuka ku izingxenye zihlangene, ungakwazi ukubuyisela kalula imfihlo .
Ngokombono wezokuphepha, isici esibalulekile salolu hlelo ukuthi umhlaseli akufanele azi lutho ngaphandle uma okungenani ene. izingxenye. Ngisho nokuba khona izingxenye akufanele zinikeze noma yiluphi ulwazi. Le ndawo siyibiza ukuphepha kwe-semantic.
I-polynomial interpolation
I-Shamir threshold scheme eyakhelwe phezu komqondo i-polynomial interpolation. Uma ungawazi lo mqondo, empeleni ulula. Eqinisweni, uma uke wadweba amaphuzu kugrafu wabe usuwaxhuma ngemigqa noma amajika, usuwasebenzisile kakade!
Ngamaphuzu amabili ungakwazi ukudweba inombolo engenamkhawulo yama-polynomials we-degree 2. Ukuze ukhethe okuwukuphela kwawo kuwo, udinga iphuzu lesithathu. Umfanekiso:
Cabanga nge-polynomial eneziqu zokuqala, . Uma ufuna ukuhlela lo msebenzi kugrafu, mangaki amaphuzu owadingayo? Hhayi-ke, siyazi ukuthi lona umsebenzi womugqa owakha umugqa ngakho udinga okungenani amaphuzu amabili. Okulandelayo, cabanga ngomsebenzi we-polynomial oneziqu zesibili, . Lona umsebenzi we-quadratic, ngakho-ke okungenani amaphuzu amathathu ayadingeka ukuze uhlele igrafu. Kuthiwani nge-polynomial eneziqu zesithathu? Okungenani amaphuzu amane. Futhi njalo njalo njalo.
Into epholile ngempela ngalesi sakhiwo ukuthi, uma kubhekwa izinga lomsebenzi we-polynomial futhi okungenani amaphuzu, singathola amaphuzu engeziwe kulo msebenzi we-polynomial. Sibiza i-extrapolation yala maphuzu engeziwe i-polynomial interpolation.
Ukwenza imfihlo
Kungenzeka ukuthi usubonile ukuthi kulapho kudlala khona isikimu sikaShamir esihlakaniphile. Ake sithi imfihlo yethu Ingabe . Singaphenduka ephuzwini kugrafu futhi uqhamuke nomsebenzi we-polynomial oneziqu , elenelisa leli phuzu. Ake sikukhumbuze lokho kuzoba umkhawulo wethu wezingcezu ezidingekayo, ngakho-ke uma sibeka umkhawulo ube yizingcezu ezintathu, kufanele sikhethe umsebenzi we-polynomial onedigri yesibili.
I-polynomial yethu izoba nefomu kuphi ΠΈ - izinombolo ezikhethiwe ngokungahleliwe. Sakha i-polynomial eneziqu , lapho i-coefficient yamahhala - Lena imfihlo yethu , nangayo ngayinye elandelayo ngokwemibandela kukhona i-coefficient ephozithivu ekhethwe ngokungahleliwe. Uma sibuyela esibonelweni sokuqala futhi sicabange ukuthi , bese sithola umsebenzi .
Kuleli qophelo singakwazi ukukhiqiza izingcezu ngokuxhuma izinombolo ezihlukile ku kuphi (ngoba kuyimfihlo yethu). Kulesi sibonelo, sifuna ukusabalalisa izingcezu ezine ngomkhawulo wokuthathu, ngakho-ke senza amaphuzu ngokungahleliwe. futhi uthumele iphuzu elilodwa kubantu abane abathenjwayo, abagcini bokhiye. Siyabazisa futhi abantu lokho , njengoba lokhu kuthathwa njengolwazi olusesidlangalaleni futhi kuyadingeka ukuze kutholakale .
Ukubuyisa imfihlo
Sesixoxile kakade ngomqondo we-polynomial interpolation nokuthi isekela kanjani uhlelo lukaShamir. . Lapho noma yibaphi abathathu kwabaphatheli abane bafuna ukubuyisela , zidinga kuphela ukuhunyushwa enamaphuzu ayo ayingqayizivele. Ukuze benze lokhu, bangakwazi ukunquma amaphuzu abo futhi ubale i-Lagrange interpolation polynomial usebenzisa ifomula elandelayo. Uma ukuhlela kucace kuwena kunezibalo, kusho ukuthi u-pi ungu-opharetha for, ephindaphinda yonke imiphumela, futhi i-sigma iyi for, okuhlanganisa konke.
ngesikhathi singayixazulula kanje futhi sibuyisele umsebenzi wethu wokuqala we-polynomial:
Ngoba siyakwazi lokho , ukululama kwenziwe kalula:
Ukusebenzisa i-integer arithmetic engaphephile
Nakuba sisebenzise ngempumelelo umqondo oyisisekelo ka-Shamir , sisele nenkinga esingazange siyinake kuze kube manje. Umsebenzi wethu we-polynomial usebenzisa i-integer arithmetic engaphephile. Qaphela ukuthi kuwo wonke amaphoyinti angeziwe atholwa umhlaseli kugrafu yomsebenzi wethu, mancane amathuba okuthi amanye amaphuzu. Lokhu ungakubona ngamehlo akho lapho uhlela inani elikhulayo lamaphuzu omsebenzi we-polynomial usebenzisa i-integer arithmetic. Lokhu akuhambisani nomgomo wethu wokuvikela oshiwo, ngoba umhlaseli akufanele azi lutho kuze kube yilapho esenayo okungenani izingcezwana.
Ukukhombisa ukuthi ibuthaka kangakanani i-integer arithmetic circuit, cabanga ngesimo lapho umhlaseli ethole khona amaphuzu amabili. futhi uyazi ulwazi lomphakathi lokho . Kusukela kulolu lwazi angakwazi ukuthola , elilingana nokubili, bese uxhuma amanani aziwayo kufomula ΠΈ .
Umhlaseli angakwazi ukuthola , ukubala :
Njengoba sesichazile njengama-integer akhethiwe ngokungahleliwe, kukhona inani elilinganiselwe elingenzeka . Ngokusebenzisa lolu lwazi, umhlaseli anganquma , ngoba noma yini enkulu kune-5 izokwenza negative. Lokhu kuvele kuyiqiniso njengoba sesinqumile
Umhlaseli angakwazi ukubala amanani angenzeka esikhundleni Π² :
Ngezinketho ezilinganiselwe ze kuyacaca ukuthi kulula kangakanani ukukhetha nokuhlola amanani . Kunezinketho ezinhlanu kuphela lapha.
Ukuxazulula inkinga nge-integer arithmetic engaphephile
Ukuze kuqedwe lobu sengozini, u-Shamir uphakamisa ukusebenzisa i-arithmetic ye-modular, esikhundleni on kuphi ΠΈ - isethi yazo zonke izinombolo eziyinhloko.
Masikhumbule ngokushesha ukuthi izibalo ze-modular zisebenza kanjani. Iwashi elinezandla liwumqondo ojwayelekile. Usebenzisa iwashi okungukuthi . Ngokushesha nje lapho isandla sehora sidlula ishumi nambili, sibuyela kweyodwa. Isici esithakazelisayo salesi simiso ukuthi ngokubuka nje iwashi, asikwazi ukuthola ukuthi zingaki izinguquko ezenziwe yihora. Kodwa-ke, uma sazi ukuthi isandla sehora sidlule izikhathi ezingu-12 izikhathi ezine, singanquma ngokuphelele inani lamahora adlulile sisebenzisa ifomula elula. kuphi isihlukanisi sethu (lapha ), yi-coefficient (kangakhi isihlukanisi singena enombolweni yokuqala ngaphandle kwensali, lapha ), futhi okusele, okuvamise ukubuyisela ikholi yomqhubi wemodulo (lapha ). Ukwazi wonke lawa magugu kusivumela ukuthi sixazulule i-equation , kodwa uma sigeja i-coefficient, ngeke sikwazi ukubuyisela inani langempela.
Singabonisa ukuthi lokhu kuthuthukisa kanjani ukuphepha kohlelo lwethu ngokusebenzisa uhlelo esibonelweni sethu sangaphambilini nokusebenzisa . Umsebenzi wethu omusha we-polynomial , kanye namaphuzu amasha . Manje abagcini abakhulu bangaphinda basebenzise i-polynomial interpolation ukuze bakhe kabusha umsebenzi wethu, kulokhu kuphela imisebenzi yokwengeza nokuphindaphinda kufanele ihambisane nokunciphisa i-modulo. (isib ).
Sisebenzisa lesi sibonelo esisha, ake sicabange ukuthi umhlaseli ufunde amaphuzu amabili kulawa amasha, , kanye nolwazi lomphakathi . Kulokhu, umhlaseli, ngokusekelwe kulo lonke ulwazi analo, ukhipha imisebenzi elandelayo, lapho iyisethi yawo wonke izinombolo eziphozithivu, futhi imele i-modulus coefficient .
Manje umhlaseli wethu uyathola futhi , ukubala :
Bese ezama futhi esikhundleni Π² :
Kulokhu unenkinga enkulu. Amanani ashoda ngefomula , ΠΈ . Njengoba kunenombolo engapheli yezinhlanganisela zalezi ziguquko, akakwazi ukuthola noma yiluphi ulwazi olwengeziwe.
Ukucatshangelwa Kokuphepha
Uhlelo luka-Shamir lokwabelana ngokuyimfihlo luyaphakamisa ukuphepha ngokombono wethiyori yolwazi. Lokhu kusho ukuthi izibalo azikwazi ukumelana nomhlaseli onamandla angenamkhawulo wekhompyutha. Nokho, isifunda sisaqukethe izindaba ezimbalwa ezaziwayo.
Isibonelo, uhlelo lukaShamir aludali izingcezu okufanele zihlolwe, okungukuthi, abantu bangaletha ngokukhululekile izingcezwana zomgunyathi futhi baphazamise ukutholwa kwemfihlo efanele. Umgcini wezingcezwana ononya onolwazi olwanele angase aveze olunye ucezu ngokushintsha ngokubona kwakho. Le nkinga ixazululwa ngokusebenzisa izinhlelo zokwabelana eziyimfihlo eziqinisekisayo, njengohlelo lukaFeldman.
Enye inkinga iwukuthi ubude banoma isiphi isiqeshana bulingana nobude bemfihlo ehambisanayo, ngakho ubude bemfihlo kulula ukunquma. Le nkinga ingaxazululwa ngezinto ezincane i-padding imfihlo enezinombolo ezifika ngobude obungashintshi.
Okokugcina, kubalulekile ukuqaphela ukuthi ukukhathazeka kwethu kwezokuphepha kungase kudlulele ngale kwedizayini ngokwayo. Kuzinhlelo zokusebenza ze-cryptographic zomhlaba wangempela, kuvame ukuba nosongo lokuhlaselwa kwesiteshi esiseceleni lapho umhlaseli ezama ukukhipha ulwazi oluwusizo esikhathini sokwenza uhlelo, ukulondoloza inqolobane, ukuphahlazeka, njll. Uma lokhu kuwukukhathazeka, kufanele kucatshangelwe ngokucophelela ngesikhathi sokuthuthukiswa ukusebenzisa izindlela zokuvikela ezifana nemisebenzi nokubheka isikhathi esingaguquki, ukuvimbela inkumbulo ukuthi ilondolozwe kudiski, kanye nokunye okucatshangelwayo okungaphezu kobubanzi balesi sihloko.
Demo
In Kukhona ukuboniswa okusebenzisanayo kohlelo lokwabelana okuyimfihlo luka-Shamir. Umboniso osuselwe kulabhulali , yona ngokwayo eyimbobo ye-JavaScript yohlelo oludumile . Qaphela ukuthi kubalwa amanani amakhulu , ΠΈ kungathatha isikhashana.
Source: www.habr.com