Isaalang-alang ang isang sitwasyon kung saan kailangan mong i-secure ang isang bank vault. Ito ay itinuturing na ganap na hindi malulutas nang walang susi, na ibinibigay sa iyo sa pinakaunang araw ng trabaho. Ang iyong layunin ay ligtas na iimbak ang susi.
Sabihin nating nagpasya kang panatilihin ang susi sa iyo sa lahat ng oras, na nagbibigay ng access sa storage kung kinakailangan. Ngunit mabilis mong mapagtanto na ang gayong solusyon ay hindi nasusukat nang maayos sa pagsasanay, dahil ang iyong pisikal na presensya ay kinakailangan sa tuwing bubuksan mo ang imbakan. Paano ang bakasyon na ipinangako sa iyo? Bilang karagdagan, ang tanong ay mas nakakatakot: paano kung nawala mo ang iyong tanging susi?
Habang nasa isip ang iyong bakasyon, nagpasya kang gumawa ng kopya ng susi at ipagkatiwala ito sa ibang empleyado. Gayunpaman, naiintindihan mo na hindi rin ito perpekto. Sa pamamagitan ng pagdodoble sa bilang ng mga susi, doblehin mo rin ang mga pagkakataon ng pagnanakaw ng susi.
Sa desperasyon, sirain mo ang duplicate at magpasya na hatiin ang orihinal na susi sa kalahati. Ngayon, maiisip mo na ang dalawang pinagkakatiwalaang tao na may mga pangunahing fragment ay kailangang pisikal na naroroon upang kolektahin ang susi at buksan ang vault. Nangangahulugan ito na ang isang magnanakaw ay kailangang magnakaw ng dalawang piraso, na dalawang beses na mas mahirap kaysa sa pagnanakaw ng isang susi. Gayunpaman, napagtanto mo sa lalong madaling panahon na ang pamamaraan na ito ay hindi mas mahusay kaysa sa isang susi lamang, dahil kung ang isang tao ay nawalan ng kalahating susi, ang buong susi ay hindi na mababawi.
Ang problema ay maaaring malutas sa isang serye ng mga karagdagang susi at kandado, ngunit ang diskarte na ito ay mabilis na mangangailangan ΠΌΠ½ΠΎΠ³ΠΎ mga susi at kandado. Magpasya ka na ang perpektong disenyo ay upang ibahagi ang susi upang ang seguridad ay hindi ganap na umasa sa isang tao. Napagpasyahan mo rin na dapat mayroong ilang threshold para sa bilang ng mga fragment upang kung mawala ang isang fragment (o kung magbabakasyon ang isang tao), mananatiling gumagana ang buong key.
Paano magbahagi ng lihim
Ang ganitong uri ng key management scheme ay naisip ni Adi Shamir noong 1979 nang ilathala niya ang kanyang trabaho . Maikling ipinaliwanag ng artikulo ang tinatawag na 
threshold scheme para sa mahusay na paghahati ng isang lihim na halaga (tulad ng isang cryptographic key) sa mga bahagi. Pagkatapos, kailan at kailan lang at least ng mga bahagi ay binuo, maaari mong madaling ibalik ang lihim .
Mula sa pananaw ng seguridad, isang mahalagang pag-aari ng pamamaraang ito ay hindi dapat malaman ng umaatake ang anumang bagay maliban kung mayroon siyang hindi bababa sa mga bahagi. Kahit ang presensya ang mga bahagi ay hindi dapat magbigay ng anumang impormasyon. Tinatawag namin itong ari-arian semantikong seguridad.
Polynomial interpolation
Shamir threshold scheme binuo sa paligid ng konsepto polynomial interpolation. Kung hindi ka pamilyar sa konseptong ito, ito ay talagang simple. Sa katunayan, kung nakaguhit ka na ng mga punto sa isang graph at pagkatapos ay ikinonekta ang mga ito sa mga linya o kurba, nagamit mo na ito!
Sa pamamagitan ng dalawang puntos maaari kang gumuhit ng walang limitasyong bilang ng mga polynomial ng degree 2. Upang pumili ng isa lamang mula sa kanila, kailangan mo ng ikatlong punto. Ilustrasyon:
Isaalang-alang ang isang polynomial na may degree one, . Kung gusto mong i-plot ang function na ito sa isang graph, ilang puntos ang kailangan mo? Well, alam namin na ito ay isang linear function na bumubuo ng isang linya at kaya kailangan nito ng hindi bababa sa dalawang puntos. Susunod, isaalang-alang ang isang polynomial function na may degree two, . Ito ay isang quadratic function, kaya hindi bababa sa tatlong puntos ang kinakailangan upang i-plot ang graph. Paano ang tungkol sa isang polynomial na may tatlong degree? Hindi bababa sa apat na puntos. At iba pa.
Ang talagang cool na bagay tungkol sa ari-arian na ito ay na, na ibinigay ang antas ng polynomial function at hindi bababa sa puntos, maaari tayong makakuha ng mga karagdagang puntos para sa polynomial function na ito. Tinatawag namin ang extrapolation ng mga karagdagang puntos na ito polynomial interpolation.
Gumagawa ng sikreto
Maaaring napagtanto mo na na dito pumapasok ang matalinong pakana ni Shamir. Sabihin na natin ang ating sikreto - Ay . Maaari tayong lumiko sa isang punto sa graph at makabuo ng isang polynomial function na may degree , na nakakatugon sa puntong ito. Paalalahanan ka namin ang ating magiging threshold ng mga kinakailangang fragment, kaya kung itatakda natin ang threshold sa tatlong fragment, dapat tayong pumili ng polynomial function na may degree two.
Ang aming polynomial ay magkakaroon ng form Saan ΠΈ β random na piniling positive integer. Gumagawa lang kami ng polynomial na may degree , kung saan ang libreng koepisyent - Ito ang aming sikreto , at para sa bawat isa sa mga kasunod may random na napiling positive coefficient. Kung babalik tayo sa orihinal na halimbawa at ipagpalagay na , pagkatapos ay makuha namin ang function .
Sa puntong ito maaari tayong bumuo ng mga fragment sa pamamagitan ng pagkonekta natatanging integer sa Saan (secret lang kasi namin yun). Sa halimbawang ito, gusto naming ipamahagi ang apat na fragment na may threshold na tatlo, kaya random kaming bumubuo ng mga puntos at magpadala ng isang punto sa bawat isa sa apat na pinagkakatiwalaang tao, ang mga tagapag-alaga ng susi. Ipinapaalam din namin ito sa mga tao , dahil ito ay itinuturing na pampublikong impormasyon at kinakailangan para sa pagbawi .
Pagbawi ng sikreto
Napag-usapan na natin ang konsepto ng polynomial interpolation at kung paano ito sumasailalim sa threshold scheme ni Shamir . Kapag may tatlo sa apat na katiwala ang gustong ibalik , kailangan lang nilang mag-interpolate na may sariling natatanging mga puntos. Upang gawin ito, maaari nilang matukoy ang kanilang mga punto at kalkulahin ang Lagrange interpolation polynomial gamit ang sumusunod na formula. Kung ang programming ay mas malinaw sa iyo kaysa sa matematika, ang pi ay mahalagang operator for, na nagpaparami sa lahat ng resulta, at ang sigma ay for, na nagdaragdag ng lahat.
Sa maaari naming malutas ito tulad nito at ibalik ang aming orihinal na polynomial function:
Since alam naman natin yun , pagbawi tapos na lang:
Paggamit ng hindi ligtas na integer arithmetic
Bagama't matagumpay nating nailapat ang pangunahing ideya ni Shamir , may natitira tayong problema na hanggang ngayon ay hindi natin pinapansin. Ang aming polynomial function ay gumagamit ng hindi ligtas na integer arithmetic. Tandaan na para sa bawat karagdagang punto na nakukuha ng isang attacker sa graph ng aming function, may mas kaunting mga posibilidad para sa iba pang mga puntos. Makikita mo ito sa sarili mong mga mata kapag nag-plot ka ng tumataas na bilang ng mga puntos para sa isang polynomial function gamit ang integer arithmetic. Ito ay kontra-produktibo sa aming nakasaad na layuning pangseguridad, dahil ang umaatake ay dapat na walang alam hangga't hindi sila mayroon mga fragment.
Upang ipakita kung gaano kahina ang integer arithmetic circuit, isaalang-alang ang isang senaryo kung saan nakakuha ang isang attacker ng dalawang puntos. at alam ang pampublikong impormasyon na . Mula sa impormasyong ito ay mahihinuha niya , katumbas ng dalawa, at isaksak ang mga kilalang halaga sa formula ΠΈ .
Pagkatapos ay mahahanap ng umaatake , nagbibilang :
Dahil natukoy natin bilang random na piniling positive integers, may limitadong bilang ng posible . Gamit ang impormasyong ito, maaaring maghinuha ang isang umaatake , dahil magagawa ng anumang mas malaki sa 5 negatibo. Ito ay lumalabas na totoo dahil natukoy na natin
Pagkatapos ay makalkula ng umaatake ang mga posibleng halaga pinapalitan Π² :
Sa limitadong mga pagpipilian para sa nagiging malinaw kung gaano kadaling piliin at suriin ang mga halaga . Mayroon lamang limang mga pagpipilian dito.
Paglutas ng problema sa hindi ligtas na integer arithmetic
Upang alisin ang kahinaan na ito, iminumungkahi ni Shamir ang paggamit ng modular arithmetic, pagpapalit sa Saan ΠΈ β ang set ng lahat ng prime number.
Mabilis nating tandaan kung paano gumagana ang modular arithmetic. Ang isang orasan na may mga kamay ay isang pamilyar na konsepto. Gumagamit siya ng relo . Sa sandaling ang kamay ng oras ay lumampas sa alas-dose, ito ay bumalik sa isa. Ang isang kawili-wiling katangian ng sistemang ito ay na sa pamamagitan lamang ng pagtingin sa orasan, hindi natin mahihinuha kung gaano karaming mga rebolusyon ang ginawa ng kamay ng oras. Gayunpaman, kung alam natin na ang kamay ng oras ay lumipas ng 12 apat na beses, maaari nating ganap na matukoy ang bilang ng mga oras na lumipas gamit ang isang simpleng formula Saan ang ating divisor (dito ), ay ang koepisyent (ilang beses napupunta ang divisor sa orihinal na numero nang walang natitira, dito ), at ay ang natitira, na karaniwang nagbabalik ng isang modulo operator na tawag (dito ). Ang pag-alam sa lahat ng mga halagang ito ay nagpapahintulot sa amin na malutas ang equation para sa , ngunit kung makaligtaan natin ang koepisyent, hindi na natin maibabalik ang orihinal na halaga.
Maaari naming ipakita kung paano nito pinapabuti ang seguridad ng aming scheme sa pamamagitan ng paglalapat ng scheme sa aming nakaraang halimbawa at paggamit . Ang aming bagong polynomial function , at ang mga bagong puntos . Ngayon ang mga pangunahing tagabantay ay maaaring muling gumamit ng polynomial interpolation upang muling buuin ang aming function, tanging sa pagkakataong ito ang pagdaragdag at pagpaparami ng mga operasyon ay dapat na sinamahan ng modulo reduction (eg ).
Gamit ang bagong halimbawang ito, ipagpalagay natin na natutunan ng umaatake ang dalawa sa mga bagong puntong ito, , at pampublikong impormasyon . Sa pagkakataong ito, ang umaatake, batay sa lahat ng impormasyong mayroon siya, ay naglalabas ng mga sumusunod na function, kung saan ay ang set ng lahat ng positive integers, at kumakatawan sa modulus coefficient .
Ngayon ay nakahanap muli ang aming attacker , pagkalkula :
Pagkatapos ay sinubukan niyang muli pinapalitan Π² :
This time may mabigat siyang problema. Mga nawawalang halaga ng formula , ΠΈ . Dahil mayroong isang walang katapusang bilang ng mga kumbinasyon ng mga variable na ito, hindi siya makakakuha ng anumang karagdagang impormasyon.
Mga Pagsasaalang-alang sa Seguridad
Iminumungkahi ng lihim na pamamaraan ng pagbabahagi ni Shamir seguridad mula sa punto ng view ng teorya ng impormasyon. Nangangahulugan ito na ang matematika ay lumalaban kahit na laban sa isang umaatake na may walang limitasyong kapangyarihan sa pag-compute. Gayunpaman, ang circuit ay naglalaman pa rin ng ilang mga kilalang isyu.
Halimbawa, hindi lumilikha ang pamamaraan ni Shamir mga fragment na susuriin, iyon ay, ang mga tao ay maaaring malayang magpakita ng mga pekeng fragment at makagambala sa pagbawi ng tamang lihim. Ang isang pagalit na tagabantay ng fragment na may sapat na impormasyon ay maaaring makagawa ng isa pang fragment sa pamamagitan ng pagbabago sa iyong sariling paghuhusga. Ang problemang ito ay nalutas gamit napapatunayan na mga scheme ng lihim na pagbabahagi, gaya ng pakana ni Feldman.
Ang isa pang problema ay ang haba ng anumang fragment ay katumbas ng haba ng kaukulang lihim, kaya ang haba ng lihim ay madaling matukoy. Ang problemang ito ay maaaring malutas sa pamamagitan ng walang kabuluhan padding lihim na may mga arbitrary na numero hanggang sa isang nakapirming haba.
Panghuli, mahalagang tandaan na ang aming mga alalahanin sa seguridad ay maaaring lumampas sa disenyo mismo. Para sa mga real-world na cryptographic application, kadalasang may banta ng mga pag-atake sa side-channel kung saan sinusubukan ng isang attacker na kunin ang kapaki-pakinabang na impormasyon mula sa oras ng pagpapatupad ng application, pag-cache, pag-crash, atbp. Kung ito ay isang alalahanin, ang maingat na pagsasaalang-alang ay dapat ibigay sa panahon ng pag-unlad sa paggamit ng mga proteksiyon na hakbang tulad ng mga function at palagiang-oras na paghahanap, pagpigil sa memorya mula sa pag-save sa disk, at ilang iba pang mga pagsasaalang-alang na lampas sa saklaw ng artikulong ito.
Demo
Sa Mayroong isang interactive na pagpapakita ng lihim na pamamaraan ng pagbabahagi ni Shamir. Demonstrasyon batay sa aklatan , na mismo ay isang JavaScript port ng sikat na programa . Tandaan na ang pagkalkula ng malalaking halaga , ΠΈ maaaring tumagal ng ilang oras.
Pinagmulan: www.habr.com