Fikiria hali ambapo unahitaji kupata hifadhi ya benki. Inachukuliwa kuwa haiwezekani kabisa bila ufunguo, ambao hupewa siku ya kwanza ya kazi. Lengo lako ni kuhifadhi ufunguo kwa usalama.
Hebu tuseme unaamua kuweka ufunguo nawe wakati wote, kutoa ufikiaji wa hifadhi inavyohitajika. Lakini utagundua haraka kuwa suluhisho kama hilo haliingii vizuri katika mazoezi, kwa sababu uwepo wako wa mwili unahitajika kila wakati unapofungua hifadhi. Vipi kuhusu likizo uliyoahidiwa? Kwa kuongeza, swali ni la kutisha zaidi: je, ikiwa umepoteza ufunguo wako pekee?
Kwa kuzingatia likizo yako, unaamua kutengeneza nakala ya ufunguo na ukabidhi kwa mfanyakazi mwingine. Walakini, unaelewa kuwa hii sio bora pia. Kwa kuongeza idadi ya funguo mara mbili, pia unaongeza uwezekano wa wizi wa ufunguo mara mbili.
Kwa kukata tamaa, unaharibu nakala na kuamua kugawanya ufunguo wa asili kwa nusu. Sasa, utafikiri kwamba watu wawili wanaoaminika walio na vipande muhimu wangepaswa kuwepo ili kukusanya ufunguo na kufungua kuba. Hii ina maana kwamba mwizi anahitaji kuiba vipande viwili, ambayo ni vigumu mara mbili kuliko kuiba ufunguo mmoja. Hata hivyo, hivi karibuni unatambua kuwa mpango huu sio bora zaidi kuliko ufunguo mmoja tu, kwa sababu ikiwa mtu anapoteza nusu ya ufunguo, ufunguo kamili hauwezi kurejeshwa.
Tatizo linaweza kutatuliwa kwa mfululizo wa funguo za ziada na kufuli, lakini mbinu hii itahitaji haraka mengi funguo na kufuli. Unaamua kuwa muundo unaofaa utakuwa kushiriki ufunguo ili usalama usitegemee kabisa mtu mmoja. Pia unahitimisha kwamba lazima kuwe na kizingiti kwa idadi ya vipande ili ikiwa kipande kimoja kitapotea (au ikiwa mtu ataenda likizo), ufunguo wote unabaki kufanya kazi.
Jinsi ya kushiriki siri
Aina hii ya mpango muhimu wa usimamizi ilifikiriwa na Adi Shamir mnamo 1979 alipochapisha kazi yake . Nakala hiyo inaelezea kwa ufupi kinachojulikana 
mpango wa kizingiti wa kugawanya thamani ya siri kwa ufanisi (kama vile kitufe cha kriptografia) ndani sehemu. Kisha, wakati na wakati tu angalau ya sehemu zimekusanyika, unaweza kurejesha siri kwa urahisi .
Kwa mtazamo wa usalama, mali muhimu ya mpango huu ni kwamba mshambuliaji hapaswi kujua chochote isipokuwa ana angalau. sehemu. Hata uwepo sehemu hazipaswi kutoa habari yoyote. Tunaita mali hii usalama wa semantic.
Ufafanuzi wa polynomial
Mpango wa kizingiti cha Shamir kujengwa karibu na dhana tafsiri ya polynomial. Ikiwa hujui wazo hili, kwa kweli ni rahisi sana. Kwa kweli, ikiwa umewahi kuchora alama kwenye grafu na kisha kuziunganisha na mistari au mikunjo, tayari umeitumia!
Kupitia pointi mbili unaweza kuteka idadi isiyo na kikomo ya polynomials ya shahada ya 2. Ili kuchagua moja tu kutoka kwao, unahitaji hatua ya tatu. Mchoro:
Fikiria polynomial na shahada ya kwanza, . Ikiwa unataka kupanga utendaji huu kwenye grafu, unahitaji pointi ngapi? Naam, tunajua kwamba hii ni kazi ya mstari ambayo huunda mstari na kwa hivyo inahitaji angalau pointi mbili. Ifuatayo, fikiria kazi ya polynomial na shahada ya pili, . Hii ni kazi ya quadratic, hivyo angalau pointi tatu zinahitajika ili kupanga grafu. Vipi kuhusu polynomial na shahada ya tatu? Angalau pointi nne. Na kadhalika na kadhalika.
Jambo la kupendeza sana juu ya mali hii ni kwamba, kwa kuzingatia kiwango cha kazi ya polynomial na angalau pointi, tunaweza kupata pointi za ziada kwa kazi hii ya polynomial. Tunaita extrapolation ya pointi hizi za ziada tafsiri ya polynomial.
Kufanya siri
Labda tayari umegundua kuwa hapa ndipo mpango wa busara wa Shamir unapoingia. Wacha tuseme siri yetu - Je, . Tunaweza kugeuka kwa uhakika kwenye grafu na kuja na kazi ya polynomial yenye digrii , ambayo inakidhi hatua hii. Tukumbuke hilo itakuwa kizingiti chetu cha vipande vinavyohitajika, kwa hivyo ikiwa tunaweka kizingiti kwa vipande vitatu, lazima tuchague kazi ya polynomial na shahada ya pili.
Polynomial yetu itakuwa na fomu Ambapo ΠΈ - nambari kamili chanya zilizochaguliwa kwa nasibu. Tunaunda tu polynomial yenye digrii , ambapo mgawo wa bure - Hii ni siri yetu , na kwa kila moja ya zinazofuata masharti kuna mgawo chanya uliochaguliwa kwa nasibu. Ikiwa tunarudi kwenye mfano wa asili na kudhani kuwa , basi tunapata kazi .
Katika hatua hii tunaweza kuzalisha vipande kwa kuunganisha nambari za kipekee ndani Ambapo (kwa sababu ni siri yetu). Katika mfano huu, tunataka kusambaza vipande vinne na kizingiti cha tatu, kwa hivyo tunatoa alama kwa nasibu. na kutuma nukta moja kwa kila mmoja wa watu wanne wanaoaminika, wasimamizi wa ufunguo. Pia tunawafahamisha watu hivyo , kwa kuwa hii inachukuliwa kuwa habari ya umma na ni muhimu kwa uokoaji .
Kurejesha siri
Tayari tumejadili dhana ya tafsiri ya polynomia na jinsi inavyozingatia mpango wa kizingiti wa Shamir. . Wakati wowote watatu kati ya wadhamini wanne wanataka kurejesha , wanahitaji tu kuingiliana na pointi zake za kipekee. Kwa kufanya hivyo, wanaweza kuamua pointi zao na ukokotoa ukalimani wa polinomia wa Lagrange kwa kutumia fomula ifuatayo. Ikiwa programu ni wazi kwako kuliko hisabati, basi pi kimsingi ni opereta for, ambayo huzidisha matokeo yote, na sigma ni for, ambayo huongeza kila kitu.
Katika tunaweza kuitatua kama hii na kurudisha kazi yetu ya asili ya polynomial:
Kwa sababu tunajua hilo , kupona imefanywa kwa urahisi:
Kwa kutumia hesabu kamili isiyo salama
Ingawa tumefaulu kutumia wazo la msingi la Shamir , tumebakiwa na tatizo ambalo tumelipuuza mpaka sasa. Utendakazi wetu wa polinomia hutumia hesabu kamili isiyo salama. Kumbuka kuwa kwa kila pointi ya ziada ambayo mshambuliaji hupata kwenye grafu ya utendaji wetu, kuna uwezekano mdogo wa pointi nyingine. Unaweza kuona hii kwa macho yako mwenyewe unapopanga idadi inayoongezeka ya alama kwa kazi ya polynomial kwa kutumia hesabu kamili. Hili halina tija kwa lengo letu la usalama lililotajwa, kwa sababu mshambuliaji hapaswi kujua chochote hadi awe na angalau vipande.
Ili kuonyesha jinsi sakiti kamili ya hesabu ilivyo dhaifu, zingatia hali ambapo mshambuliaji alipata pointi mbili. na anajua habari za umma . Kutoka kwa habari hii anaweza kuamua , sawa na mbili, na uchomeke maadili yanayojulikana kwenye fomula ΠΈ .
Mshambulizi anaweza kupata , kuhesabu :
Kwa kuwa tumefafanua kama nambari kamili chanya zilizochaguliwa kwa nasibu, kuna idadi ndogo ya iwezekanavyo . Kwa kutumia habari hii, mshambuliaji anaweza kuamua , kwani chochote kikubwa kuliko 5 kitafanya hasi. Hii inageuka kuwa kweli kwani tumeamua
Mshambulizi anaweza kisha kuhesabu thamani zinazowezekana kuchukua nafasi Π² :
Na chaguzi mdogo kwa inakuwa wazi jinsi ilivyo rahisi kuchagua na kuangalia maadili . Kuna chaguzi tano tu hapa.
Kutatua tatizo kwa hesabu kamili isiyo salama
Ili kuondoa uwezekano huu, Shamir anapendekeza kutumia hesabu za msimu, kuchukua nafasi juu ya Ambapo ΠΈ - seti ya nambari zote kuu.
Wacha tukumbuke haraka jinsi hesabu ya kawaida inavyofanya kazi. Saa yenye mikono ni dhana inayofahamika. Anatumia saa ambayo ni . Mara tu mkono wa saa unapopita kumi na mbili, unarudi kwa moja. Sifa ya kuvutia ya mfumo huu ni kwamba kwa kuangalia tu saa, hatuwezi kuamua ni mapinduzi ngapi ambayo mkono wa saa umefanya. Walakini, ikiwa tunajua kuwa saa imepita mara 12 mara nne, tunaweza kuamua kabisa idadi ya masaa ambayo yamepita kwa kutumia fomula rahisi. Ambapo ndiye mgawanyiko wetu (hapa ), ni mgawo (ni mara ngapi kigawanyiko kinaingia kwenye nambari asilia bila salio, hapa ), na ni salio, ambayo kawaida hurejesha simu ya waendeshaji modulo (hapa ) Kujua maadili haya yote huturuhusu kutatua equation , lakini tukikosa mgawo, hatutaweza kamwe kurejesha thamani asili.
Tunaweza kuonyesha jinsi hii inavyoboresha usalama wa mpango wetu kwa kutumia mpango huo kwa mfano wetu wa awali na kutumia . Utendaji wetu mpya wa polynomial , na pointi mpya . Sasa watunzaji muhimu wanaweza tena kutumia tafsiri ya polinomia kuunda upya kazi yetu, wakati huu tu shughuli za kuongeza na kuzidisha lazima ziambatane na upunguzaji wa modulo. (mfano ).
Kwa kutumia mfano huu mpya, tuchukulie kuwa mshambuliaji alijifunza mambo mawili kati ya haya mapya, , na taarifa za umma . Wakati huu, mshambuliaji, kulingana na taarifa zote anazo, hutoa kazi zifuatazo, wapi ni seti ya nambari zote chanya, na inawakilisha mgawo wa moduli .
Sasa mshambuliaji wetu anapata tena , kuhesabu :
Kisha anajaribu tena kuchukua nafasi Π² :
Wakati huu ana tatizo kubwa. Fomula inakosa maadili , ΠΈ . Kwa kuwa kuna idadi isiyo na kikomo ya mchanganyiko wa vigezo hivi, hawezi kupata maelezo yoyote ya ziada.
Mazingatio ya Usalama
Mpango wa kushiriki siri wa Shamir unapendekeza usalama kutoka kwa mtazamo wa nadharia ya habari. Hii ina maana kwamba hisabati ni sugu hata dhidi ya mshambuliaji aliye na uwezo wa kompyuta usio na kikomo. Walakini, mzunguko bado una maswala kadhaa yanayojulikana.
Kwa mfano, mpango wa Shamir hauunda vipande vya kukaguliwa, yaani, watu wanaweza kuwasilisha kwa uhuru vipande vya uwongo na kuingilia kati urejeshaji wa siri sahihi. Mlinzi wa vipande vya uhasama na habari za kutosha anaweza hata kutoa kipande kingine kwa kubadilisha kwa hiari yako mwenyewe. Tatizo hili linatatuliwa kwa kutumia mipango ya kugawana siri inayoweza kuthibitishwa, kama vile mpango wa Feldman.
Shida nyingine ni kwamba urefu wa kipande chochote ni sawa na urefu wa siri inayolingana, kwa hivyo urefu wa siri ni rahisi kuamua. Tatizo hili linaweza kutatuliwa kwa mambo madogo pedi siri na nambari za kiholela hadi urefu uliowekwa.
Hatimaye, ni muhimu kutambua kwamba masuala yetu ya usalama yanaweza kuenea zaidi ya muundo wenyewe. Kwa programu za kriptografia za ulimwengu halisi, mara nyingi kuna tishio la mashambulizi ya idhaa ya kando ambapo mshambulizi anajaribu kutoa taarifa muhimu kutoka kwa muda wa utekelezaji wa programu, kuweka akiba, kuacha kufanya kazi, n.k. Ikiwa hili ni jambo la kutia wasiwasi, uzingatiaji wa makini unapaswa kuzingatiwa wakati wa utayarishaji wa kutumia hatua za ulinzi kama vile vitendakazi na ukaguzi wa mara kwa mara, kuzuia kumbukumbu kuhifadhiwa kwenye diski, na mambo mengine kadhaa ambayo hayako zaidi ya upeo wa makala haya.
NI
Cha Kuna onyesho shirikishi la mpango wa kushiriki siri wa Shamir. Maonyesho kulingana na maktaba , ambayo yenyewe ni bandari ya JavaScript ya programu maarufu . Kumbuka kwamba kuhesabu maadili makubwa , ΠΈ inaweza kuchukua muda.
Chanzo: mapenzi.com