Zvažme scénář, kdy je nutné zajistit bezpečnost bankovního trezoru. Ten se považuje za zcela neprůstřelný bez klíče, který obdržíte hned první pracovní den. Vaším cílem je bezpečně uchovat klíč.

Předpokládejme, že jste se rozhodli klíč neustále nosit u sebe a poskytovat přístup k trezoru podle potřeby. Rychle však zjistíte, že takové řešení se prakticky neškáluje, protože pokaždé je nutná vaše fyzická přítomnost pro otevření trezoru. A co dovolené, které vám slíbili? Navíc je tu ještě strašidelnější otázka: co když ztratíte jediný klíč?

S myšlenkou na dovolenou jste se rozhodli udělat kopii klíče a svěřit ji jinému zaměstnanci. Uvědomujete si však, že to také není ideální. Dvojí počet klíčů znamená také dvojnásobné možnosti krádeže klíče.

Bezradně ničíte dublikat a rozhodujete se rozdělit původní klíč na dvě části. Teď si říkáte, že dva důvěryhodní lidé s částmi klíče musí být fyzicky přítomni, aby klíč složili a otevřeli trezor. To znamená, že zloděj musí ukrást dvě části, což je dvakrát těžší než ukrást jeden klíč. Ale brzy si uvědomíte, že tento plán není o moc lepší než mít jen jeden klíč, protože pokud někdo ztratí jednu část klíče, celý klíč nelze obnovit.

Problém lze vyřešit sérií dalších klíčů a zámků, ale při takovém přístupu se rychle vyžaduje mnoho klíčů a zámků. Rozhodujete se, že v ideálním plánu by mělo být rozděleno klíče, aby bezpečnost nespoléhala zcela na jednu osobu. Také závěříte, že by mělo existovat určité prahové množství částí, aby při ztrátě jedné části (nebo pokud osoba odejde na dovolenou) zůstal celý klíč funkční.

Jak rozdělit tajemství

O takovém typu schématu správy klíčů přemýšlel Adi Shamir v roce 1979, když publikoval svou práci „Jak rozdělit tajemství“. V článku se stručně vysvětluje tzv. prahové schéma pro efektivní rozdělení tajné hodnoty (například kryptografického klíče) na části. A teprve když jsou shromážděny alespoň z části, lze tajemství snadno obnovit. .

Z hlediska bezpečnosti je důležitou vlastností tohoto schématu to, že útočník by neměl zjistit absolutně nic, pokud nemá alespoň částí. I přítomnost částí by neměla poskytovat žádné informace. Tento vlastnost nazýváme semastrickou bezpečností.

Polynomiální interpolace

Prahové schéma Shamir je postaveno kolem konceptu polynomiální interpolace.Pokud nejste s tímto konceptem obeznámeni, je to vlastně docela jednoduché. V podstatě, pokud jste někdy kreslili body na grafu a pak je spojovali čarami nebo křivkami, již jste ho použili!

Mezi dvěma body lze nakreslit neomezené množství polynomů druhého stupně. Abychom vybrali jediný, potřebujeme třetí bod. Ilustrace: Wikipedia

Zvažme polynom prvního stupně, . Kolik bodů potřebujete, pokud chcete nakreslit tuto funkci na grafu? No, víme, že je to lineární funkce, která tvoří čáru, a proto potřebujeme alespoň dva body. Dále zvažme polynomiální funkci druhého stupně, . Je to kvadratická funkce, a proto k vykreslení grafu potřebujeme alespoň tři body. Co říkáte na polynom třetího stupně? Alespoň čtyři body. A tak dále.

Opravdu skvělá věc na této vlastnosti je, že, vezmeme-li v úvahu stupeň polynomiální funkce a alespoň bodů, můžeme odvodit další body pro tuto polynomiální funkci. Extrapolaci těchto dalších bodů nazýváme polynomiální interpolace..

Sestavování tajemství

Možná už chápete, že zde vstupuje do hry chytrý Shamirův plán. Předpokládejme, že naše tajemství je — to je . Můžeme převést na bod na grafu a vymyslet polynomiální funkci stupně , která tento bod splňuje. Připomeňme, že bude naším prahem požadovaných částí, takže pokud nastavíme práh na tři části, musíme zvolit polynomiální funkci stupně dva.

Náš polynom bude mít tvar , kde a — náhodně vybraná kladná celá čísla. Jen stavíme polynom stupně , kde volný koeficient  je naše tajemství, a každý z následujících členů je náhodně vybraný kladný koeficient. Pokud se vrátíme k původnímu příkladu a předpokládáme, že , pak získáme funkci .

V této fázi můžeme generovat úseky připojením unikátních celých čísel v , kde (protože to je naše tajemství). V tomto příkladu chceme rozdat čtyři úseky s prahem tři, takže náhodně generujeme body a posíláme jeden bod každému ze čtyř důvěryhodných osob, strážců klíče. Také informujeme lidi, že , protože se považuje za veřejnou informaci a je potřebná pro obnovu .

Obnova tajemství

Již jsme se zabývali konceptem polynomické interpolace a tím, že leží v základech Shamirova schématu . Když jakékoli tři z čtyř důvěryhodných osob chtějí obnovit , potřebují pouze interpolovat s jejich unikátními body. K tomu mohou určit své body a vypočítat interpolující Lagrangeův polynom pomocí následujícího vzorce. Pokud vám programování dává větší smysl než matematika, pak pi je v podstatě operátor for, který násobí všechny výsledky, a sigma je for, která všechno sčítá.

Při můžeme to vyřešit následujícím způsobem a vrátit naši původní polynomickou funkci:

Jelikož víme, že , obnova se provádí jednoduše:

Použití nezabezpečené celočíselné aritmetiky

I když jsme úspěšně aplikovali základní myšlenku Shamira , zbývá nám problém, který jsme dosud ignorovali. Naše polynomická funkce používá nezabezpečenou celočíselnou aritmetiku. Mějte na paměti, že s každým dalším bodem, který útočník získává na grafu naší funkce, zůstává méně možností pro ostatní body. To můžete vidět na vlastní oči, když kreslíte graf s rostoucím počtem bodů pro polynomickou funkci s použitím celočíselné aritmetiky. To je kontraproduktivní pro náš deklarovaný cíl bezpečnosti, protože útočník by neměl zjistit absolutně nic, dokud nemá alespoň fragments.

Abychom demonstrovali, jak slabá je schéma s celočíselnou aritmetikou, zvažme scénář, ve kterém útočník získal dva body a ví veřejnou informaci, že . Z těchto informací může odvodit , rovný dvěma, a dosadit do vzorce známé hodnoty a .

Pak může útočník zjistit , spočítáním :

Jelikož jsme určili jako náhodně vybraná celá kladná čísla, existuje omezený počet možných . Pomocí těchto informací může útočník odvodit , jelikož vše, co je větší než 5, udělá negativním. To se ukazuje jako pravdivé, protože jsme určili

Pak může útočník spočítat možné hodnoty , nahrazením v :

S omezenou sadou variant pro se stává jasné, jak snadné je odhadnout a ověřit hodnoty . Tady je celkem pět variant.

Řešení problému s nebezpečnou celočíselnou aritmetikou

Aby se tato zranitelnost odstranila, navrhuje Shamir použít modulární aritmetiku, nahrazením na , kde a — množstvím všech prvočísel.

Rychle si připomeňme, jak funguje modulární aritmetika. Hodiny s ručičkami jsou již známý koncept. Používají hodiny, které jsou . Jakmile ručička hodin projde kolem dvanácti, vrací se k jedné. Zajímavou vlastností tohoto systému je to, že pouhým pohledem na hodiny nemůžeme odvodit, kolikrát se ručička otočila. Nicméně pokud víme, že ručička hodin prošla 12 čtyřikrát, můžeme pomocí jednoduchého vzorce zcela určit počet uplynulých hodin , kde  — je náš dělitel (zde ),  — je koeficient (kolikrát dělitel bez zbytku přechází do původního čísla, zde ), a  — je zbytek, který obvykle vrací volání operátoru podle modulu (zde ). Znalost všech těchto hodnot nám umožňuje vyřešit rovnici pro , ale pokud koeficient vynecháme, nikdy nebudeme moci obnovit původní hodnotu.

Může být demonstrováno, jak to zlepšuje bezpečnost našeho schématu, použitím schématu na našem předchozím příkladu a použitím . Naše nová polynomická funkce , a nové body . Nyní mohou správci klíče znovu použít polynomickou interpolaci pro obnovu naší funkce, ale tentokrát musí být operace sčítání a násobení doprovázeny zjednodušením podle modulu (např. ).

Použitím tohoto nového příkladu předpokládejme, že útočník zjistil dvě z těchto nových bodů, , a veřejné informace . Tentokrát útočník na základě všech dostupných informací odvozuje následující funkce, kde  — množina všech kladných celých čísel, a představuje koeficient modulu .

Nyní náš útočník opět nachází , vypočítavá :

Poté se znovu pokouší odvodit , nahrazením v :

Tentokrát má vážný problém. Ve vzorci chybí hodnoty , a . Jelikož existuje nekonečné množství kombinací těchto proměnných, nemůže získat žádné další informace.

Zabezpečení

Schéma dělení tajemství Shamirovy nabízí bezpečnost z hlediska teorie informace. To znamená, že matematika je odolná i vůči útočníkovi s neomezeným výpočetním výkonem. Přesto schéma stále obsahuje několik známých problémů.

Například Shamirovo schéma nevytváří ověřitelné útržky, což znamená, že lidé mohou svobodně předkládat falešné útržky a komplikovat obnovu správného tajemství. Nepřátelský správce útržků s dostatečnými informacemi může dokonce vyprodukovat jiný útržek, když změní podle svého uvážení. Tento problém se řeší pomocí ověřitelných schémat dělení tajemství, jako je Feldmanovo schéma.

Dalším problémem je to, že délka jakéhokoli útržku je rovna délce odpovídajícího tajemství, takže délku tajemství lze snadno určit. Tento problém se řeší triviálním naplněním tajemství libovolnými čísly do pevné délky.

Nakonec je důležité poznamenat, že naše obavy o zabezpečení mohou přesahovat samo schéma. Pro skutečné kryptografické aplikace často existuje hrozba útoků prostřednictvím bočních kanálů, kdy se útočník pokouší získat užitečné informace z doby běhu aplikace, vyrovnávací paměti, selhání atd. Pokud to vyvolává obavy, je vhodné při vývoji pečlivě zvážit použití ochranných opatření, jako jsou funkce a vyhledávání s konstantní dobou běhu, zamezit ukládání paměti na disk a promyslet řadu dalších věcí, které přesahují tento článek.

Demo

Na tato stránka existuje interaktivní demonstrace Shamirova schéma dělení tajemství. Demonstrace byla vytvořena na základě knihovny ssss-js, která je sama o sobě JavaScriptovým portem populárního programu ssssVezměte prosím na vědomí, že výpočet velkých hodnot , a může trvat nějakou dobu.

Zdroj: habr.com