Разгледзім сцэнар, калі неабходна гарантаваць бяспеку банкаўскага сховішча. Яно лічыцца абсалютна непрыступным без ключа, які вам выдаюць у першы ж дзень працы. Ваша мэта - надзейна захаваць ключ.
Выкажам здагадку, вы вырашылі ўвесь час захоўваць ключ пры сабе, падаючы доступ да сховішча па меры неабходнасці. Але вы хутка зразумееце, што такое рашэнне на практыцы нармальна не маштабуецца, таму што кожны раз для адкрыцця сховішча патрабуецца ваша фізічная прысутнасць. А як наконт водпуску, якія вам абяцалі? Акрамя таго яшчэ больш палохае пытанне: а што, калі вы страцілі адзіны ключ?
З думкай аб водпуску вы вырашылі зрабіць копію ключа і даверыць яе іншаму супрацоўніку. Аднак вы разумееце, што гэта таксама не ідэальна. Падвойваючы колькасць ключоў, вы таксама падвоілі магчымасці крадзяжу ключа.
Страціўшы надзею, вы знішчаеце дублікат і вырашаеце падзяліць зыходны ключ напалову. Цяпер, вы думаеце, два давераных чалавека з фрагментамі ключоў павінны фізічна прысутнічаць, каб сабраць ключ і адкрыць сховішча. Гэта азначае, што злодзею неабходна выкрасці два фрагменты, што ўдвая цяжэй крадзяжы аднаго ключа. Аднак неўзабаве вы разумееце, што гэтая схема ненашмат лепш, чым проста адзін ключ, таму што калі нехта страціць палову ключа, поўны ключ нельга аднавіць.
Праблему можна вырашыць з дапамогай серыі дадатковых ключоў і замкаў, але пры такім падыходзе хутка запатрабуецца шмат ключоў і замкаў. Вы вырашаеце, што ў ідэальнай схеме трэба падзяліць ключ, каб бяспека не належыла цалкам на аднаго чалавека. Вы таксама складаеце, што павінен існаваць нейкі парог колькасці фрагментаў, каб пры страце аднаго фрагмента (ці калі чалавек сышоў у адпачынак) увесь ключ заставаўся функцыянальным.
Як падзяліць сакрэт
Аб такім тыпе схемы кіравання ключамі думаў Ады Шамір у 1979 году, калі апублікаваў сваю працу . У артыкуле коратка тлумачыцца так званая 
парогавая схема для эфектыўнага падзелу сакрэтнага значэння (напрыклад, крыптаграфічнага ключа) на частак. Затым, калі і толькі калі хаця б з частак сабраны, можна лёгка аднавіць сакрэт .
З пункту гледжання бяспекі важнай уласцівасцю гэтай схемы з'яўляецца тое, што зламыснік не павінен даведацца абсалютна нічога, калі ў яго няма хаця б частак. Нават наяўнасць частак не павінна даваць ніякай інфармацыі. Мы называем гэтую ўласцівасць семантычнай бяспекай.
Палінаміальная інтэрпаляцыя
Парогавая схема Шаміра пабудавана вакол канцэпцыі паліномнай інтэрпаляцыі. Калі вы не знаёмыя з гэтай канцэпцыяй, яна насамрэч даволі простая. Наогул, калі вы калі-небудзь малявалі кропкі на графіцы, а затым злучалі іх лініямі ці крывымі, то ўжо выкарыстоўвалі яе!
Праз дзве кропкі можна правесці неабмежаваную колькасць паліномаў ступені 2. Каб выбраць з іх адзіны - патрэбна трэцяя кропка. Ілюстрацыя:
Разгледзім палінам са ступенню адзін, . Калі вы хочаце пабудаваць гэтую функцыю на графіцы, колькі кропак вам трэба? Ну, мы ведаем, што гэта лінейная функцыя, якая ўтварае лінію і таму трэба па меншай меры дзве кропкі. Далей разгледзім паліномны функцыю са ступенню два, . Гэта квадратычная функцыя, таму для пабудовы графіка патрабуецца не менш за тры кропкі. Як наконт мнагачлена са ступенню тры? Прынамсі, чатыры кропкі. І гэтак далей і да таго падобнае.
Сапраўды класная рэч у гэтай уласцівасці складаецца ў тым, што, улічваючы ступень паліномнай функцыі і, прынамсі, кропак, мы можам вывесці дадатковыя кропкі для гэтай паліномны функцыі. Экстрапаляцыю гэтых дадатковых кропак мы называем паліномнай інтэрпаляцыяй.
Складанне сакрэту
Магчыма, вы ўжо зразумелі, што тут уступае ў гульню разумная схема Шаміра. Выкажам здагадку, што наш сакрэт - Гэта . Мы можам ператварыць у кропку на графіцы і прыдумаць паліномны функцыю са ступенню , якая задавальняе гэтай кропцы. Нагадаем, што будзе нашым парогам патрабаваных фрагментаў, таму калі мы ўсталяваць парог у тры фрагменты, то павінны абраць паліномны функцыю са ступенню два.
Наш паліном будзе мець форму , Дзе и - Выпадковым чынам выбраныя станоўчыя цэлыя лікі. Мы ўсяго толькі які будуецца паліном са ступенню , дзе вольны каэфіцыент - гэта наш сакрэт , а ў кожнага з наступных чальцоў ёсць выпадковым чынам абраны дадатны каэфіцыент. Калі вярнуцца да першапачатковага прыкладу і выказаць здагадку, што , то тады мы атрымаем функцыю .
На гэтым этапе мы можам генераваць фрагменты, падлучыўшы унікальных цэлых лікаў у , Дзе (Бо гэта наш сакрэт). У дадзеным прыкладзе мы хочам раздаць чатыры фрагменты з парогам тры, таму выпадковым чынам генеруем кропкі. і адпраўляем па адной кропцы кожнаму з чатырох давераных чалавек, захавальнікаў ключа. Мы таксама паведамляем людзям, што , так як гэта лічыцца публічнай інфармацыяй і неабходна для аднаўлення .
Аднаўленне сакрэту
Мы ўжо абмяркоўвалі канцэпцыю паліномнай інтэрпаляцыі і тое, што яна ляжыць у аснове парогавай схемы Шаміра . Калі любыя тры з чатырох давераных асоб хочуць аднавіць , ім трэба толькі інтэрпаліраваць са сваімі ўнікальнымі кропкамі. Для гэтага яны могуць вызначыць свае кропкі і разлічыць інтэрпаляцыйны паліном Лагранжа, выкарыстоўваючы наступную формулу. Калі праграмаванне вам больш зразумела, чым матэматыка, то пі - гэта па сутнасці аператар for, Які памнажае ўсе вынікі, а сігма - гэта for, які ўсё складае.
Пры мы можам гэта вырашыць наступным чынам і вярнуць нашу зыходную паліномны функцыю:
Бо мы ведаем, што , аднаўленне ажыццяўляецца проста:
Выкарыстанне небяспечнай цэлалікай арыфметыкі
Хоць мы паспяхова ўжылі асноўную ідэю Шаміра , у нас застаецца праблема, якую мы ігнаравалі да цяперашняга моманту. Наша паліномны функцыя выкарыстоўвае небяспечную цэлалікавую арыфметыку. Улічыце, што для кожнай дадатковай кропкі, якую атакавалы атрымлівае на графіцы нашай функцыі, застаецца меншая колькасць магчымасцяў для іншых кропак. Вы можаце ўбачыць гэта на свае вочы, калі будуеце графік з павелічэннем колькасці кропак для паліномны функцыі з выкарыстаннем цэлалікай арыфметыкі. Гэта контрпрадуктыўна для нашай заяўленай мэты бяспекі, таму што зламыснік не павінен абсалютна нічога даведацца, пакуль у іх не будзе хаця б фрагментаў.
Каб прадэманстраваць, наколькі слабая схема з цэлалікай арыфметыкай, разгледзім сцэнар, у якім зламыснік атрымаў дзве кропкі. і ведае публічную інфармацыю, што . З гэтай інфармацыі ён можа вывесці , роўны двум, і падлучыць у формулу вядомыя значэння и .
Затым зламыснік можа знайсці , палічыўшы :
Паколькі мы вызначылі як выпадкова выбраныя цэлыя станоўчыя лікі, ёсць абмежаваную колькасць магчымых . З дапамогай гэтай інфармацыі зламыснік можа вывесці , паколькі ўсё, што больш за 5, зробіць адмоўным. Гэта аказваецца праўдай, паколькі мы вызначылі
Затым зламыснік можа разлічыць магчымыя значэння , замяніўшы в :
З абмежаваным наборам варыянтаў для становіцца зразумела, наколькі лёгка падабраць і праверыць значэння . Тут усяго пяць варыянтаў.
Рашэнне праблемы з небяспечнай цэлалікай арыфметыкай
Каб ухіліць гэтую ўразлівасць, Шамір прапануе выкарыстоўваць модульную арыфметыку, замяніўшы на , Дзе и - мноства ўсіх простых лікаў.
Хутка ўспомнім, як працуе модульная арыфметыка. Гадзіны са стрэлкамі - ужо знаёмая канцэпцыя. Яна выкарыстоўвае гадзіннік, якія з'яўляюцца . Як толькі гадзіннікавая стрэлка праходзіць міма дванаццаці, яна вяртаецца да аднаго. Цікавай уласцівасцю гэтай сістэмы з'яўляецца тое, што проста паглядзеўшы на гадзіннік, мы не можам вывесці, колькі абарачэнняў зрабіла гадзіннікавая стрэлка. Аднак калі мы ведаем, што гадзіннікавая стрэлка чатыры разы абмінула 12, можна цалкам вызначыць колькасць мінулых гадзін з дапамогай простай формулы. , Дзе - гэта наш дзельнік (тут ), - Гэта каэфіцыент (колькі разоў дзельнік без астатку пераходзіць у зыходны лік, тут ), А – гэта рэштка, якая звычайна і вяртае выклік аператара па модулі (тут ). Веды ўсіх гэтых значэнняў дазваляе нам вырашыць раўнанне для , Але калі мы прапусцім каэфіцыент, то ніколі не зможам аднавіць зыходнае значэнне.
Можна прадэманстраваць, як гэта паляпшае бяспеку нашай схемы, ужыўшы схему да нашага папярэдняга прыкладу і выкарыстоўваючы . Наша новая паліномны функцыя , а новыя кропкі . Цяпер захавальнікі ключа могуць яшчэ раз выкарыстоўваць паліномны інтэрпаляцыю для аднаўлення нашай функцыі, толькі на гэты раз аперацыі складання і множання павінны суправаджацца скарачэннем па модулі (Напрыклад, ).
Выкарыстоўваючы гэты новы прыклад, выкажам здагадку, што зламыснік даведаўся дзве з гэтых новых кропак, , а публічная інфармацыя . Гэтым разам атакавалы на аснове ўсёй наяўнай у яго інфармацыі выводзіць наступныя функцыі, дзе - Набор усіх станоўчых цэлых лікаў, а уяўляе каэфіцыент модуля .
Цяпер наш зламыснік зноў знаходзіць , вылічыўшы :
Затым ён зноў спрабуе вывесці , замяніўшы в :
На гэты раз у яго сур'ёзная праблема. У формуле адсутнічаюць значэнні , и . Паколькі існуе бясконцая колькасць камбінацый гэтых зменных, ён не можа атрымаць ніякай дадатковай інфармацыі.
Меркаванні бяспекі
Схема падзелу сакрэту Шаміра прапануе бяспека з пункту гледжання тэорыі інфармацыі. Гэта значыць, што матэматыка з'яўляецца стойкай нават супраць зламысніка з неабмежаванай вылічальнай магутнасцю. Аднак схема па-ранейшаму змяшчае некалькі вядомых праблем.
Напрыклад, схема Шаміра не стварае правяраемых фрагментаў, гэта значыць людзі могуць свабодна прад'яўляць падробленыя фрагменты і перашкаджаць аднаўленню правільнага сакрэту. Варожы захавальнік фрагментаў з дастатковай інфармацыяй можа нават вырабіць іншы фрагмент, змяніўшы на сваё меркаванне. Гэтая праблема вырашаецца з дапамогай правяраемых схем падзелу сакрэту, такіх як схема Фельдмана.
Іншая праблема заключаецца ў тым, што даўжыня любога фрагмента роўная даўжыні адпаведнага сакрэту, так што даўжыню сакрэту лёгка вызначыць. Гэтая праблема вырашаецца трывіяльнай набіўкай сакрэту адвольнымі лікамі да фіксаванай даўжыні.
Нарэшце, важна адзначыць, што нашыя асцярогі з нагоды бяспекі могуць выходзіць за рамкі самой схемы. Для рэальных крыптаграфічных прыкладанняў часта існуе пагроза нападаў па іншых каналах, калі зламыснік спрабуе атрымаць карысную інфармацыю з часу выканання прыкладання, кэшавання, збояў і г.д. Калі гэта выклікае заклапочанасць, варта падчас распрацоўкі старанна разгледзець выкарыстанне ахоўных мер, такіх як функцыі і пошук са сталым часам выканання, прадухіліць захаванне памяці на дыск і прадумаць шэраг іншых рэчаў, якія выходзяць за рамкі гэтага артыкула.
дэма
На ёсць інтэрактыўная дэманстрацыя cхема падзелу сакрэту Шаміра. Дэманстрацыя зроблена на базе бібліятэкі , якая сама па сабе з'яўляецца JavaScript-портам папулярнай праграмы . Звярніце ўвагу, што вылічэнне вялікіх значэнняў , и можа заняць некаторы час.
Крыніца: habr.com