Hunahunaa ang usa ka senaryo diin kinahanglan nimo nga masiguro ang usa ka vault sa bangko. Giisip kini nga hingpit nga dili mabuntog nga walay yawe, nga gihatag kanimo sa unang adlaw sa trabaho. Ang imong tumong mao ang luwas nga pagtipig sa yawe.
Ibutang ta nga modesisyon ka nga tipigan nimo ang yawe sa tanang panahon, nga maghatag ug access sa vault kon gikinahanglan. Apan dali nimo mahibal-an nga ang ingon nga solusyon dili maayo nga sukod sa praktis, tungod kay sa matag higayon nga kinahanglan nimo nga pisikal nga presente aron maablihan ang vault. Unsa ang mahitungod sa bakasyon nga imong gisaad? Dugang pa, ang pangutana mas makahadlok: unsa man kung nawala nimo ang bugtong yawe?
Uban sa ideya sa usa ka bakasyon, nakahukom ka nga maghimo usa ka kopya sa yawe ug itugyan kini sa laing empleyado. Bisan pa, nasabtan nimo nga dili usab kini maayo. Pinaagi sa pagdoble sa gidaghanon sa mga yawe, nadoble usab nimo ang kahigayonan sa pagpangawat sa yawe.
Desperado, imong gub-on ang duplicate ug modesisyon nga bahinon ang orihinal nga yawe sa tunga. Karon, sa imong hunahuna ang duha ka kasaligan nga mga tawo nga adunay yawe nga mga tipik kinahanglan nga pisikal nga naa aron makolekta ang yawe ug maablihan ang vault. Kini nagpasabot nga ang kawatan kinahanglan nga mangawat ug duha ka tipik, nga doble kalisod sa pagkawat sa usa ka yawe. Bisan pa, nahibal-an dayon nimo nga kini nga laraw dili labi ka maayo kaysa usa ra ka yawe, tungod kay kung adunay usa nga mawad-an sa katunga sa yawe, ang tibuuk nga yawe dili na mabawi.
Ang problema mahimong masulbad sa usa ka sunod-sunod nga dugang nga mga yawe ug mga kandado, apan kini nga pamaagi sa madali nagkinahanglan usa ka daghan yawe ug mga kandado. Nakahukom ka nga ang sulundon nga laraw mao ang pagpaambit sa yawe aron ang seguridad dili magsalig sa usa ka tawo. Naghinapos ka usab nga kinahanglan adunay pipila ka sukaranan alang sa gidaghanon sa mga tipik aron kung mawala ang usa ka tipik (o kung ang tawo magbakasyon), ang tibuuk nga yawe magpabilin nga magamit.
Unsaon pag share ug sekreto
Kini nga matang sa key management scheme gihunahuna ni Adi Shamir niadtong 1979 sa dihang iyang gipatik ang iyang trabaho . Ang artikulo mubo nga nagpatin-aw sa gitawag nga 
thresholding scheme para sa epektibong pagbahin sa usa ka sekreto nga bili (pananglitan, usa ka cryptographic nga yawe) ngadto sa mga bahin. Unya, kanus-a ug kanus-a lang labing menos gikan sa ang mga bahin gitigum, dali nimo mapasig-uli ang sekreto .
Gikan sa usa ka punto sa seguridad, usa ka importante nga kabtangan niini nga laraw mao nga ang usa ka tig-atake kinahanglan nga dili makakat-on kung wala siya labing menos mga bahin. Bisan ang presensya Ang mga bahin kinahanglan dili maghatag bisan unsang kasayuran. Gitawag namo kini nga kabtangan semantiko nga seguridad.
Polynomial Interpolation
Threshold Shamir scheme gitukod sa palibot sa konsepto polynomial interpolation. Kung dili ka pamilyar sa kini nga konsepto, kini sa tinuud yano ra. Sa kinatibuk-an, kung nakadrowing ka na ug mga punto sa usa ka tsart ug dayon gisumpay kini sa mga linya o mga kurba, nagamit na nimo kini!
Pinaagi sa duha ka punto, mahimo ka magdrowing og walay kinutuban nga gidaghanon sa mga polynomial sa degree 2. Aron mapili ang usa lamang gikan kanila, kinahanglan nimo ang ikatulo nga punto. Ilustrasyon:
Hunahunaa ang usa ka polynomial nga adunay degree uno, . Kung gusto nimong iplano kini nga function sa usa ka graph, pila ka punto ang imong kinahanglan? Aw, nahibal-an namon nga kini usa ka linear function nga nagporma usa ka linya ug busa kinahanglan namon ang labing menos duha ka puntos. Sunod, ikonsiderar ang usa ka polynomial function nga adunay degree nga duha, . Kini usa ka quadratic function, busa labing menos tulo ka punto ang gikinahanglan aron maplano ang graph. Unsa man ang bahin sa usa ka polynomial nga adunay degree nga tulo? Labing menos upat ka tuldok. Ug uban pa ug uban pa.
Ang tinuod nga cool nga butang bahin sa kini nga kabtangan mao nga, gihatagan ang lebel sa polynomial function ug labing menos puntos, mahimo kitang makakuha og dugang nga mga punto alang niining polynomial function. Gitawag namo ang extrapolation niining dugang nga mga punto polynomial interpolation.
Paghimo og sekreto
Mahimong nahibal-an na nimo nga dinhi nagsugod ang maalamon nga laraw ni Shamir. Ibutang ta atong sekreto Mao ba . Mahimo kitang moliko hangtod sa punto sa graph ug adunay usa ka polynomial function nga adunay degree , nga nagtagbaw niini nga punto. Hinumdomi kana mao ang atong threshold sa gikinahanglan nga mga tipik, mao nga kon atong ibutang ang threshold sa tulo ka mga tipik, kita kinahanglan gayud nga mopili sa usa ka polynomial function nga adunay usa ka degree sa duha.
Ang among polynomial adunay porma diin ΠΈ mga random nga gipili nga positibo nga mga integer. Nagtukod lang kami usa ka polynomial nga adunay degree , diin ang libre nga coefficient - Kini ang among sekreto , ug ang matag usa sa mosunod Ang mga termino usa ka random nga gipili nga positibo nga coefficient. Kung mobalik kita sa orihinal nga pananglitan ug hunahunaon kana , unya atong makuha ang function .
Niini nga punto, makahimo kita og mga tipik pinaagi sa pagkonektar talagsaon nga mga integer sa diin (kay sekreto man ni nato). Sa kini nga pananglitan, gusto namon nga ipang-apod-apod ang upat ka mga tipik nga adunay tulo nga sukdanan, mao nga random nga makamugna kami mga puntos ug ipadala ang usa ka punto sa matag usa sa upat ka sinaligan nga mga tawo, ang mga magbalantay sa yawe. Gisultihan usab namo kana sa mga tawo , ingon nga kini gikonsiderar nga publiko nga impormasyon ug gikinahanglan alang sa pagbawi .
Sekreto nga Pagbawi
Nahisgotan na nato ang konsepto sa polynomial interpolation ug kung giunsa kini nagpahipi sa thresholding scheme ni Shamir. . Kung adunay tulo sa upat ka mga sinaligan nga gusto ibalik , kinahanglan lang nila i-interpolate uban sa ilang talagsaon nga mga punto. Aron mahimo kini, mahimo nilang ipasabut ang ilang mga punto ug kuwentaha ang Lagrange interpolation polynomial gamit ang mosunod nga pormula. Kung ang programming mas klaro kanimo kaysa sa matematika, nan ang pi usa ka operator for, nga nagpadaghan sa tanan nga mga resulta, ug ang sigma mao fornga nagadugang sa tanan.
sa masulbad nato kini sama niini ug ibalik ang atong orihinal nga polynomial function:
Sanglit nahibal-an namon kana , pagkaayo gihimo sa yano:
Paggamit sa dili luwas nga integer aritmetika
Bisan kung malampuson namon nga gipadapat ang sukaranan nga ideya ni Shamir , naa tay problema nga wala nato tagda hangtod karon. Ang among polynomial function naggamit ug dili luwas nga integer aritmetika. Timan-i nga sa matag dugang nga punto nga makuha sa tig-atake sa among function graph, adunay gamay nga posibilidad alang sa ubang mga punto. Makita nimo kini sa imong kaugalingon nga mga mata kung magplano ka og dugang nga gidaghanon sa mga punto alang sa usa ka polynomial function gamit ang integer arithmetic. Kini dili produktibo sa among gipahayag nga katuyoan sa seguridad, tungod kay ang usa ka tig-atake kinahanglan nga walaβy nahibal-an hangtod nga sila adunay labing menos mga tipik.
Para ipakita kung unsa ka huyang ang integer arithmetic scheme, tagda ang usa ka senaryo diin ang tig-atake nakadawat ug duha ka puntos ug nahibalo sa publiko nga impormasyon nga . Gikan sa kini nga kasayuran, mahimo niyang mahibal-an , katumbas sa duha, ug ikonektar ang nahibal-an nga mga kantidad sa pormula ΠΈ .
Makapangita dayon ang tig-atake , pag-ihap :
Sukad ato gipasabot ingon nga random nga gipili nga positibo nga mga integer, adunay limitado nga gidaghanon sa posible . Uban niini nga kasayuran, ang usa ka tig-atake mahimong makahunahuna , tungod kay bisan unsa nga labaw pa sa 5 makahimo negatibo. Kini nahimo nga tinuod, tungod kay kami nakahukom
Mahimong kuwentahon sa tig-atake ang posibleng mga kantidad pagpuli Π² :
Uban sa limitado nga mga kapilian alang sa mahimong klaro kung unsa kadali ang pagkuha ug pagsusi sa mga kantidad . Adunay lima lamang ka kapilian dinhi.
Pagsulbad sa problema sa dili luwas nga integer aritmetika
Aron ayohon kini nga pagkahuyang, gisugyot ni Shamir ang paggamit sa modular arithmetic pinaagi sa pag-ilis sa diin ΠΈ mao ang set sa tanang prime number.
Atong hinumdoman dayon kung giunsa paglihok ang modular aritmetika. Ang mga orasan sa kamot usa ka pamilyar nga konsepto. Gigamit niya ang usa ka relo nga mao . Sa diha nga ang takna molabay sa dose, kini mobalik sa usa. Ang usa ka makapaikag nga kabtangan niini nga sistema mao nga pinaagi lamang sa pagtan-aw sa orasan, dili naton mahibal-an kung pila ang mga rebolusyon nga nahimo sa kamot sa oras. Bisan pa, kung nahibal-an naton nga ang kamot sa orasan milabay sa 12 upat ka beses, mahimo naton hingpit nga mahibal-an ang gidaghanon sa mga oras nga milabay gamit ang usa ka yano nga pormula. diin mao ang atong divisor (dinhi ), - kini ang coefficient (pila ka beses ang divisor nga walaβy nahabilin nga moadto sa orihinal nga numero, dinhi ), ug mao ang nahabilin, nga kasagaran nagbalik sa usa ka tawag sa modulo operator (dinhi ). Ang pagkahibalo sa tanan niini nga mga kantidad nagtugot kanato sa pagsulbad sa equation alang sa , apan kon atong laktawan ang coefficient, dili na nato mabalik ang orihinal nga bili.
Atong mapakita kon sa unsang paagi kini makapauswag sa seguridad sa atong sirkito pinaagi sa pagpadapat sa sirkito sa atong miaging pananglitan ug paggamit . Ang among bag-ong polynomial function , ug ang bag-ong mga punto . Karon ang yawe nga mga tigbantay mahimo na usab nga mogamit sa polynomial interpolation aron matukod pag-usab ang among function, niining higayona ang pagdugang ug pagpadaghan nga mga operasyon kinahanglan sundan sa pagkunhod sa modulo. (pananglitan ).
Gamit kining bag-ong pananglitan, pananglitan ang tig-atake nakakat-on sa duha niining bag-ong mga punto, , ug impormasyon sa publiko . Niining higayona, ang tig-atake, base sa tanang impormasyon nga naa niya, nagpakita sa mosunod nga mga gimbuhaton, diin mao ang set sa tanang positibo nga integer, ug nagrepresentar sa modulus coefficient .
Karon nakit-an na usab ang among intruder , pagkalkula :
Unya misulay siya pag-usab sa pag-atras pagpuli Π² :
Niining higayona siya adunay usa ka seryoso nga problema. Nawala nga mga kantidad ang pormula , ΠΈ . Tungod kay adunay walay kinutuban nga gidaghanon sa mga kombinasyon niini nga mga baryable, dili siya makakuha og bisan unsa nga dugang nga impormasyon.
Mga Konsiderasyon sa Seguridad
Ang sekreto nga pamaagi sa pagpaambit ni Shamir nagsugyot seguridad sa impormasyon. Kini nagpasabot nga ang matematika lig-on bisan batok sa usa ka tig-atake nga adunay walay kinutuban nga gahum sa pag-compute. Bisan pa, ang schema naglangkob gihapon sa daghang nahibal-an nga mga isyu.
Pananglitan, ang laraw sa Shamir wala maghimo mga tipik nga susihon, nga mao, ang mga tawo gawasnon sa pagpresentar sa peke nga mga tipik ug makabalda sa pagbawi sa husto nga sekreto. Ang usa ka kaaway nga tigbantay sa tipik nga adunay igo nga kasayuran mahimo pa gani nga makahimo og laing tipik pinaagi sa pagbag-o sa imong pagkabuotan. Kini nga problema masulbad sa mapamatud-an nga sekreto nga mga pamaagi sa pagpaambit, sama sa laraw sa Feldman.
Ang laing problema mao nga ang gitas-on sa bisan unsa nga tipik katumbas sa gitas-on sa katugbang nga sekreto, mao nga ang gitas-on sa sekreto sayon ββββnga mahibal-an. Kini nga problema masulbad pinaagi sa walay hinungdan padding sekreto pinaagi sa arbitraryong mga numero hangtod sa gitakdang gitas-on.
Sa katapusan, hinungdanon nga timan-an nga ang among mga kabalaka sa seguridad mahimong molapas sa laraw mismo. Alang sa tinuod nga mga aplikasyon sa cryptographic, kanunay adunay hulga sa mga pag-atake sa side-channel, kung ang usa ka tig-atake mosulay sa pagkuha sa mapuslanon nga kasayuran gikan sa oras sa pagpatuman sa aplikasyon, pag-cache, pag-crash, ug uban pa. Kung kini usa ka kabalaka, kinahanglan nimong hunahunaon pag-ayo ang paggamit sa mga panalipod sa panahon sa pag-uswag, sama sa mga gimbuhaton ug kanunay nga pagpangita sa oras, pagpugong sa pagtipig sa memorya sa disk, ug pagkonsiderar sa daghang uban pang mga butang nga wala sa sulud sa kini nga artikulo.
Demo
sa Adunay usa ka interactive nga pagpakita sa sekreto nga pamaagi sa pagpaambit ni Shamir. Ang demonstrasyon gihimo base sa librarya , nga mismo usa ka JavaScript port sa usa ka sikat nga programa . Timan-i nga ang pagkalkula sa dagkong mga kantidad , ΠΈ mahimong magdugay.
Source: www.habr.com