Нека разгледаме сценарий, при който трябва да осигурим сигурността на банково хранилище. То се счита за абсолютно недостъпно без ключа, който ви се дава в първия ден на работа. Вашата цел е надеждно да запазите ключа.

Да предположим, че решавате да държите ключа само при себе си, предоставяйки достъп до хранилището, когато е необходимо. Но бързо ще разберете, че подобно решение практично не е мащабируемо, тъй като за отваряне на хранилището е нужно физическото ви присъствие всеки път. А какво ще кажете за обещаните ви ваканции? Освен това, още по-плашещ е въпросът: а какво, ако загубите единствения ключ?

С мисъл за ваканцията, решавате да направите копие на ключа и да го доверите на друг служител. Въпреки това разбирате, че и това не е идеално. Удвоявайки броя на ключовете, вие също така удвоявате възможностите за кражба на ключа.

В отчаянието си, вие унищожавате дубликата и решавате да разделите оригиналния ключ на две. Сега, си казвате, двама доверени лица с фрагменти от ключа трябва физически да са присъствали, за да съберат ключа и да отворят хранилището. Това означава, че крадецът трябва да открадне два фрагмента, което е два пъти по-трудно от кражбата на един ключ. Но скоро разбирате, че тази схема не е много по-добра от просто един ключ, защото ако някой изгуби половината ключ, пълният ключ не може да бъде възстановен.

Проблемът може да бъде решен с помощта на серия от допълнителни ключове и заключалки, но с такъв подход бързо ще се нуждаете от много ключове и заключалки. Вие решавате, че в идеалната схема ключът трябва да бъде разделен, така че безопасността да не зависи изцяло от един човек. Вие също така заключавате, че трябва да съществува определен праг на броя на фрагментите, така че при загуба на един фрагмент (или ако човекът е на почивка) целият ключ да остане функционален.

Как да разделим секрет

За такъв тип схема за управление на ключове е мислил Ади Шамир през 1979 година, когато публикува своята работа «Как да разделим секрет». В статията кратко се обяснява така наречената прагова схема за ефективно разделяне на секретна стойност (например, криптографски ключ) на части. След това, когато и само когато поне от части са събрани, може лесно да се възстанови секретът. .

От гледна точка на сигурността, важно свойство на тази схема е, че нападателят не трябва да знае абсолютно нищо, ако няма поне части. Дори наличието на части не трябва да дава никаква информация. Ние наричаме това свойство семантична сигурност.

Полиномна интерполация

Схемата на Шамир е изградена около концепцията на полиномната интерполация. Ако не сте запознати с тази концепция, всъщност тя е доста проста. Всъщност, ако някога сте рисували точки на графика и след това сте свързвали тях с линии или криви, вече сте я използвали!

Чрез две точки могат да се проведат неограничен брой полиноми от степен 2. За да изберем единствения от тях, е необходима трета точка. Илюстрация: Уикипедия

Нека разгледаме полином от степен едно, . Ако искате да построите тази функция на графика, колко точки ви трябват? Ами, знаем, че това е линейна функция, която образува права линия и следователно е необходима поне две точки. След това разгледайте полиномиалната функция от степен две, . Това е квадратична функция, така че за изграждането на графика са необходими не по-малко от три точки. А какво ще кажете за полином от степен три? Поне четири точки. И така нататък.

Наистина впечатляващото в това свойство е, че, вземайки предвид степента на полиномната функция и поне точки, можем да извлечем допълнителни точки за тази полиномна функция. Екстраполацията на тези допълнителни точки наричаме полиномна интерполация.

Създаване на тайна

Може би сте разбрали, че тук влиза в игра умната схема на Шамир. Да предположим, че нашата тайна — това е . Можем да я превърнем в точка на графика и да създадем полиномиална функция от степен , която удовлетворява тази точка. Напомням, че ще бъде нашият праг на необходимите фрагменти, така че ако установим прага на три фрагмента, трябва да изберем полиномиална функция от степен две.

Нашият полином ще има формата , където и — случайно избрани положителни цели числа. Ние просто изграждаме полином от степен , където свободният коефициент  е нашата тайна , а всеки от следващите членов е случаен положителен коефициент. Ако се върнем към първоначалния пример и предположим, че , тогава ще получим функция .

На този етап можем да генерираме фрагменти, свързвайки уникални цели числа в , където (защото това е нашата тайна). В този пример искаме да раздадем четири фрагмента с прага три, така че случайно генерираме точки и изпращаме по една точка на всеки от четиримата доверени лица, съхранители на ключа. Също така уведомяваме хората, че , тъй като това се счита за публична информация и е необходимо за възстановяване .

Възстановяване на тайната

Вече обсъдихме концепцията за полиномна интерполация и това, че тя лежи в основата на схемата на Шамир . Когато каквито и да е три от четирима доверени лица искат да възстановят , им е нужно само да интерполират със своите уникални точки. За това те могат да определят своите точки и да изчислят интерполационния полином на Лагранж, използвайки следната формула. Ако програмирането ви е по-разбираемо от математиката, то пи е по същество оператор for, който умножава всички резултати, а сигма е for, която всичко събира.

При можем да решим това по следния начин и да върнем нашата първоначална полиномна функция:

Тъй като знаем, че , възстановяването се извършва просто:

Използване на небезопасна целочислена аритметика

Въпреки че успешно приложихме основната идея на Шамир , имаме проблем, който игнорирахме до момента. Нашата полиномна функция използва небезопасна целочислена аритметика. Имайте предвид, че за всяка допълнителна точка, която атакуващият получи на графиката на нашата функция, остава по-малко количество възможности за другите точки. Можете да видите това сами, когато изграждате график с увеличаване на броя на точките за полиномна функция с използване на целочислена аритметика. Това е контрапродуктивно за нашата заявена цел на сигурност, защото злонамереният не трябва да знае абсолютно нищо, докато не има поне фрагменти.

За да демонстрираме колко слаба е схемата с целочислена аритметика, разгледайте сценарий, в който злонамереният е получил две точки и знае публичната информация, че . От тази информация той може да извлече , равен на две, и да свърже известните стойности в уравнението и .

След това нападателят може да намери , като изчисли :

Понеже определихме като случайно избрани положителни цели числа, има ограничен брой възможни . С тази информация нападателят може да извлече , тъй като всичко, което е над 5, ще направи отрицателно. Това се оказва вярно, тъй като ние определихме

След това нападателят може да изчисли възможните стойности , като замени в :

С ограничен набор от опции за става ясно колко лесно е да подбереш и провериш стойностите . Има само пет варианта тук.

Решаването на проблема с нестабилната целочислена аритметика

За да се отстрани тази уязвимост, Шамир предлага да се използва модулна аритметика, заменяйки на , където и — множеството на всичките прости числа.

Бързо да си припомним как работи модулната аритметика. Часовниците са вече позната концепция. Те използват часовници, които са . Когато стрелката на часа премине през дванадесет, тя се връща на едно. Интересна особеност на тази система е, че просто поглеждайки часовника, не можем да извлечем колко оборота е направила стрелката на часа. Въпреки това, ако знаем, че стрелката на часа е преминала четири пъти през 12, можем напълно да определим колко часа са минали с проста формула , където  — това е нашето деление (тук ),  — това е коефициентът (колко пъти делителят без остатък влиза в оригиналното число, тук ), а  — това е остатъкът, който обикновено връща операторът по модул (тук ). Познаването на всички тези стойности ни позволява да решим уравнението за , но ако пропуснем коефициента, никога няма да можем да възстановим оригиналната стойност.

Може да се демонстрира как това подобрява безопасността на нашата схема, прилагайки схемата към нашия предишен пример и използвайки . Нашата нова полиномиална функция , а новите точки . Сега ключоводителите могат отново да използват полиномиална интерполация, за да възстановят нашата функция, само че този път операциите на събиране и умножение трябва да бъдат придружени от модулно съкращаване (напр. ).

Използвайки този нов пример, да предположим, че нападателят е узнал две от тези нови точки, , а публичната информация . Този път атакуващият, на базата на всяка налична информация, извежда следните функции, където  — набор от всички положителни цели числа, а представлява коефициента на модула .

Сега нашият нападател отново открива , изчислявайки :

След това отново се опитва да извлече , като замени в :

Този път той има сериозен проблем. Във формулата липсват стойности , и . Понеже съществуват безкрайно много комбинации от тези променливи, той не може да получи никаква допълнителна информация.

Съображения за сигурност

Схемата за разделяне на тайната на Шамир предлага сигурност в контекста на теорията на информацията. Това означава, че математиката е устойчива дори срещу нападател с неограничена изчислителна мощност. Въпреки това, схемата все пак съдържа няколко известни проблема.

Например, схемата на Шамир не създава проверяеми фрагменти, тоест хората могат свободно да представят фалшиви фрагменти и да затруднят възстановяването на правилната тайна. Враждебен пазач на фрагменти с достатъчно информация дори може да произведе друг фрагмент, променяйки по свое усмотрение. Този проблем се решава чрез проверяеми схеми за разделяне на тайни, като схемата на Фелдман.

Друг проблем е, че дължината на всеки фрагмент е равна на дължината на съответната тайна, така че дължината на тайната е лесна за определяне. Този проблем се решава с тривиална попълване на тайната с произволни числа до фиксирана дължина.

Накрая, важно е да се отбележи, че нашите опасения относно сигурността могат да излязат извън самата схема. За реални криптографски приложения често съществува заплаха от атаки по странични канали, когато нападателят се опитва да извлече полезна информация от времето на изпълнение на приложението, кеширане, сривове и т.н. Ако това предизвиква безпокойство, по време на разработката трябва внимателно да се разгледат защитни мерки, като функции и търсене с постоянно време за изпълнение, да се предотврати запазването на паметта на диск и да се обмислят редица други неща, които излизат извън рамките на тази статия.

Демо

На на тази страница има интерактивна демонстрация на схемата за разделяне на тайната на Шамир. Демонстрацията е направена на база библиотеката ssss-js, която самата е JavaScript порт на популярната програма ssss. Обърнете внимание, че изчисляването на големи стойности , и може да отнеме известно време.

Източник: habr.com