Сенарияеро баррасӣ кунед, ки дар он шумо бояд хазинаи бонкиро таъмин кунед. Он бе калид, ки ба шумо дар рӯзи аввали кор дода мешавад, комилан ғайриимкон ҳисобида мешавад. Ҳадафи шумо бехатар нигоҳ доштани калид аст.
Фарз мекунем, ки шумо қарор медиҳед, ки калидро ҳамеша бо худ нигоҳ доред ва дар ҳолати зарурӣ дастрасӣ ба анборро таъмин кунед. Аммо шумо ба зудӣ хоҳед фаҳмид, ки чунин ҳалли амалия хуб нест, зеро ҳузури ҷисмонии шумо ҳар дафъае, ки шумо анборро мекушоед, талаб карда мешавад. Дар бораи таътили ба шумо ваъдашуда чӣ гуфтан мумкин аст? Илова бар ин, савол боз ҳам даҳшатовартар аст: агар шумо калиди ягонаи худро гум кунед, чӣ мешавад?
Бо дарназардошти таътили худ, шумо қарор медиҳед, ки калидро нусхабардорӣ кунед ва онро ба корманди дигар супоред. Аммо, шумо мефаҳмед, ки ин ҳам идеалӣ нест. Бо ду баробар зиёд кардани шумораи калидҳо, шумо инчунин эҳтимолияти дуздии калидҳоро ду баробар зиёд мекунед.
Дар ноумедӣ, шумо нусхаи нусхаро нест мекунед ва қарор мекунед, ки калиди аслиро ба ду тақсим кунед. Акнун, шумо фикр мекунед, ки ду шахси боэътимод бо пораҳои калидӣ бояд ҷисман ҳузур дошта бошанд, то калидро ҷамъоварӣ кунанд ва анборро кушоянд. Ин маънои онро дорад, ки дузд бояд ду дона дуздад, ки ин назар ба дуздидани як калид ду маротиба мушкилтар аст. Бо вуҷуди ин, шумо ба зудӣ дарк мекунед, ки ин схема аз як калид беҳтар нест, зеро агар касе нисфи калидро гум кунад, калиди пурраро барқарор кардан мумкин нест.
Мушкилотро бо як қатор калидҳо ва қулфҳои иловагӣ ҳал кардан мумкин аст, аммо ин равиш зуд талаб мекунад много калидҳо ва қулфҳо. Шумо қарор мекунед, ки тарҳи идеалӣ мубодилаи калид аст, то амният комилан ба як шахс такя накунад. Шумо инчунин ба хулосае омадед, ки барои шумораи порчаҳо бояд ҳадди аққал вуҷуд дошта бошад, то ки агар як порча гум шавад (ё агар шахс ба рухсатӣ равад), тамоми калид фаъол боқӣ мемонад.
Чӣ тавр мубодила кардани сир
Дар бораи ин намуди нақшаи идоракунии калидӣ Ади Шамир соли 1979 ҳангоми нашри кори худ фикр карда буд . Мақола ба истилоҳ мухтасар шарҳ медиҳад 
схемаи ҳадди барои самаранок тақсим кардани арзиши махфӣ (масалан калиди криптографӣ) ба қисмҳо. Пас, кай ва танҳо вақте ки ҳадди аққал аз он қисмҳо ҷамъ шудаанд, шумо метавонед ба осонӣ сирро барқарор кунед .
Аз нуқтаи назари амният, як хусусияти муҳими ин нақша дар он аст, ки ҳамлагар набояд комилан чизеро донад, агар ҳадди ақалл қисмҳо. Ҳатто ҳузури қисмҳо набояд ягон маълумот пешниҳод кунанд. Мо ин амволро меномем амнияти семантикӣ.
Интерполясияи полиномӣ
Схемаи хадди Шамир дар атрофи консепсия сохта шудааст интерполяцияи полиномӣ. Агар шумо бо ин консепсия ошно набошед, он воқеан хеле содда аст. Дарвоқеъ, агар шумо ягон вақт нуқтаҳоро дар график кашида бошед ва онҳоро бо хатҳо ё каҷҳо пайваст карда бошед, шумо аллакай онро истифода кардаед!
Тавассути ду нуқта шумо метавонед шумораи номаҳдуди полиномҳои дараҷаи 2-ро кашед. Барои интихоби ягонаи онҳо, ба шумо нуқтаи сеюм лозим аст. Иллюстрация:
Як полиноми дорои дараҷаи якумро баррасӣ кунед, . Агар шумо хоҳед, ки ин функсияро дар график ҷойгир кунед, ба шумо чанд нукта лозим аст? Хуб, мо медонем, ки ин функсияи хатӣ аст, ки хатро ташкил медиҳад ва аз ин рӯ, ҳадди аққал ду нуқта лозим аст. Минбаъд, функсияи полиномиро бо дараҷаи дуюм баррасӣ кунед, . Ин функсияи квадратӣ аст, бинобар ин барои кашидани график ҳадди аққал се нуқта лозим аст. Дар бораи полиномии дараҷаи се чӣ гуфтан мумкин аст? Камаш чор хол. Ва гайра ва гайра.
Чизи воқеан аҷиби ин амвол дар он аст, ки бо назардошти дараҷаи функсияи полиномӣ ва ҳадди аққал Нуқтаҳо, мо метавонем барои ин функсияи полиномӣ нуқтаҳои иловагӣ ба даст орем. Мо экстраполяцияи ин нуктаҳои иловагӣ меномем интерполяцияи полиномӣ.
Сохтани сирр
Шояд шумо аллакай дарк карда бошед, ки дар ин чо накшаи мохирона Шомир ба кор медарояд. Биёед сирри худро бигӯем Оё . Мо метавонем гардем ба як нуқтаи дар график ва функсияи полиномиро бо дараҷа пайдо кунед , ки ин нуктаро конеъ мегардонад. Хотиррасон мекунем, ки остонаи порчаҳои зарурии мо хоҳад буд, бинобар ин, агар мо ҳадди ақалро ба се порча муқаррар кунем, мо бояд функсияи полиномии дараҷаи дуюмро интихоб кунем.
Полиномияи мо шакл хоҳад дошт ки дар и — ададхои мусбати ба таври тасодуфй интихобшуда. Мо танҳо як полиномияро бо дараҷа сохта истодаем , ки дар он коэффисиенти озод — Ин сирри мост , ва барои ҳар яке аз минбаъда шартҳои аст, ки коэффисиенти мусбат тасодуфӣ интихоб нест. Агар ба мисоли аввала баргардем ва тахмин кунем , пас мо функсияро мегирем .
Дар ин лаҳза мо метавонем пораҳоро тавассути пайвастшавӣ тавлид кунем ададҳои беназир дар ки дар (зеро ин сирри мост). Дар ин мисол, мо мехоҳем чаҳор порчаро бо ҳадди се тақсим кунем, бинобар ин мо ба таври тасодуфӣ нуқтаҳоро тавлид мекунем ва ба чор нафари боваринок, нигахбони калид як хол фиристед. Мо инчунин ба мардум хабар медиҳем , зеро ин иттилооти ҷамъиятӣ ҳисобида мешавад ва барои барқарорсозӣ зарур аст .
Бозгашти сир
Мо аллакай дар бораи мафҳуми интерполясияи полиномӣ ва чӣ гуна он схемаи хадди Шамирро баррасӣ кардем. . Вакте ки се нафар аз чор шахсони боэътимод баркарор кардан мехоханд , онҳо танҳо бояд интерполясия кунанд бо нуктахои беназири худ. Барои ин онҳо метавонанд нуқтаҳои худро муайян кунанд ва бо формулаи зерин полиномияи интерполяционии Лагранжро ҳисоб кунед. Агар барномасозӣ барои шумо нисбат ба математика равшантар бошад, пас pi аслан оператор аст for, ки ҳамаи натиҷаҳоро афзун мекунад ва сигма аст for, ки ҳама чизро илова мекунад.
дар мо метавонем онро чунин ҳал кунем ва вазифаи полиномии аслии худро баргардонем:
Зеро мо инро медонем , барқароршавӣ оддӣ карда шудааст:
Истифодаи арифметикии бутуни хатарнок
Хол он ки мо идеяи асосии Шомирро бомуваффакият татбик кардаем , мо бо проблемадое мондаем, ки то ин дам ба он эътибор надодаем. Функсияи полиномии мо арифметикаи бутуни хатарнокро истифода мебарад. Аҳамият диҳед, ки барои ҳар як нуқтаи иловагӣ, ки ҳамлакунанда дар графики функсияи мо ба даст меорад, барои нуқтаҳои дигар имкониятҳои камтар вуҷуд доранд. Шумо инро бо чашми худ мебинед, вақте ки шумо шумораи афзояндаи нуқтаҳоро барои функсияи полиномӣ бо истифода аз арифметикаи бутунӣ тартиб медиҳед. Ин ба ҳадафи амниятии мо мухолиф аст, зеро ҳамлакунанда набояд ҳеҷ чизро бидонад, то ҳадди аққал он ки онҳо дошта бошанд пораҳо.
Барои нишон додани он ки схемаи арифметикии бутун то чӣ андоза заиф аст, сенарияеро баррасӣ кунед, ки дар он ҳамлакунанда ду хол ба даст овард. ва маълумоти умумиро медонад, ки . Аз ин маълумот вай хулоса бароварда метавонад , ба ду баробар аст ва арзишҳои маълумро ба формула ворид кунед и .
Он гоҳ ҳамлакунанда метавонад пайдо кунад , ҳисоб кардан :
Азбаски мо муайян кардем ҳамчун ададҳои мусбати ба таври тасодуфӣ интихобшуда, шумораи маҳдуди имконпазир вуҷуд дорад . Бо истифода аз ин маълумот, ҳамлакунанда метавонад хулоса барорад , зеро ҳама чизи бузургтар аз 5 кор мекунад манфӣ. Ин дуруст аст, зеро мо муайян кардем
Пас аз он ҳамлакунанда метавонад арзишҳои имконпазирро ҳисоб кунад иваз кардан в :
Бо имконоти маҳдуд барои маълум мешавад, ки интихоб ва тафтиши арзишҳо то чӣ андоза осон аст . Дар ин ҷо танҳо панҷ вариант вуҷуд дорад.
Ҳалли масъала бо арифметикаи бутуни хатарнок
Барои бартараф кардани ин осебпазирӣ, Шамир истифодаи арифметикаи модулиро пешниҳод мекунад, ки иваз карда шавад ба ки дар и — маҷмӯи ҳамаи рақамҳои ибтидоӣ.
Биёед зуд ба хотир орем, ки арифметикаи модулӣ чӣ гуна кор мекунад. Соат бо дастҳо як мафҳуми шинос аст. Вай соатеро истифода мебарад . Ҳамин ки ақрабаки соат аз дувоздаҳ гузашт, ба як бармегардад. Хусусияти ҷолиби ин система дар он аст, ки танҳо ба соат нигоҳ карда, мо наметавонем хулоса кунем, ки ақрабаки соат чӣ қадар гардиш кардааст. Аммо, агар донем, ки ақрабаки соат 12 чор маротиба гузашт, мо метавонем бо формулаи оддӣ шумораи соатҳои гузаштаро пурра муайян кунем. ки дар тақсимкунандаи мост (дар ин ҷо ), коэффисиент аст (чанд маротиба тақсимкунанда ба адади аслӣ бидуни боқимонда мегузарад, дар ин ҷо ), ва боқимонда аст, ки одатан занги оператори модулро бармегардонад (дар ин ҷо ). Донистани ҳамаи ин арзишҳо ба мо имкон медиҳад, ки муодиларо ҳал кунем , аммо агар коэффициентро аз даст дихем, мо харгиз арзиши аслиро баркарор карда наметавонем.
Мо метавонем нишон диҳем, ки чӣ тавр ин бехатарии нақшаи моро тавассути татбиқи схема ба мисоли пешинаи худ беҳтар мекунад ва бо истифода аз . Функсияи нави полиномии мо , ва нуктахои нав . Ҳоло нигаҳбонони калидӣ метавонанд бори дигар интерполясияи полиномиро барои барқарор кардани функсияи мо истифода баранд, танҳо ин дафъа амалиёти илова ва зарб бояд бо коҳиши модул ҳамроҳ карда шавад. (масалан, ).
Бо истифода аз ин мисоли нав, биёед фарз кунем, ки ҳамлагар ду нуктаи навро омӯхтааст, , ва иттилооти оммавӣ . Ин дафъа, ҳамлагар дар асоси тамоми маълумоти дар даст доштааш, вазифаҳои зеринро мебарорад, ки дар куҷо маҷмӯи ҳамаи ададҳои мусбат аст, ва коэффисиенти модулро ифода мекунад .
Ҳоло ҳамлагари мо боз пайдо мекунад , ҳисоб кардан :
Сипас ӯ боз кӯшиш мекунад иваз кардан в :
Ин дафъа ӯ мушкили ҷиддӣ дорад. Формула арзишҳои гумшуда , и . Азбаски шумораи беохири комбинатсияи ин тағирёбандаҳо вуҷуд доранд, вай наметавонад ягон маълумоти иловагӣ ба даст орад.
Мулоҳизаҳои амниятӣ
Нақшаи мубодилаи сирри Шамир пешниҳод мекунад амният аз нуқтаи назари назарияи иттилоот. Ин маънои онро дорад, ки математика ҳатто ба ҳамлагаре, ки қудрати ҳисоббарории номаҳдуд дорад, тобовар аст. Бо вуҷуди ин, схема то ҳол якчанд масъалаҳои маълумро дар бар мегирад.
Масалан, схемаи Шомир эиёд намекунад пораҳо бояд тафтиш карда шаванд, яъне одамон метавонанд озодона пораҳои қалбакӣ пешниҳод кунанд ва ба барқарорсозии сирри дуруст халал расонанд. Нигоҳдорандаи порчаи душманӣ бо маълумоти кофӣ метавонад ҳатто бо тағир додани порчаи дигарро тавлид кунад бо ихтиёри худ. Ин мушкилот бо истифода аз он ҳал карда мешавад схемаҳои мубодилаи махфии тафтишшаванда, ба монанди схемаи Фельдман.
Масъалаи дигар ин аст, ки дарозии ҳар як порча ба дарозии сирри мувофиқ баробар аст, бинобар ин дарозии сирро муайян кардан осон аст. Ин мушкилотро бо роҳи ночиз ҳал кардан мумкин аст пӯшиш махфӣ бо рақамҳои худсарона то дарозии собит.
Ниҳоят, қайд кардан муҳим аст, ки нигарониҳои амниятии мо метавонанд аз тарҳи худ берунтар бошанд. Барои барномаҳои криптографии ҷаҳони воқеӣ, аксар вақт таҳдиди ҳамлаҳои паҳлӯӣ вуҷуд дорад, ки дар он ҳамлакунанда кӯшиш мекунад, ки аз вақти иҷрои барнома, кэш, садамаҳо ва ғайра маълумоти муфидро ба даст орад. Агар ин боиси нигаронӣ бошад, ҳангоми таҳияи истифодаи чораҳои муҳофизатӣ, аз қабили функсияҳо ва ҷустуҷӯҳои доимӣ, пешгирӣ аз захира кардани хотира дар диск ва як қатор мулоҳизаҳои дигаре, ки аз доираи ин мақола берунанд, бояд бодиққат баррасӣ карда шавад.
Намоиш
Дар бораи он Намоиши интерактивии схемаи мубодилаи махфии Шамир мавҷуд аст. Намоиш аз руи китобхона , ки худ як порти JavaScript-и барномаи маъмул аст . Дар хотир доред, ки ҳисоб кардани арзишҳои калон , и метавонад чанд вақтро дар бар гирад.
Манбаъ: will.com