Размислете за сценарио каде што треба да обезбедите банкарски трезор. Се смета за апсолутно непробојна без клуч, кој ви се дава на првиот работен ден. Вашата цел е безбедно да го складирате клучот.
Да речеме дека одлучивте да го чувате клучот со себе секогаш, обезбедувајќи пристап до складиштето по потреба. Но, брзо ќе сфатите дека ваквото решение не се размерува добро во пракса, бидејќи вашето физичко присуство е потребно секогаш кога ќе го отворите складиштето. Што е со одморот што ви го ветија? Освен тоа, прашањето е уште пострашно: што ако го изгубите единствениот клуч?
Имајќи го предвид вашиот одмор, одлучувате да направите копија од клучот и да му го доверите на друг вработен. Сепак, разбирате дека ниту ова не е идеално. Со двојно зголемување на бројот на клучеви, ги удвојувате и шансите за кражба на клучеви.
Во очај, го уништувате дупликатот и одлучувате да го поделите оригиналниот клуч на половина. Сега, би помислиле дека две доверливи луѓе со клучни фрагменти треба да бидат физички присутни за да го соберат клучот и да го отворат трезорот. Тоа значи дека крадецот треба да украде две парчиња, што е двојно потешко отколку да украде еден клуч. Сепак, наскоро сфаќате дека оваа шема не е многу подобра од само еден клуч, бидејќи ако некој изгуби половина клуч, целиот клуч не може да се врати.
Проблемот може да се реши со серија дополнителни клучеви и брави, но овој пристап брзо ќе бара много клучеви и брави. Вие одлучувате дека идеалниот дизајн би бил да го споделите клучот за безбедноста да не се потпира целосно на една личност. Исто така, заклучувате дека мора да има одреден праг за бројот на фрагменти, така што ако еден фрагмент се изгуби (или ако некое лице оди на одмор), целиот клуч да остане функционален.
Како да споделите тајна
За овој тип на шема за управување со клучеви Ади Шамир размислувал во 1979 година кога ја објавил својата работа . Во написот накратко се објаснува т.н 
праг шема за ефикасно делење тајна вредност (како што е криптографски клуч) на Делови. Тогаш, кога и само кога барем на делови се собрани, лесно можете да ја вратите тајната .
Од безбедносна гледна точка, важна особина на оваа шема е дека напаѓачот не треба да знае апсолутно ништо, освен ако има барем Делови. Дури и присуството деловите не треба да даваат никакви информации. Ние го нарекуваме овој имот семантичка сигурност.
Полиномна интерполација
Шема на праг на Шамир изградена околу концептот полиномна интерполација. Ако не сте запознаени со овој концепт, всушност е прилично едноставен. Всушност, ако некогаш сте нацртале точки на графикон, а потоа сте ги поврзале со линии или криви, веќе сте го користеле!
Преку две точки можете да нацртате неограничен број полиноми од степен 2. За да го изберете единствениот од нив, потребна ви е трета точка. Илустрација:
Размислете за полином со степен еден, . Ако сакате да ја нацртате оваа функција на графикон, колку точки ви се потребни? Па, знаеме дека ова е линеарна функција што формира права и затоа и требаат најмалку две точки. Следно, разгледајте полиномна функција со степен два, . Ова е квадратна функција, така што се потребни најмалку три точки за да се нацрта графикот. Што е со полином со три степен? Најмалку четири поени. И така натаму и така натаму.
Навистина кул работа за ова својство е тоа што, со оглед на степенот на полиномната функција и барем поени, можеме да изведеме дополнителни точки за оваа полиномна функција. Ние го нарекуваме екстраполација на овие дополнителни точки полиномна интерполација.
Измислување тајна
Можеби веќе сте сфатиле дека тука стапува во игра паметната шема на Шамир. Да ја кажеме нашата тајна - Дали . Можеме да се свртиме до точка на графикот и да излезе со полиномна функција со степен , што ја задоволува оваа точка. Да се потсетиме на тоа ќе биде нашиот праг на потребните фрагменти, па ако го поставиме прагот на три фрагменти, мора да избереме полиномна функција со степен два.
Нашиот полином ќе ја има формата каде и — случајно избрани позитивни цели броеви. Ние само конструираме полином со степен , каде што слободен коефициент - Ова е нашата тајна , и за секоја од следните термини постои случајно избран позитивен коефициент. Ако се вратиме на првобитниот пример и претпоставиме дека , тогаш ја добиваме функцијата .
Во овој момент можеме да генерираме фрагменти со поврзување единствени цели броеви во каде (бидејќи тоа е нашата тајна). Во овој пример, сакаме да дистрибуираме четири фрагменти со праг од три, па случајно генерираме поени и испратете по еден поен на четирите доверливи луѓе, чувари на клучот. Ние, исто така, им даваме до знаење на луѓето , бидејќи ова се смета за јавна информација и е неопходно за обновување .
Враќање на тајната
Веќе разговаравме за концептот на полиномна интерполација и како таа лежи во основата на шемата на праг на Шамир . Кога било кои тројца од четирите доверители сакаат да обноват , треба само да се интерполираат со свои уникатни точки. За да го направат ова, тие можат да ги одредат своите поени и пресметај го Лагранжовиот полином на интерполација користејќи ја следната формула. Ако програмирањето ви е појасно од математиката, тогаш пи е во суштина оператор for, што ги множи сите резултати, а сигма е for, што собира сè.
на можеме да го решиме вака и да ја вратиме нашата оригинална полиномна функција:
Затоа што го знаеме тоа , закрепнување направено едноставно:
Користење на небезбедна аритметика со цели броеви
Иако успешно ја применивме основната идеја на Шамир , ни остана проблем кој до сега сме го игнорирале. Нашата полиномна функција користи небезбедна аритметика со цели броеви. Забележете дека за секоја дополнителна точка што напаѓачот ја добива на графикот на нашата функција, има помалку можности за други точки. Можете да го видите ова со свои очи кога ќе нацртате зголемен број точки за полиномна функција користејќи аритметика со цели броеви. Ова е контрапродуктивно на нашата наведена безбедносна цел, бидејќи напаѓачот не треба да знае апсолутно ништо додека не знае барем фрагменти.
За да покажете колку е слабо аритметичкото коло со цели броеви, разгледајте сценарио во кое напаѓачот добил два поени и знае информации од јавен карактер дека . Од оваа информација тој може да заклучи , еднакво на два и вклучете ги познатите вредности во формулата и .
Напаѓачот потоа може да најде , броејќи :
Бидејќи ние дефиниравме како случајно избрани позитивни цели броеви, има ограничен број можни . Користејќи ги овие информации, напаѓачот може да заклучи , бидејќи сè поголемо од 5 ќе направи негативен. Излегува дека ова е точно бидејќи ние утврдивме
Напаѓачот потоа може да ги пресмета можните вредности , заменувајќи в :
Со ограничени опции за станува јасно колку е лесно да се изберат и проверат вредностите . Овде има само пет опции.
Решавање на проблемот со небезбедна аритметика со цели броеви
За да се елиминира оваа ранливост, Шамир предлага користење на модуларна аритметика, замена на каде и — множество од сите прости броеви.
Ајде брзо да се потсетиме како функционира модуларната аритметика. Часовникот со стрелки е познат концепт. Таа користи часовник што е . Штом часовникот ќе помине дванаесет, се враќа на еден. Интересно својство на овој систем е тоа што едноставно со гледање на часовникот не можеме да заклучиме колку вртежи направила часовникот. Меѓутоа, ако знаеме дека часовникот поминал 12 четири пати, можеме целосно да го одредиме бројот на поминати часови користејќи едноставна формула каде е нашиот делител (тука ), е коефициентот (колку пати делителот влегува во оригиналниот број без остаток, овде ), и е остатокот, кој обично враќа повик на модуло оператор (тука ). Познавањето на сите овие вредности ни овозможува да ја решиме равенката за , но ако го пропуштиме коефициентот, никогаш нема да можеме да ја вратиме првобитната вредност.
Можеме да покажеме како ова ја подобрува безбедноста на нашата шема со примена на шемата на нашиот претходен пример и користење . Нашата нова полиномна функција , и новите точки . Сега чуварите на клучеви можат повторно да користат полиномна интерполација за да ја реконструираат нашата функција, само што овој пат операциите за собирање и множење мора да бидат придружени со намалување на модулите (пр ).
Користејќи го овој нов пример, да претпоставиме дека напаѓачот научил две од овие нови точки, , и информации од јавен карактер . Овој пат, напаѓачот, врз основа на сите информации што ги има, ги издава следните функции, каде е множество од сите позитивни цели броеви, и го претставува коефициентот на модул .
Сега нашиот напаѓач повторно наоѓа , пресметување :
Потоа повторно се обидува , заменувајќи в :
Овој пат има сериозен проблем. Недостасуваат вредности на формулата , и . Бидејќи има бесконечен број комбинации на овие променливи, тој не може да добие дополнителни информации.
Безбедносни размислувања
Тајната шема за споделување на Шамир сугерира безбедност од гледна точка на теоријата на информации. Ова значи дека математиката е отпорна дури и против напаѓач со неограничена компјутерска моќ. Сепак, колото сè уште содржи неколку познати проблеми.
На пример, шемата на Шамир не создава фрагменти кои треба да се проверат, односно, луѓето можат слободно да презентираат лажни фрагменти и да се мешаат во враќањето на точната тајна. Непријателски чувар на фрагменти со доволно информации може дури и да произведе друг фрагмент со менување по сопствена дискреција. Овој проблем е решен со користење проверливи шеми за споделување тајни, како што е шемата на Фелдман.
Друг проблем е тоа што должината на кој било фрагмент е еднаква на должината на соодветната тајна, така што должината на тајната е лесно да се одреди. Овој проблем може да се реши со тривијално баласт тајна со произволни броеви до фиксна должина.
Конечно, важно е да се забележи дека нашите безбедносни грижи може да се прошират надвор од самиот дизајн. За криптографските апликации од реалниот свет, често постои закана од напади на страничните канали каде што напаѓачот се обидува да извлече корисни информации од времето на извршување на апликацијата, кеширањето, паѓањата итн. Ако ова е загриженост, при развојот треба внимателно да се разгледа користењето заштитни мерки како што се функциите и пребарувањето со постојано време, спречувањето меморија да се зачува на дискот и голем број други размислувања кои се надвор од опсегот на овој член.
Демо
На Постои интерактивна демонстрација на шемата за тајно споделување на Шамир. Демонстрација врз основа на библиотеката , која сама по себе е JavaScript порта на популарната програма . Забележете дека пресметувањето на големи вредности , и може да потрае некое време.
Извор: www.habr.com