Shamirovo sdílení tajemství

Shamirovo 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í.

Matematická definice

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

1. Znalost některých $k\,\!$ nebo více $D_i\,\!$ částí zajistí snadné zjištění $D\,\!$ .
2. 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.\!$

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_1x+a_2x^2+a_3x^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.