Shamirovo sdílení tajemství

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  • 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.