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

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

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

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

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

Как да разделим тайна

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

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

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

Схемата на Шамир с прагове е изградена около концепцията за полиномиална интерполация. Ако не сте запознати с тази концепция, наистина е доста проста. Всъщност, ако някога сте чертали точки на графика и след това сте свързвали тези точки с линии или криви, то вече сте я използвали!Чрез две точки могат да се начертаят неограничен брой полиноми от степен 2. За да изберем единствен, е нужна трета точка. Илюстрация:

Нека разгледаме полином от степен 1, Уикипедия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Демо

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

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