Банктык сейфти камсыз кылуу керек болгон сценарийди карап көрөлү. Ачкычсыз бул таптакыр алынгыс болуп эсептелет, ал сизге жумуштун биринчи күнүндө берилет. Сиздин максат - ачкычты коопсуз сактоо.

Керек болсо сактагычка кирүү мүмкүнчүлүгүн берип, ачкычты ар дайым жаныңызда сактоону чечтиңиз дейли. Бирок, мындай чечим иш жүзүндө жакшы масштабда эмес экенин тез эле түшүнөсүз, анткени сактоону ачкан сайын сиздин физикалык катышуусуңуз талап кылынат. Сизге убада кылынган эс алуу жөнүндө эмне айтууга болот? Андан тышкары, суроо андан да коркунучтуу: эгер сиз жалгыз ачкычыңызды жоготуп алсаңызчы?

Эс алууңузду эске алып, ачкычтын көчүрмөсүн жасап, аны башка кызматкерге тапшырууну чечесиз. Бирок, бул да идеалдуу эмес экенин түшүнөсүз. Ачкычтардын санын эки эсеге көбөйтүү менен, сиз ачкыч уурдоо мүмкүнчүлүгүн да эки эсеге көбөйтөсүз.

Айласы кеткенде, сиз дубликатты жок кылып, баштапкы ачкычты экиге бөлүүнү чечесиз. Эми сиз ачкычты чогултуу жана сактагычты ачуу үчүн негизги фрагменттери бар эки ишенимдүү адам физикалык жактан болушу керек деп ойлойсуз. Бул ууру эки даана уурдашы керек дегенди билдирет, бул бир ачкычты уурдоодон эки эсе кыйын. Бирок, көп өтпөй бул схема бир ачкычтан алда канча жакшы эмес экенин түшүнөсүз, анткени кимдир бирөө жарым ачкычты жоготуп алса, толук ачкычты калыбына келтирүү мүмкүн эмес.

Көйгөй бир катар кошумча ачкычтар жана кулпулар менен чечилиши мүмкүн, бирок бул ыкма тез арада талап кылынат много ачкычтар жана кулпулар. Коопсуздук толугу менен бир адамга көз каранды болбошу үчүн ачкычты бөлүшүү идеалдуу дизайн деп чечтиңиз. Сиз ошондой эле фрагменттердин саны үчүн кандайдыр бир босого болушу керек деген тыянакка келесиз, эгер бир фрагмент жоголсо (же адам эс алууга кетсе), ачкыч бүт бойдон иштей берет.

Кантип сыр бөлүшүү керек

Негизги башкаруу схемасынын бул түрү жөнүндө Ади Шамир 1979-жылы өз ишин жарыялаганда ойлонгон "Сырды кантип бөлүшүү керек". Макала кыскача деп аталганды түшүндүрөт жашыруун маанини (мисалы, криптографиялык ачкыч) натыйжалуу бөлүү үчүн босого схемасы бөлүктөр. Андан кийин, качан жана качан гана чейин бөлүктөрү чогулган, сиз оңой эле сырды калыбына келтире аласыз .

Коопсуздук көз карашынан алганда, бул схеманын маанилүү касиети - чабуулчу, жок эле дегенде, жок дегенде, эч нерсени билбеши керек. бөлүктөр. Жада калса катышуусу бөлүктөрү эч кандай маалымат бербеши керек. Биз бул мүлк деп аталат семантикалык коопсуздук.

Полиномдук интерполяция

Шамир босого схемасы концепциянын айланасында курулган полиномдук интерполяция. Эгер сиз бул түшүнүк менен тааныш эмес болсоңуз, анда бул абдан жөнөкөй. Чынында, эгер сиз качандыр бир графикке чекиттерди тартып, анан аларды сызыктар же ийри сызыктар менен бириктирген болсоңуз, анда сиз аны мурунтан эле колдонгонсуз!

Эки чекит аркылуу чексиз сандагы 2-даражадагы көп мүчөлөрдү тарта аласыз. Алардын ичинен бирөөнү тандоо үчүн сизге үчүнчү чекит керек. Иллюстрация: Wikipedia

Биринчи даражадагы көп мүчөнү карап көрөлү, . Бул функцияны графикке түшүргүңүз келсе, сизге канча пункт керек? Ооба, биз билебиз, бул сызык түзүүчү сызыктуу функция жана андыктан ага жок дегенде эки чекит керек. Андан кийин, экинчи даражадагы көп мүчөлүү функцияны карап көрөлү, . Бул квадраттык функция, ошондуктан графикти түзүү үчүн жок дегенде үч чекит талап кылынат. Үчүнчү даражадагы көп мүчө жөнүндө эмне айтууга болот? Жок дегенде төрт упай. Жана башкалар жана башкалар.

Бул касиеттин эң сонун жагы, полиномдук функциянын даражасын эске алганда жана жок дегенде упайлар болсо, бул полиномдук функция үчүн кошумча упайларды чыгара алабыз. Бул кошумча пункттарды экстраполяция деп атайбыз полиномдук интерполяция.

Жашыруун сыр түзүү

Шамирдин айлакер схемасы дал ушул жерден ишке ашарын түшүнгөн чыгарсыз. Сырыбызды айталы - аны . Биз бура алабыз графиктин бир чекитине жана даражасы бар көп мүчөлүү функцияны ойлоп табыңыз , бул пунктту канааттандырат. Ошону эске салалы биздин талап кылынган фрагменттердин босогосу болот, ошондуктан биз босогону үч фрагментке койсок, экинчи даражадагы көп мүчөлүү функцияны тандашыбыз керек.

Биздин полином формага ээ болот кайда и — кокус тандалып алынган оң бүтүн сандар. Биз жөн гана даражасы бар көп мүчө куруп жатабыз , мында эркин коэффициент  - Бул биздин сырыбыз , жана кийинкилердин ар бири үчүн кокусунан тандалып алынган оң коэффициент бар. Баштапкы мисалга кайрылып, ошону ойлосок , анда биз функцияны алабыз .

Бул учурда биз туташтыруу менен фрагменттерди түзө алабыз уникалдуу бүтүн сандар кайда (анткени бул биздин сырыбыз). Бул мисалда биз үч босого менен төрт фрагментти бөлүштүргүбүз келет, ошондуктан биз туш келди упайларды түзөбүз. жана ачкычтын сакчылары болгон төрт ишенимдүү адамдын ар бирине бирден упай жөнөтүңүз. Муну элге да билдиребиз , анткени бул коомдук маалымат болуп эсептелет жана калыбына келтирүү үчүн зарыл .

Сырды калыбына келтирүү

Биз буга чейин полиномдук интерполяция концепциясын жана ал Шамирдин босого схемасынын негизин кантип түзөрүн талкууладык. . Төрт ишенимдүү адамдын үчөө калыбына келтиргиси келгенде , аларды интерполяциялоо гана керек өзүнүн уникалдуу пункттары менен. Бул үчүн алар өз упайларын аныктай алышат жана Лагранж интерполяциялык полиномиясын төмөнкү формула менен эсептегиле. Эгер программалоо сизге математикага караганда түшүнүктүү болсо, анда pi негизинен оператор болуп саналат for, бардык натыйжаларды көбөйтөт жана сигма болуп саналат for, бул бардыгын кошот.

боюнча биз аны ушинтип чечип, баштапкы полиномдук функциябызды кайтара алабыз:

Анткени биз муну билебиз , калыбына келтирүү жөн гана жасалган:

Кооптуу бүтүн арифметиканы колдонуу

Шамирдин негизги идеясын ийгиликтүү ишке ашырдык да , биз ушул убакка чейин көңүл бурбай келген көйгөйүбүз менен калдык. Биздин полиномдук функция кооптуу бүтүн арифметиканы колдонот. Биздин функциянын графигинде чабуулчу алган ар бир кошумча чекит үчүн башка чекиттер үчүн азыраак мүмкүнчүлүктөр бар экенин эске алыңыз. Бүтүн сандык арифметиканы колдонуп, көп мүчөлүү функция үчүн чекиттердин көбөйүп бараткан санын түзгөндө муну өз көзүңүз менен көрө аласыз. Бул биздин коопсуздук максатыбызга терс таасирин тийгизет, анткени чабуулчу жок дегенде эч нерсе билмейинче эч нерсе билбеши керек фрагменттери.

Бүтүн арифметикалык схема канчалык алсыз экенин көрсөтүү үчүн, чабуулчу эки упай алган сценарийди карап көрөлү. жана коомдук маалыматты билет . Бул маалыматтардан ал жыйынтык чыгара алат , экиге барабар жана формулага белгилүү маанилерди киргизиңиз и .

Андан кийин чабуулчу таба алат , эсептөө :

Биз аныктагандан бери кокус тандалып алынган оң бүтүн сандар катары, мүмкүн чектелген саны бар . Бул маалыматты колдонуп, чабуулчу жыйынтык чыгара алат , анткени 5тен чоңураак нерсе кылат терс. Бул биз аныктагандан бери чын болуп чыкты

Андан кийин чабуулчу мүмкүн болгон маанилерди эсептей алат , алмаштыруу в :

үчүн чектелген параметрлери менен баалуулуктарды тандоо жана текшерүү канчалык оңой экени айкын болот . Бул жерде беш гана вариант бар.

Кооптуу бүтүн арифметика менен маселени чечүү

Бул алсыздыкты жоюу үчүн, Шамир алмаштыруучу модулдук арифметиканы колдонууну сунуштайт боюнча кайда и — бардык жай сандардын жыйындысы.

Келгиле, модулдук арифметика кантип иштээрин тез эле эстеп көрөлү. Колдору бар саат - бул тааныш түшүнүк. Ал саатты колдонот . Саат жебеси он экиден өткөндө кайра бирге келет. Бул системанын эң кызыктуу бир өзгөчөлүгү – саатты карап эле, саат жебесинин канча айлангандыгын аныктай албайбыз. Бирок, саат жебеси 12 төрт жолу өткөнүн билсек, жөнөкөй формула менен өткөн сааттардын санын толук аныктай алабыз. кайда  биздин бөлүүчү (бул жерде ),  коэффицент (бөлүүчү баштапкы санга калдыгы жок канча жолу кирет, бул жерде ), жана  калган, адатта, модулдук оператордун чакырыгын кайтарат (бул жерде ). Бардык бул баалуулуктарды билүү бизге теңдемени чечүүгө мүмкүндүк берет , бирок биз коэффициентти өткөрүп жиберсек, биз эч качан баштапкы маанини калыбына келтире албайбыз.

Схеманы мурунку мисалга колдонуу жана колдонуу менен бул схемабыздын коопсуздугун кантип жакшыртаарын көрсөтө алабыз. . Биздин жаңы көп мүчөлүү функция , жана жаңы пункттар . Эми негизги сактоочулар биздин функциябызды реконструкциялоо үчүн дагы бир жолу полиномдук интерполяцияны колдоно алышат, бул жолу гана кошуу жана көбөйтүү операциялары модулдук кыскартуу менен коштолушу керек (мисалы, ).

Бул жаңы мисалды колдонуу менен, чабуулчу бул жаңы пункттардын экөөсүн үйрөндү деп ойлойлу, , жана коомдук маалымат . Бул жолу чабуулчу, колунда болгон бардык маалыматтарга таянып, төмөнкү функцияларды чыгарат, кайда  бардык оң бүтүн сандардын жыйындысы жана модулдук коэффициентти билдирет .

Азыр биздин чабуулчу дагы табат , эсептөө :

Анан кайра аракет кылат , алмаштыруу в :

Бул жолу анын олуттуу көйгөйү бар. Формулада маанилер жок , и . Бул өзгөрмөлөрдүн чексиз сандагы комбинациялары бар болгондуктан, ал эч кандай кошумча маалымат ала албайт.

Коопсуздукту кароо

Шамирдин жашыруун бөлүшүү схемасы сунуш кылат маалымат теориясынын көз карашынан алганда коопсуздук. Бул математика чексиз эсептөө күчү менен чабуулчуга да туруштук берет дегенди билдирет. Бирок, схема дагы эле бир нече белгилүү маселелерди камтыйт.

Мисалы, Шамирдин схемасы түзбөйт сыныктары текшерилет, башкача айтканда, адамдар жасалма фрагменттерди эркин көрсөтүп, туура сырды калыбына келтирүүгө тоскоолдук кыла алышат. Жетиштүү маалыматка ээ болгон душмандык фрагментти сактоочу, ал тургай, өзгөртүү менен башка фрагментти чыгарышы мүмкүн өз каалоосу боюнча. Бул маселе колдонуу менен чечилет текшерилүүчү жашыруун бөлүшүү схемаларыФельдмандын схемасы сыяктуу.

Дагы бир маселе, кандайдыр бир фрагменттин узундугу тиешелүү сырдын узундугуна барабар болгондуктан, сырдын узундугун аныктоо оңой. Бул маселени майда-чүйдөсүнө чейин чечсе болот толтуруу белгиленген узундукка чейин каалаган сандар менен сыр.

Акырында, биздин коопсуздук маселелери дизайндын өзүнөн тышкары болушу мүмкүн экенин белгилей кетүү маанилүү. Чыныгы криптографиялык тиркемелер үчүн көбүнчө каптал канал чабуулдарынын коркунучу бар, анда чабуулчу тиркемени аткаруу убактысынан, кэштен, кыйроолордон жана башкалардан пайдалуу маалыматты алууга аракет кылат. Эгер бул тынчсызданууну жаратса, иштеп чыгууда функциялар жана туруктуу убакыт издөө сыяктуу коргоо чараларын колдонуу, эстутумдун дискке сакталышына жол бербөө жана ушул макаланын алкагына кирбеген бир катар башка ойлорду кылдаттык менен карап чыгуу керек.

Демо

боюнча бул барак Шамирдин жашыруун бөлүшүү схемасынын интерактивдүү демонстрациясы бар. Китепкананын негизинде демонстрация ssss-js, ал өзү популярдуу программанын JavaScript порту суроолор. Чоң маанилерди эсептөөгө көңүл буруңуз , и бир аз убакыт талап кылынышы мүмкүн.

Source: www.habr.com