Банк қоймасын қамтамасыз ету қажет сценарийді қарастырыңыз. Бұл сізге жұмыстың бірінші күнінде берілетін кілтсіз мүлдем алынбайды деп саналады. Сіздің мақсатыңыз кілтті қауіпсіз сақтау.
Қажет болса, жадқа қолжетімділікті қамтамасыз ете отырып, кілтті әрқашан өзіңізбен бірге ұстауды шештіңіз делік. Бірақ сіз мұндай шешімнің іс жүзінде жақсы масштабталмағанын тез түсінесіз, өйткені қойманы ашқан сайын сіздің физикалық қатысуыңыз қажет. Сізге уәде етілген демалыс ше? Сонымен қатар, сұрақ одан да қорқынышты: егер сіз жалғыз кілтіңізді жоғалтып алсаңыз ше?
Сіздің демалысыңызды ескере отырып, сіз кілттің көшірмесін жасап, оны басқа қызметкерге тапсыруды шешесіз. Дегенмен, бұл да идеал емес екенін түсінесіз. Кілттердің санын екі есе көбейту арқылы сіз кілттерді ұрлау мүмкіндігін де екі есе арттырасыз.
Амалсыздан сіз көшірмелерді жойып, бастапқы кілтті екіге бөлуді шешесіз. Енді кілтті жинап, қойманы ашу үшін кілт фрагменттері бар екі сенімді адам физикалық түрде қатысуы керек деп ойлайсыз. Бұл ұрыға екі бөлікті ұрлау керек дегенді білдіреді, бұл бір кілтті ұрлаудан екі есе қиын. Дегенмен, көп ұзамай сіз бұл схеманың бір кілтке қарағанда әлдеқайда жақсы емес екенін түсінесіз, себебі біреу жарты кілтті жоғалтып алса, толық кілтті қалпына келтіру мүмкін емес.
Мәселені қосымша кілттер мен құлыптар сериясымен шешуге болады, бірақ бұл тәсіл тез қажет болады много кілттер мен құлыптар. Қауіпсіздік бір адамға ғана сенбеуі үшін кілтті ортақ пайдалану идеалды дизайн болады деп шешесіз. Сондай-ақ, егер бір фрагмент жоғалса (немесе адам демалысқа шықса) барлық кілт жұмыс істеп тұруы үшін фрагменттердің саны үшін белгілі бір шек болуы керек деген қорытындыға келдіңіз.
Құпиямен қалай бөлісуге болады
Негізгі басқару схемасының бұл түрі туралы Ади Шамир 1979 жылы өз жұмысын жариялаған кезде ойлаған . Мақалада қысқаша деп аталатындар түсіндіріледі 
құпия мәнді (мысалы, криптографиялық кілт) тиімді бөлуге арналған шекті схема бөліктері. Содан кейін, кем дегенде қашан және қашан -дан бөлшектер жиналған, сіз құпияны оңай қалпына келтіре аласыз .
Қауіпсіздік тұрғысынан, бұл схеманың маңызды қасиеті - шабуылдаушы, егер кем дегенде, егер ол болмаса, мүлдем ештеңе білмеуі керек. бөліктері. Тіпті болуы бөліктері ешқандай ақпарат бермеуі керек. Біз бұл қасиет деп атаймыз семантикалық қауіпсіздік.
Полиномдық интерполяция
Шамир шекті схемасы тұжырымдамасы төңірегінде құрылған полиномдық интерполяция. Егер сіз бұл тұжырымдамамен таныс болмасаңыз, бұл өте қарапайым. Шындығында, егер сіз графиктегі нүктелерді салып, содан кейін оларды сызықтармен немесе қисықтармен байланыстырсаңыз, сіз оны бұрыннан қолдандыңыз!
Екі нүкте арқылы 2-дәрежелі көпмүшелердің шексіз санын салуға болады. Олардың ішінен жалғызын таңдау үшін үшінші нүкте қажет. Иллюстрация:
Бірінші дәрежелі көпмүшені қарастырайық, . Бұл функцияны графикке салғыңыз келсе, сізге қанша нүкте қажет? Біз бұл сызықты құрайтын сызықтық функция екенін білеміз, сондықтан оған кемінде екі нүкте қажет. Әрі қарай, екінші дәрежелі көпмүшелік функцияны қарастырыңыз, . Бұл квадраттық функция, сондықтан графикті салу үшін кемінде үш нүкте қажет. Үшінші дәрежелі көпмүше туралы не деуге болады? Кем дегенде төрт ұпай. Және тағы басқалар.
Бұл қасиет туралы шынымен керемет нәрсе, полиномдық функцияның дәрежесін ескере отырып және кем дегенде нүктелер болса, біз осы көпмүшелік функция үшін қосымша нүктелерді шығара аламыз. Бұл қосымша нүктелерді экстраполяция деп атаймыз полиномдық интерполяция.
Құпия ойлап табу
Шамирдің ақылды схемасы осы жерде іске асатынын түсінген боларсыз. Сырымызды айтайық Мүмкін . Біз бұра аламыз графиктегі нүктеге және дәрежесі бар көпмүшелік функцияны шығарыңыз , бұл осы тармақты қанағаттандырады. Естеріңізге сала кетейік біздің қажетті фрагменттердің табалдырығы болады, сондықтан шекті үш фрагментке орнатсақ, екінші дәрежелі көпмүшелік функцияны таңдауымыз керек.
Біздің көпмүшенің пішіні болады қайда и — кездейсоқ таңдалған оң бүтін сандар. Біз жай ғана дәрежесі бар көпмүшені құрастырамыз , мұндағы бос коэффициент - Бұл біздің құпиямыз , және одан кейінгілердің әрқайсысы үшін кездейсоқ таңдалған оң коэффициент бар. Егер біз бастапқы мысалға оралсақ және оны болжасақ , содан кейін функцияны аламыз .
Осы кезде біз қосылу арқылы фрагменттерді жасай аламыз ішіндегі бірегей бүтін сандар қайда (себебі бұл біздің құпиямыз). Бұл мысалда біз үш табалдырықпен төрт фрагментті таратқымыз келеді, сондықтан біз кездейсоқ нүктелерді жасаймыз және кілтті сақтаушы төрт сенімді адамға бір ұпайдан жіберіңіз. Оны да халыққа хабарлаймыз , өйткені бұл жалпыға ортақ ақпарат болып саналады және қалпына келтіру үшін қажет .
Құпияны қалпына келтіру
Біз көпмүшелік интерполяция түсінігін және оның Шамирдің шекті схемасының негізінде жатқанын жоғарыда талқыладық. . Төрт сенімді тұлғаның үшеуі қалпына келтіргісі келгенде , олар тек интерполяциялау керек өзіндік ерекше нүктелері бар. Ол үшін олар өз ұпайларын анықтай алады және келесі формула арқылы Лагранж интерполяциясының көпмүшелігін есептеңіз. Егер бағдарламалау сізге математикаға қарағанда түсінікті болса, онда pi мәні оператор болып табылады for, ол барлық нәтижелерді көбейтеді, ал сигма for, ол бәрін қосады.
жанында біз оны осылай шеше аламыз және бастапқы полиномдық функциямызды қайтара аламыз:
Өйткені біз мұны білеміз , қалпына келтіру қарапайым орындалды:
Қауіпті бүтін арифметиканы пайдалану
Біз Шәмірдің негізгі идеясын сәтті қолдандық , осы уақытқа дейін назардан тыс қалдырған мәселе қалды. Біздің көпмүшелік функциямыз қауіпті бүтін арифметиканы пайдаланады. Біздің функцияның графигінде шабуылдаушы алатын әрбір қосымша нүкте үшін басқа нүктелер үшін аз мүмкіндіктер бар екенін ескеріңіз. Бүтін арифметика арқылы көпмүшелік функция үшін нүктелердің көбеюін сызған кезде мұны өз көзіңізбен көруге болады. Бұл біздің мәлімдеген қауіпсіздік мақсатымызға кері әсер етеді, өйткені шабуылдаушы ең болмағанда қолында ештеңе білмеуі керек фрагменттері.
Бүтін арифметикалық схеманың қаншалықты әлсіз екенін көрсету үшін шабуылдаушы екі ұпай алған сценарийді қарастырыңыз. және бұл туралы қоғамдық ақпаратты біледі . Осы мәліметтерден ол қорытынды шығара алады , екіге тең және белгілі мәндерді формулаға қосыңыз и .
Содан кейін шабуылдаушы таба алады , санау :
Біз анықтағандықтан кездейсоқ таңдалған оң бүтін сандар ретінде мүмкін болатын саны шектеулі . Осы ақпаратты пайдалана отырып, шабуылдаушы қорытынды жасай алады , өйткені 5-тен жоғары кез келген нәрсе жасайды теріс. Біз анықтағандықтан, бұл рас болып шықты
Содан кейін шабуылдаушы ықтимал мәндерді есептей алады ауыстыру в :
Шектеулі опциялармен мәндерді таңдау және тексеру қаншалықты оңай екені белгілі болады . Мұнда тек бес нұсқа бар.
Қауіпті бүтін арифметикамен есепті шешу
Бұл осалдықты жою үшін Шамир модульдік арифметиканы ауыстыруды ұсынады туралы қайда и — барлық жай сандар жиыны.
Модульдік арифметика қалай жұмыс істейтінін тез еске түсірейік. Қолдары бар сағат - бұл таныс ұғым. Ол сағатты пайдаланады . Сағат тілі он екіден өткен соң бірден бірге қайтады. Бұл жүйенің қызықты қасиеті - сағатқа қарап, сағат тілі қанша айналым жасағанын анықтай алмаймыз. Алайда, егер сағат тілі 12 төрт рет өткенін білсек, қарапайым формула арқылы өткен сағат санын толық анықтауға болады. қайда біздің бөлгішіміз (мұнда ), коэффициент болып табылады (бөлінгіш бастапқы санға қалдықсыз қанша рет түседі, мұнда ), және әдетте модуль операторының шақыруын қайтаратын қалдық (мұнда ). Барлық осы мәндерді білу бізге теңдеуді шешуге мүмкіндік береді , бірақ егер біз коэффициентті жіберіп алсақ, біз ешқашан бастапқы мәнді қалпына келтіре алмаймыз.
Алдыңғы мысалға схеманы қолдану және пайдалану арқылы бұл схемамыздың қауіпсіздігін қалай жақсартатынын көрсете аламыз. . Біздің жаңа көпмүшелік функциямыз , және жаңа нүктелер . Енді негізгі сақтаушылар функциямызды қайта құру үшін полиномдық интерполяцияны тағы бір рет пайдалана алады, тек осы жолы қосу және көбейту амалдары модульді азайтумен бірге жүруі керек. (мысалы ).
Осы жаңа мысалды пайдалана отырып, шабуылдаушы осы екі жаңа тармақты білді делік, , және қоғамдық ақпарат . Бұл жолы шабуылдаушы өзінің барлық ақпаратына сүйене отырып, келесі функцияларды шығарады, мұнда барлық натурал сандар жиыны және модуль коэффициентін көрсетеді .
Енді біздің шабуылдаушы қайтадан табады , есептеу :
Содан кейін ол қайтадан тырысады ауыстыру в :
Бұл жолы оның ауыр проблемасы бар. Формула жоқ мәндер , и . Бұл айнымалылардың комбинацияларының шексіз саны болғандықтан, ол ешқандай қосымша ақпаратты ала алмайды.
Қауіпсіздікті қарастыру
Шамирдің құпия бөлісу схемасы ұсынады ақпарат теориясы тұрғысынан қауіпсіздік. Бұл математиканың тіпті шектеусіз есептеу қабілеті бар шабуылдаушыға да төзімді екенін білдіреді. Дегенмен, схема әлі де бірнеше белгілі мәселелерді қамтиды.
Мысалы, Шамирдің схемасы жасамайды тексерілетін үзінділер, яғни адамдар жалған фрагменттерді еркін ұсынып, дұрыс құпияны қалпына келтіруге кедергі жасай алады. Жеткілікті ақпараты бар дұшпандық фрагментті сақтаушы тіпті өзгерту арқылы басқа фрагментті де жасай алады өз қалауыңыз бойынша. Бұл мәселе көмегімен шешіледі тексерілетін құпия бөлісу схемалары, мысалы, Фельдман схемасы.
Тағы бір мәселе, кез келген фрагменттің ұзындығы сәйкес құпияның ұзындығына тең, сондықтан құпияның ұзындығын анықтау оңай. Бұл мәселені тривиальды жолмен шешуге болады төсеу белгіленген ұзындыққа дейін ерікті сандармен құпия.
Соңында, біздің қауіпсіздік мәселелері дизайнның өзінен тыс болуы мүмкін екенін ескеру маңызды. Шынайы криптографиялық қолданбалар үшін шабуылдаушы қолданбаның орындалу уақытынан, кэштеуден, бұзылулардан және т.б. пайдалы ақпаратты алуға тырысатын бүйірлік арналық шабуылдар қаупі жиі кездеседі. Егер бұл алаңдаушылық тудырса, әзірлеу кезінде функциялар мен тұрақты уақыттағы іздеулер, жадтың дискіге сақталуына жол бермеу және осы мақаланың ауқымынан тыс басқа да бірқатар мәселелер сияқты қорғаныс шараларын қолдануды мұқият қарастырған жөн.
Демо
туралы Шамирдің құпия бөлісу схемасының интерактивті көрсетілімі бар. Кітапханаға негізделген демонстрация , ол өзі танымал бағдарламаның JavaScript порты болып табылады . Үлкен мәндерді есептеуді ескеріңіз , и біраз уақыт алуы мүмкін.
Ақпарат көзі: www.habr.com