Šamirovo sdílení tajemství

Šamirovo schéma pro sdílení tajemství je kryptografický algoritmus. Je to forma sdílení tajné informace, kdy je tato informace rozdělena do částí (každému účastníku je přidělena jedinečná část) a pro rekonstrukci původní informace je třeba alespoň určitý počet z dílčích částí. Izraelský matematik Adi Šamir jej formuloval v roce 1979

Matematická definice

Našim cílem je rozdělit nějaká data $D$ do $n\,\!$ částí $D_{1},\ldots ,D_{n}\,\!$ tak, že:

Znalost některých $k\,\!$ nebo více $D_{i}\,\!$ částí zajistí snadné zjištění $D\,\!$ .
Znalost některých $k-1\,\!$ nebo méně $D_{i}\,\!$ částí ponechá $D\,\!$ zcela neurčená (ve smyslu, že všechny hodnoty jsou stejně možné).

Toto schéma nazýváme $\left(k,n\right)\,\!$ prahové schéma. Pokud $k=n\,\!$ , všichni účastníci jsou třeba k rekonstrukci tajemství.

Shamirovo schéma

Předpokládejme, že chceme užít $\left(k,n\right)\,\!$ prahové schéma pro sdílení tajemství $S\!$ . Bez újmy na obecnosti předpokládejme, že $S\!$ je prvkem konečného tělesa $F\!$ velikosti $P$ kde $0<k\leq n<P;S<P$ a zároveň je $P$ prvočíslo.

Náhodně vybereme $k-1\!$ koeficientů $a_{1},\ldots ,a_{k-1}\in F\!$ . Dále $a_{0}=S.\!$ Sestavíme polynom $f\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{k-1}x^{k-1}\,\!$ . Dále vypočítáme souřadnice $n\,\!$ bodů tohoto polynomu. Například pro $i=1,\ldots ,n\!$ získáme $n\!$ bodů ve tvaru $\left[i,f\left(i\right)\right].\!$

Tyto souřadnice jsou rozděleny mezi $n,\!$ účastníků. Jelikož je polynom stupně $k-1\!$ určen jednoznačně $k\!$ body, z jakékoliv $k\!$ -prvkové podmnožiny bodů lze jednoznačně pomocí interpolace určit koeficienty polynomu $f,\!$ a tedy i tajemství $S=a_{0}.\!$

Reference

SHAMIR, Adi. How to share a secret. Communications of the ACM. 1979, roč. 22, čís. 11, s. 612–613.

V tomto článku byl použit překlad textu z článku Shamir's Secret Sharing na anglické Wikipedii.