Shamir Secret Sharing

Peněženka je aplikace nebo zařízení pro přijímání a odesílání bitcoinů. Anna chce zálohu, která přežije ztrátu části záznamů. Zvolí tři z pěti: vytvoří se pět různých podílů a libovolné tři platné podíly stejné sady obnoví tajemství. Dva může ztratit, tři už ne. Potřebnému počtu se říká práh; obecně k z n znamená k potřebných podílů z n vytvořených a dovoluje ztrátu n−k. Práh ale nepozná Annin souhlas. Pokud potřebné tři podíly získá někdo jiný nebo se jejich držitelé domluví, obnoví totéž tajemství. Nižší práh usnadňuje obnovu, zároveň zmenšuje skupinu, která ji zvládne bez Anny. [1] [6]

Anna si nepomůže, když všech pět souborů uloží do jediného cloudového účtu. Jeho ztráta či prolomení zasáhne všechny najednou. K záloze patří rozumné rozmístění, označení použitého postupu a parametrů i zkouška obnovy na důvěryhodném zařízení. Má-li plán sloužit také dědicům, musí rozumět tomu, co hledají a jak s tím bezpečně zacházet. Nové náhodné rozdělení stejného tajemství S vytvoří novou sadu; staré a nové podíly se nemíchají. Dostatečná stará sada však S obnoví dál. Přerozdělení tedy není odvolání už uniklé použitelné zálohy ani změna samotného tajemství. [1] [4]

Při běžné obnově se celé tajemství znovu objeví v jednom zařízení. Pokud je zařízení napadené, může ho útočník získat právě v tomto okamžiku. Je-li tajemstvím Private Key, tedy tajný číselný údaj pro vytvoření digitálního podpisu schvalujícího útratu, jeho držitel pak může podepisovat bez dalších podílů. Multisig naproti tomu vyžaduje více podpisů podle podmínek konkrétního utracení. Existuje i prahové podepisování: s pomocí dalšího protokolu MPC, bezpečného společného výpočtu několika účastníků, mohou podíly přispět k podpisu bez sestavení celého klíče. NIST tyto situace rozlišuje. Samotný Shamirův podíl ale takový podpisový protokol nezavádí. [3] [5] [6]

Dva programy se slovem Shamir v názvu nemusejí umět přečíst podíly toho druhého. Pro obnovu musí souhlasit matematické operace, zápis hodnot, označení podílů i příslušnost k sadě. SLIP-39 je konkrétní standard, který na této metodě staví: přidává slovník pro zápis podílů, metadata neboli pomocné údaje, skupiny, šifrování a kontrolu chyb. Obecný princip proto není návod, jak ručně rozdělit existující Seed Phrase. Dříve než záloze svěříte peněženku, potřebujete znát podporovaný formát a ověřit, že ji zamýšlený postup skutečně obnoví. [2]

U schématu tři z pěti je jasné, co znamená ztratit dva podíly. Poškozený nebo podvržený podíl ale může základní výpočet dovést k jinému tajemství, místo aby oznámil nedostatek. Samotná metoda neověřuje původ podílů ani poctivost toho, kdo je vytvořil. Kontrola chyb, jejich oprava a verifiable secret sharing, postupy umožňující ověřovat správnost sdílení, jsou další vrstvy s vlastními předpoklady. SLIP-39 například přidává kontrolní součet a ověřovací otisk zvaný digest. Neznamená to, že každá aplikace používající Shamir Secret Sharing má stejné kontroly nebo že správný součet dokazuje důvěryhodný původ zálohy. [2] [5]

V ideálním schématu nedá útočníkovi méně než k úplných podílů žádnou novou informaci o tajemství S, ani s neomezeným výpočtem. Podíl tedy není viditelnou třetinou původních slov. Tato vlastnost ovšem předpokládá správnou náhodnost: čísla použitá při rozdělení jsou volena nezávisle a se stejnou pravděpodobností. Předvídatelná čísla, jejich opakované používání nebo únik z paměti zařízení mění situaci. Zvlášť se musí posuzovat i doplňkové kontrolní údaje, například digest ve SLIP-39. A slabé původní heslo nepřestane být uhodnutelné jinou cestou jen proto, že jsme jeho zálohu rozdělili. [1] [2]

Pro pochopení použijme malé tajemství S=5 a předpis f(x)=5+3*x mod 17. Značka mod 17 říká, že z výsledku bereme zbytek po dělení 17. Tři podíly jsou dvojice (1,8), (2,11), (3,14): první číslo označuje pozici, druhé vypočtenou hodnotu. Z prvních dvou zjistíme přírůstek 3 a původní tajemství 8−3=5. Stejnou pětku obnoví kterákoli ze tří možných dvojic. Samotný bod (1,8) přitom připouští každé S od 0 do 16, pokud se zvolí přírůstek a=8−S mod 17. Tohle malé počítání je pouze ilustrace, ne návrh zálohy pro skutečnou peněženku. [1]

Obecný předpis je f(x)=S+a1*x+…+a(k−1)*x^(k−1). Výrazu se říká polynom; S je tajemství a ostatní koeficienty jsou nezávislé, rovnoměrně náhodné prvky konečného tělesa, prostředí s přesnými pravidly sčítání a násobení. Podíl tvoří (x,f(x)), kde každé x musí být jiné a nenulové: x=0 by přímo odhalilo S. Z k bodů vypočte Lagrangeova interpolace hodnotu f(0), tedy tajemství. Dvě kopie stejného bodu novou informaci nepřidají. U prvočíselného tělesa GF(p) se místo běžného dělení používá násobení modulárním inverzním prvkem, jehož součin s dělitelem je 1. A GF(256) počítá jinak než prosté zbytky modulo 256; zaměnit tyto operace by bylo chybou. [1]