Zvážte scenár, v ktorom potrebujete zabezpečiť bankový trezor. Považuje sa za absolútne nedobytné bez kľúča, ktorý dostanete hneď v prvý deň práce. Vaším cieľom je bezpečne uložiť kľúč.

Povedzme, že ste sa rozhodli mať kľúč vždy pri sebe a poskytnúť tak prístup k úložisku podľa potreby. Rýchlo však zistíte, že takéto riešenie nie je v praxi dobre škálovateľné, pretože pri každom otvorení úložiska je potrebná vaša fyzická prítomnosť. A čo dovolenka, ktorú ste sľúbili? Navyše, otázka je ešte desivejšia: čo keby ste stratili svoj jediný kľúč?

S ohľadom na vašu dovolenku sa rozhodnete urobiť kópiu kľúča a zveriť ju inému zamestnancovi. Chápete však, že ani to nie je ideálne. Zdvojnásobením počtu kľúčov zdvojnásobíte aj pravdepodobnosť krádeže kľúčov.

V zúfalstve zničíte duplikát a rozhodnete sa rozdeliť pôvodný kľúč na polovicu. Teraz by ste si mysleli, že na vyzdvihnutie kľúča a otvorenie trezoru by museli byť fyzicky prítomní dvaja dôveryhodní ľudia s úlomkami kľúča. To znamená, že zlodej potrebuje ukradnúť dva kusy, čo je dvakrát ťažšie ako ukradnúť jeden kľúč. Čoskoro si však uvedomíte, že táto schéma nie je oveľa lepšia ako len jeden kľúč, pretože ak niekto stratí polovicu kľúča, celý kľúč sa už nedá získať späť.

Problém je možné vyriešiť sériou ďalších kľúčov a zámkov, ale tento prístup bude rýchlo vyžadovať много kľúče a zámky. Rozhodnete sa, že ideálnym riešením by bolo zdieľať kľúč, aby bezpečnosť nezávisela výlučne na jednej osobe. Tiež ste dospeli k záveru, že musí existovať určitá hranica pre počet fragmentov, takže ak sa jeden fragment stratí (alebo ak osoba odíde na dovolenku), celý kľúč zostane funkčný.

Ako zdieľať tajomstvo

O tomto type schémy správy kľúčov uvažoval Adi Shamir v roku 1979, keď publikoval svoju prácu "Ako zdieľať tajomstvo". Článok stručne vysvetľuje tzv prahová schéma na efektívne rozdelenie tajnej hodnoty (ako je kryptografický kľúč). časti. Potom, kedy a len vtedy, keď aspoň z diely sú zmontované, môžete ľahko obnoviť tajomstvo .

Z bezpečnostného hľadiska je dôležitou vlastnosťou tejto schémy, že útočník by nemal vedieť absolútne nič, pokiaľ nemá aspoň časti. Dokonca aj prítomnosť časti by nemali poskytovať žiadne informácie. Túto vlastnosť nazývame sémantickej bezpečnosti.

Polynomiálna interpolácia

Shamir prahová schéma postavený okolo konceptu polynomiálna interpolácia. Ak tento koncept nepoznáte, je to vlastne celkom jednoduché. V skutočnosti, ak ste niekedy kreslili body do grafu a potom ich spájali čiarami alebo krivkami, už ste to použili!

Prostredníctvom dvoch bodov môžete nakresliť neobmedzený počet polynómov stupňa 2. Na výber jediného z nich potrebujete tretí bod. Ilustrácia: Wikipedia

Uvažujme polynóm s prvým stupňom, . Ak chcete túto funkciu vykresliť do grafu, koľko bodov potrebujete? Vieme, že ide o lineárnu funkciu, ktorá tvorí priamku, a preto potrebuje aspoň dva body. Ďalej zvážte polynomickú funkciu s druhým stupňom, . Ide o kvadratickú funkciu, takže na vykreslenie grafu sú potrebné aspoň tri body. Čo tak polynóm s tretím stupňom? Aspoň štyri body. A tak ďalej a tak ďalej.

Naozaj skvelá vec na tejto vlastnosti je, že vzhľadom na stupeň polynomiálnej funkcie a minimálne bodov, môžeme odvodiť ďalšie body pre túto polynómovú funkciu. Tieto dodatočné body nazývame extrapolácia polynomiálna interpolácia.

Vymýšľanie tajomstva

Možno ste si už uvedomili, že práve tu vstupuje do hry Shamirova šikovná schéma. Povedzme si naše tajomstvo - je . Môžeme sa obrátiť do bodu na grafe a prísť s polynomickou funkciou so stupňom , ktorý tento bod spĺňa. Pripomeňme si to bude náš prah požadovaných fragmentov, takže ak nastavíme prah na tri fragmenty, musíme zvoliť polynomickú funkciu so stupňom dva.

Náš polynóm bude mať tvar Kde и — náhodne vybrané kladné celé čísla. Práve vytvárame polynóm so stupňom , kde voľný koeficient  - Toto je naše tajomstvo a pre každú z nasledujúcich pojmov existuje náhodne vybraný kladný koeficient. Ak sa vrátime k pôvodnému príkladu a predpokladáme, že , potom dostaneme funkciu .

V tomto bode môžeme generovať fragmenty spojením jedinečné celé čísla v Kde (lebo je to naše tajomstvo). V tomto príklade chceme rozdeliť štyri fragmenty s prahom troch, takže náhodne generujeme body a pošlite jeden bod každej zo štyroch dôveryhodných osôb, správcov kľúča. Dávame to vedieť aj ľuďom , pretože sa to považuje za verejnú informáciu a je potrebné na obnovu .

Obnovenie tajomstva

Už sme diskutovali o koncepte polynomiálnej interpolácie a o tom, ako je základom Shamirovej prahovej schémy . Keď ktorýkoľvek traja zo štyroch správcov chcú obnoviť , potrebujú iba interpoláciu s vlastnými jedinečnými bodmi. Na tento účel si môžu určiť svoje body a vypočítajte Lagrangeov interpolačný polynóm pomocou nasledujúceho vzorca. Ak je vám programovanie jasnejšie ako matematika, potom je pi v podstate operátor for, ktorý vynásobí všetky výsledky a sigma je for, ktorý všetko zráta.

Na môžeme to vyriešiť takto a vrátiť našu pôvodnú polynómovú funkciu:

Keďže to vieme , zotavenie urobené jednoducho:

Použitie nezabezpečenej celočíselnej aritmetiky

Aj keď sme úspešne aplikovali základnú myšlienku Shamir , zostal nám problém, ktorý sme doteraz ignorovali. Naša polynomická funkcia používa nebezpečnú celočíselnú aritmetiku. Všimnite si, že za každý ďalší bod, ktorý útočník získa na grafe našej funkcie, existuje menej možností pre ďalšie body. Môžete to vidieť na vlastné oči, keď pomocou celočíselnej aritmetiky vykreslíte rastúci počet bodov pre polynomickú funkciu. To je kontraproduktívne voči nášmu stanovenému bezpečnostnému cieľu, pretože útočník by nemal vedieť absolútne nič, kým to nebude mať aspoň úlomky.

Ak chcete demonštrovať, aký slabý je celý aritmetický obvod, zvážte scenár, v ktorom útočník získal dva body a pozná verejné informácie, že . Z týchto informácií vie vydedukovať , rovné dvom a do vzorca vložte známe hodnoty и .

Útočník potom môže nájsť , počítanie :

Keďže sme definovali ako náhodne vybrané kladné celé čísla existuje obmedzený počet možných . Pomocou týchto informácií môže útočník dedukovať , pretože bude stačiť čokoľvek väčšie ako 5 negatívne. Ukazuje sa, že je to pravda, pretože sme sa rozhodli

Útočník potom môže vypočítať možné hodnoty nahradenie в :

S obmedzenými možnosťami pre je jasné, aké ľahké je vybrať a skontrolovať hodnoty . Tu je len päť možností.

Riešenie problému s nebezpečnou celočíselnou aritmetikou

Na odstránenie tejto zraniteľnosti Shamir navrhuje použiť modulárnu aritmetiku, nahradiť na Kde и — množina všetkých prvočísel.

Rýchlo si pripomeňme, ako funguje modulárna aritmetika. Hodiny s ručičkami sú známy pojem. Používa hodinky, tj . Len čo hodinová ručička prejde dvanástou, vráti sa k jednotke. Zaujímavou vlastnosťou tohto systému je, že jednoduchým pohľadom na hodiny nedokážeme odvodiť, koľko otáčok hodinová ručička urobila. Ak však vieme, že hodinová ručička uplynula štyrikrát 12, môžeme úplne určiť počet hodín, ktoré uplynuli pomocou jednoduchého vzorca Kde  je náš deliteľ (tu ),  je koeficient (koľkokrát sa deliteľ dostane do pôvodného čísla bezo zvyšku, tu ), a  je zvyšok, ktorý zvyčajne vracia volanie operátora modulo (tu ). Poznanie všetkých týchto hodnôt nám umožňuje vyriešiť rovnicu pre , ale ak nám chýba koeficient, nikdy sa nám nepodarí vrátiť pôvodnú hodnotu.

Môžeme ukázať, ako to zlepšuje bezpečnosť našej schémy, aplikovaním schémy na náš predchádzajúci príklad a použitím . Naša nová polynomická funkcia a nové body . Teraz môžu správcovia kľúčov opäť použiť polynomiálnu interpoláciu na rekonštrukciu našej funkcie, len tentoraz musia operácie sčítania a násobenia sprevádzať modulo redukcia (napr ).

Pomocou tohto nového príkladu predpokladajme, že útočník sa naučil dva z týchto nových bodov, a verejné informácie . Tentoraz útočník na základe všetkých informácií, ktoré má, vypíše nasledujúce funkcie, kde  je množina všetkých kladných celých čísel a predstavuje modulový koeficient .

Teraz náš útočník opäť našiel , výpočet :

Potom to skúsi znova nahradenie в :

Tentoraz má vážny problém. Vo vzorci chýbajú hodnoty , и . Keďže existuje nekonečné množstvo kombinácií týchto premenných, nemôže získať žiadne ďalšie informácie.

Úvahy o bezpečnosti

Shamirova schéma tajného zdieľania naznačuje bezpečnosť z pohľadu teórie informácie. To znamená, že matematika je odolná aj voči útočníkovi s neobmedzeným výpočtovým výkonom. Okruh však stále obsahuje niekoľko známych problémov.

Napríklad Shamirova schéma nevytvára úlomky, ktoré sa majú skontrolovať, to znamená, že ľudia môžu voľne prezentovať falošné fragmenty a zasahovať do získania správneho tajomstva. Nepriateľský strážca fragmentu s dostatočnými informáciami by dokonca mohol zmenou vytvoriť ďalší fragment podľa vlastného uváženia. Tento problém je vyriešený pomocou overiteľné schémy zdieľania tajomstiev, ako je Feldmanova schéma.

Ďalším problémom je, že dĺžka akéhokoľvek fragmentu sa rovná dĺžke zodpovedajúceho tajomstva, takže dĺžku tajomstva je ľahké určiť. Tento problém sa dá vyriešiť triviálne vypchávka tajný s ľubovoľnými číslami do pevnej dĺžky.

Nakoniec je dôležité poznamenať, že naše obavy o bezpečnosť môžu presahovať rámec samotného dizajnu. Pri kryptografických aplikáciách v reálnom svete často hrozia útoky na bočný kanál, pri ktorých sa útočník pokúša získať užitočné informácie z času spustenia aplikácie, ukladania do vyrovnávacej pamäte, zlyhaní atď. Ak je to problém, počas vývoja by sa malo dôkladne zvážiť používanie ochranných opatrení, ako sú funkcie a vyhľadávanie v konštantnom čase, zabránenie ukladaniu pamäte na disk a množstvo ďalších úvah, ktoré presahujú rámec tohto článku.

demonštrácie

Na na tejto stránke Je tu interaktívna ukážka Shamirovej schémy tajného zdieľania. Ukážka založená na knižnici ssss-js, ktorý je sám o sebe JavaScriptovým portom obľúbeného programu ssss. Všimnite si, že výpočet veľkých hodnôt , и môže nejaký čas trvať.

Zdroj: hab.com