Размислите о сценарију где морате да обезбедите банковни трезор. Сматра се апсолутно неосвојивим без кључа, који добијате већ првог дана рада. Ваш циљ је да безбедно чувате кључ.
Рецимо да одлучите да кључ увек држите са собом, пружајући приступ складишту по потреби. Али брзо ћете схватити да такво решење није добро у пракси, јер је ваше физичко присуство потребно сваки пут када отворите складиште. Шта је са одмором који вам је обећан? Осим тога, питање је још страшније: шта ако сте изгубили једини кључ?
Имајући на уму одмор, одлучујете да направите копију кључа и поверите је другом запосленом. Међутим, разумете да ни ово није идеално. Удвостручавањем броја кључева удвостручујете се и шансе за крађу кључева.
У очају, уништите дупликат и одлучите да поделите оригинални кључ на пола. Сада бисте помислили да би две особе од поверења са фрагментима кључа морале да буду физички присутне да узму кључ и отворе трезор. То значи да лопов треба да украде два комада, што је дупло теже од крађе једног кључа. Међутим, убрзо схватате да ова шема није много боља од само једног кључа, јер ако неко изгуби пола кључа, цео кључ се не може повратити.
Проблем се може решити низом додатних кључева и брава, али ће овај приступ брзо захтевати много кључеве и браве. Ви одлучујете да би идеалан дизајн био да делите кључ тако да се безбедност не ослања у потпуности на једну особу. Такође закључујете да мора постојати неки праг за број фрагмената тако да ако се један фрагмент изгуби (или ако особа оде на одмор), цео кључ остане функционалан.
Како поделити тајну
О овој врсти шеме управљања кључем размишљао је Ади Шамир 1979. када је објавио свој рад . У чланку се укратко објашњава тзв 
шема прага за ефикасну поделу тајне вредности (као што је криптографски кључ). делови. Тада, када и само када барем од делови су састављени, лако можете вратити тајну .
Са безбедносне тачке гледишта, важно својство ове шеме је да нападач не би требало да зна апсолутно ништа осим ако нема барем делови. Чак и присуство делови не би требало да дају никакве информације. Ово својство зовемо семантичка сигурност.
Полиномска интерполација
Шамирова шема прага изграђен око концепта полиномска интерполација. Ако нисте упознати са овим концептом, он је заправо прилично једноставан. У ствари, ако сте икада цртали тачке на графикону, а затим их повезивали линијама или кривима, већ сте то користили!
Кроз две тачке можете повући неограничен број полинома степена 2. Да бисте од њих изабрали једини, потребна вам је трећа тачка. Илустрација:
Размотримо полином са степеном један, . Ако желите да исцртате ову функцију на графикону, колико поена вам треба? Па, знамо да је ово линеарна функција која формира праву и да су јој потребне најмање две тачке. Затим, размотрите полиномску функцију са степеном два, . Ово је квадратна функција, тако да су потребне најмање три тачке за цртање графика. Шта кажете на полином са степеном три? Најмање четири бода. И тако даље и тако даље.
Заиста цоол ствар у вези са овим својством је да, с обзиром на степен полиномске функције и најмање тачке, можемо извести додатне тачке за ову полиномску функцију. Ове додатне тачке називамо екстраполацијом полиномска интерполација.
Прављење тајне
Можда сте већ схватили да ту долази до изражаја Шамирова паметна шема. Рецимо нашу тајну - Је . Можемо да се окренемо до тачке на графикону и смислити полиномску функцију са степеном , што задовољава ову тачку. Да вас подсетимо биће наш праг потребних фрагмената, тако да ако поставимо праг на три фрагмента, морамо изабрати полиномску функцију са степеном два.
Наш полином ће имати облик Где и — насумично одабрани позитивни цели бројеви. Управо конструишемо полином са степеном , где је слободни коефицијент - Ово је наша тајна , и за сваку од наредних термини постоји насумично одабран позитиван коефицијент. Ако се вратимо на првобитни пример и претпоставимо да , онда добијамо функцију .
У овом тренутку можемо генерисати фрагменте повезивањем јединствени цели бројеви у Где (јер је то наша тајна). У овом примеру желимо да дистрибуирамо четири фрагмента са прагом од три, тако да насумично генеришемо тачке и пошаљи по један поен сваком од четири поуздана лица, чуварима кључа. То такође стављамо до знања људима , пошто се то сматра јавном информацијом и неопходно је за опоравак .
Повратак тајне
Већ смо разговарали о концепту полиномске интерполације и како она лежи у основи Шамирове шеме прага . Када било која три од четири повереника желе да обнове , само треба да интерполирају са својим јединственим тачкама. Да би то урадили, они могу одредити своје тачке и израчунај Лагранжов интерполациони полином користећи следећу формулу. Ако вам је програмирање јасније од математике, онда је пи у суштини оператор for, што множи све резултате, а сигма је for, што све сабира.
У можемо то решити овако и вратити нашу оригиналну полиномску функцију:
Пошто то знамо , опоравак урађено једноставно:
Коришћење небезбедне целобројне аритметике
Иако смо основну Шамирову идеју успешно применили , остаје нам проблем који смо до сада игнорисали. Наша полиномска функција користи небезбедну целобројну аритметику. Имајте на уму да за сваку додатну тачку коју нападач добије на графу наше функције, постоји мање могућности за друге тачке. Ово можете видети сопственим очима када исцртате све већи број тачака за полиномску функцију користећи целобројну аритметику. Ово је контрапродуктивно за наш наведени безбедносни циљ, јер нападач не би требало да зна апсолутно ништа док не зна fragmenti.
Да бисте показали колико је слабо целобројно аритметичко коло, размотрите сценарио у којем је нападач добио два поена и зна јавне информације да . Из ових података може закључити , једнако два, и убаците познате вредности у формулу и .
Нападач тада може пронаћи , рачунајући :
Пошто смо дефинисали као насумично одабрани позитивни цели бројеви, постоји ограничен број могућих . Користећи ове информације, нападач може закључити , пошто ће све што је веће од 5 послужити негативан. Испоставило се да је то тачно пошто смо утврдили
Нападач тада може израчунати могуће вредности , замена в :
Са ограниченим опцијама за постаје јасно колико је лако изабрати и проверити вредности . Овде постоји само пет опција.
Решавање проблема са небезбедном целобројном аритметиком
Да би елиминисао ову рањивост, Шамир предлаже коришћење модуларне аритметике, замене на Где и — скуп свих простих бројева.
Хајде да се брзо подсетимо како функционише модуларна аритметика. Сат са казаљкама је познат концепт. Она користи сат који је . Чим казаљка сата прође дванаест, враћа се на један. Занимљиво својство овог система је да једноставним гледањем на сат не можемо закључити колико је обртаја казаљка сата направила. Међутим, ако знамо да је казаљка сата прешла 12 четири пута, можемо у потпуности одредити број сати који су прошли користећи једноставну формулу Где је наш делилац (овде ), је коефицијент (колико пута делилац иде у првобитни број без остатка, овде ), и је остатак, који обично враћа модуло позив оператора (овде ). Познавање свих ових вредности омогућава нам да решимо једначину за , али ако пропустимо коефицијент, никада нећемо моћи да вратимо првобитну вредност.
Можемо показати како ово побољшава безбедност наше шеме применом шеме на претходни пример и коришћењем . Наша нова полиномска функција , и нове тачке . Сада чувари кључева поново могу да користе полиномску интерполацију да реконструишу нашу функцију, само што овај пут операције сабирања и множења морају бити праћене модуло редукцијом (на пример ).
Користећи овај нови пример, претпоставимо да је нападач научио две од ових нових поена, , и јавно информисање . Овог пута, нападач, на основу свих информација које има, исписује следеће функције, где је скуп свих позитивних целих бројева, и представља коефицијент модула .
Сада наш нападач поново проналази , рачунајући :
Онда покушава поново , замена в :
Овог пута има озбиљан проблем. Формули недостају вредности , и . Пошто постоји бесконачан број комбинација ових варијабли, он не може добити никакве додатне информације.
Безбедносна разматрања
Шамирова шема дељења тајне сугерише безбедност са становишта теорије информација. То значи да је математика отпорна чак и на нападача са неограниченом рачунарском снагом. Међутим, коло још увек садржи неколико познатих проблема.
На пример, Шамирова шема не ствара фрагменти које треба проверити, односно људи могу слободно представити лажне фрагменте и ометати враћање исправне тајне. Непријатељски чувар фрагмента са довољно информација могао би чак да произведе још један фрагмент променом по сопственом нахођењу. Овај проблем се решава коришћењем проверљиве шеме дељења тајне, као што је Фелдманова шема.
Други проблем је што је дужина било ког фрагмента једнака дужини одговарајуће тајне, тако да је дужину тајне лако одредити. Овај проблем се може решити тривијално паддинг тајна са произвољним бројевима до фиксне дужине.
На крају, важно је напоменути да се наши безбедносни проблеми могу проширити и изван самог дизајна. За криптографске апликације у стварном свету, често постоји претња од напада са стране канала где нападач покушава да извуче корисне информације из времена извршавања апликације, кеширања, рушења итд. Ако је ово забринутост, током развоја треба пажљиво размотрити коришћење заштитних мера као што су функције и тражење у сталном времену, спречавање меморисања да се сачува на диску и низ других разматрања која су ван оквира овог чланка.
Демо
На Постоји интерактивна демонстрација Шамирове шеме дељења тајне. Демонстрација на основу библиотеке , који је и сам ЈаваСцрипт порт популарног програма . Имајте на уму да израчунавање великих вредности , и може потрајати неко време.
Извор: ввв.хабр.цом