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

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

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

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

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

Как да споделим тайна

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогава нападателят може да намери , броене :

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

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

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

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

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

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

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

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

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

След това отново се опитва да се оттегли подмяна в :

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

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

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

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

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

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

демонстрация

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

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