Š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,\dots ,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 $(k,n)$ 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 $(k,n)$ 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\le n<P;S<P$ a zároveň je $P$ prvočíslo.

Náhodně vybereme $k-1$ koeficientů $a_1,\dots ,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,\dots ,n$ získáme $n$ bodů ve tvaru $[i,f\left(i\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

• Šablona:Citace periodika