Zvažte scénář, kdy potřebujete zajistit bankovní trezor. Je považován za absolutně nedobytný bez klíče, který dostanete první den v práci. Vaším cílem je bezpečně uložit klíč.
Předpokládejme, že se rozhodnete mít klíč neustále u sebe a poskytnout tak přístup do trezoru podle potřeby. Rychle si ale uvědomíte, že takové řešení není v praxi dobře škálovatelné, protože pokaždé, když je potřeba být fyzicky přítomen k otevření trezoru. A co dovolená, kterou jste slíbili? Navíc je otázka ještě děsivější: co kdybyste ztratili jediný klíč?
S nápadem na dovolenou se rozhodnete vytvořit kopii klíče a svěřit ji jinému zaměstnanci. Chápete však, že to také není ideální. Zdvojnásobením počtu klíčů jste také zdvojnásobili šance na krádež klíčů.
Zoufalí zničíte duplikát a rozhodnete se rozdělit původní klíč na polovinu. Nyní si myslíte, že k vyzvednutí klíče a otevření trezoru musí být fyzicky přítomni dva důvěryhodní lidé s fragmenty klíče. To znamená, že zloděj potřebuje ukrást dva úlomky, což je dvakrát tak obtížné než ukrást jeden klíč. Brzy si však uvědomíte, že toto schéma není o moc lepší než jen jeden klíč, protože pokud někdo ztratí polovinu klíče, celý klíč nelze obnovit.
Problém lze vyřešit řadou dalších klíčů a zámků, ale tento přístup bude rychle vyžadovat много klíče a zámky. Rozhodnete se, že ideální schéma je sdílet klíč, aby bezpečnost nezávisela výhradně na jedné osobě. Dojdete také k závěru, že musí existovat určitá hranice pro počet fragmentů, aby v případě ztráty jednoho fragmentu (nebo pokud osoba odjela na dovolenou) zůstal celý klíč funkční.
Jak sdílet tajemství
Tento typ schématu správy klíčů napadl Adi Shamir v roce 1979, když publikoval svou práci . Článek stručně vysvětluje tzv 
prahové schéma pro efektivní rozdělení tajné hodnoty (například kryptografického klíče). díly. Pak, kdy a jen kdy alespoň z díly jsou sestaveny, můžete snadno obnovit tajemství .
Z bezpečnostního hlediska je důležitou vlastností tohoto schématu to, že útočník by se neměl naučit absolutně nic, pokud nemá alespoň díly. Dokonce i přítomnost části by neměly poskytovat žádné informace. Tuto vlastnost nazýváme sémantické zabezpečení.
Polynomiální interpolace
Schéma Threshold Shamir postavený kolem konceptu polynomiální interpolace. Pokud tento koncept neznáte, je to vlastně docela jednoduché. Obecně platí, že pokud jste někdy nakreslili body na grafu a poté je spojili čarami nebo křivkami, již jste to použili!
Prostřednictvím dvou bodů můžete nakreslit neomezený počet polynomů stupně 2. K výběru jediného z nich potřebujete třetí bod. Ilustrace:
Uvažujme polynom s prvním stupněm, . Pokud chcete tuto funkci vykreslit do grafu, kolik bodů potřebujete? Víme, že se jedná o lineární funkci, která tvoří přímku, a proto potřebujeme alespoň dva body. Dále uvažujme polynomiální funkci se stupněm dva, . Jedná se o kvadratickou funkci, takže k vykreslení grafu jsou potřeba alespoň tři body. Co třeba polynom se stupněm tři? Alespoň čtyři tečky. A tak dále a tak dále.
Opravdu skvělé na této vlastnosti je to, že vzhledem ke stupni polynomiální funkce a minimálně body, můžeme pro tuto polynomickou funkci odvodit další body. Tyto dodatečné body nazýváme extrapolací polynomiální interpolace.
Dělat tajemství
Možná jste již přišli na to, že právě zde vstupuje do hry Shamirovo chytré schéma. Předpokládejme naše tajemství - Je . Můžeme se otočit k bodu na grafu a přijít s polynomiální funkcí se stupněm , který tento bod splňuje. Odvolej to bude náš práh požadovaných fragmentů, takže pokud nastavíme práh na tři fragmenty, musíme zvolit polynomickou funkci se stupněm dva.
Náš polynom bude mít tvar Kde и jsou náhodně vybraná kladná celá čísla. Prostě sestavíme polynom se stupněm , kde volný koeficient - To je naše tajemství a každý z následujících členy je náhodně vybraný kladný koeficient. Pokud se vrátíme k původnímu příkladu a předpokládáme, že , pak dostaneme funkci .
V tomto okamžiku můžeme generovat fragmenty připojením jedinečná celá čísla v Kde (protože je to naše tajemství). V tomto příkladu chceme rozmístit čtyři fragmenty s prahem tří, takže náhodně generujeme body a poslat jeden bod každému ze čtyř důvěryhodných lidí, držitelů klíče. I to říkáme lidem , protože se považuje za veřejnou informaci a je nezbytná pro obnovu .
Tajné zotavení
Již jsme diskutovali o konceptu polynomiální interpolace a o tom, jak je základem Shamirova prahovacího schématu. . Když tři ze čtyř správců chtějí obnovit , potřebují pouze interpolovat se svými jedinečnými body. K tomu mohou definovat své body a vypočítat Lagrangeův interpolační polynom pomocí následujícího vzorce. Pokud je vám programování jasnější než matematika, pak je pí v podstatě operátor for, který násobí všechny výsledky, a sigma je forto všechno sčítá.
na můžeme to vyřešit takto a vrátit naši původní polynomiální funkci:
Protože to víme , zotavení se dělá jednoduše:
Použití nebezpečné celočíselné aritmetiky
Přestože jsme úspěšně použili základní myšlenku Shamira , zůstal nám problém, který jsme doposud ignorovali. Naše polynomiální funkce používá nebezpečnou celočíselnou aritmetiku. Všimněte si, že s každým dalším bodem, který útočník dostane na náš funkční graf, existuje méně možností pro další body. Můžete to vidět na vlastní oči, když vynesete rostoucí počet bodů pro polynomiální funkci pomocí celočíselné aritmetiky. To je kontraproduktivní vůči našemu uvedenému bezpečnostnímu cíli, protože útočník by neměl vědět absolutně nic, dokud to nebude mít alespoň fragmenty.
Chcete-li demonstrovat, jak slabé je celočíselné aritmetické schéma, zvažte scénář, ve kterém útočník získal dva body a zná veřejné informace, že . Z těchto informací může usuzovat , rovnající se dvěma a připojte známé hodnoty ke vzorci и .
Útočník pak může najít , počítání :
Protože jsme definovali jako náhodně vybraná kladná celá čísla existuje omezený počet možných . Z těchto informací může útočník dedukovat , protože cokoliv většího než 5 udělá negativní. To se ukazuje jako pravda, protože jsme se rozhodli
Útočník pak může vypočítat možné hodnoty nahrazovat в :
S omezenými možnostmi pro je jasné, jak snadné je získat a zkontrolovat hodnoty . Zde je pouze pět možností.
Řešení problému s nebezpečnou celočíselnou aritmetikou
Chcete-li tuto zranitelnost opravit, Shamir navrhuje použít modulární aritmetiku nahrazením na Kde и je množina všech prvočísel.
Rychle si připomeňme, jak funguje modulární aritmetika. Ruční hodiny jsou známý pojem. Používá hodinky . Jakmile hodinová ručička přejde dvanáctou, vrátí se na jedničku. Zajímavou vlastností tohoto systému je, že pouhým pohledem na hodiny nedokážeme odvodit, kolik otáček hodinová ručička udělala. Pokud však víme, že hodinová ručička uplynula čtyřikrát 12, můžeme plně určit počet hodin, které uplynuly, pomocí jednoduchého vzorce Kde je náš dělitel (zde ), - toto je koeficient (kolikkrát se dělitel beze zbytku dostane do původního čísla, zde ) a je zbytek, který obvykle vrací volání operátorovi modulo (zde ). Znalost všech těchto hodnot nám umožňuje vyřešit rovnici pro , ale pokud koeficient přeskočíme, nikdy se nám nepodaří obnovit původní hodnotu.
Můžeme demonstrovat, jak to zlepšuje bezpečnost našeho obvodu, použitím obvodu na náš předchozí příklad a pomocí . Naše nová polynomiální funkce a nové body . Nyní mohou klíčoví správci opět použít polynomiální interpolaci k rekonstrukci naší funkce, ale tentokrát po operacích sčítání a násobení musí následovat modulo redukce. (např ).
S použitím tohoto nového příkladu předpokládejme, že se útočník naučil dva z těchto nových bodů, a veřejné informace . Tentokrát útočník na základě všech informací, které má, zobrazí následující funkce, kde je množina všech kladných celých čísel a představuje modulový koeficient .
Nyní náš vetřelec najde znovu , počítání :
Pak se znovu pokusí stáhnout nahrazovat в :
Tentokrát má vážný problém. Ve vzorci chybí hodnoty , и . Protože existuje nekonečné množství kombinací těchto proměnných, nemůže získat žádné další informace.
Bezpečnostní aspekty
Shamirovo schéma tajného sdílení naznačuje informační bezpečnost. To znamená, že matematika je silná i proti útočníkovi s neomezeným výpočetním výkonem. Schéma však stále obsahuje několik známých problémů.
Například schéma Shamir nevytváří fragmenty ke kontrole, to znamená, že lidé mohou volně předkládat falešné fragmenty a zasahovat do získávání správného tajemství. Nepřátelský strážce fragmentu s dostatkem informací může dokonce vytvořit další fragment změnou dle vašeho uvážení. Tento problém je vyřešen pomocí ověřitelná tajná schémata sdílení, jako je Feldmanovo schéma.
Dalším problémem je, že délka libovolného fragmentu se rovná délce odpovídajícího tajenky, takže délku tajenky lze snadno určit. Tento problém je řešen triviálně vycpávka tajné libovolnými čísly až do pevné délky.
Nakonec je důležité poznamenat, že naše obavy o bezpečnost mohou přesahovat samotné schéma. U skutečných kryptografických aplikací často hrozí útoky postranním kanálem, kdy se útočník snaží získat užitečné informace z doby provádění aplikace, ukládání do mezipaměti, pády atd. Pokud vás to znepokojuje, měli byste pečlivě zvážit použití ochranných opatření během vývoje, jako jsou funkce a vyhledávání v konstantním čase, zabránit ukládání paměti na disk a zvážit řadu dalších věcí, které jsou nad rámec tohoto článku.
Demonstrace
Na je zde interaktivní ukázka Shamirova tajného schématu sdílení. Ukázka byla provedena na základě knihovny , který je sám o sobě JavaScriptovým portem oblíbeného programu . Všimněte si, že počítání velkých hodnot , и může chvíli trvat.
Zdroj: www.habr.com