Shamir-féle titokmegosztás

A Shamir-féle titokmegosztás egy kriptográfiai algoritmus. Ennél a fajta titokmegosztásnál a titok részekre van osztva, úgy, hogy minden titokbirtokosnak különböző rész van a birtokában, és ahol az eredeti titok helyreállításhoz néhány vagy az összes titokrész szükséges.

Bármilyen titok helyreállítása során nem praktikus, ha az összes résztvevő szükséges a helyreállításhoz, ezért a tűréshatár megoldást alkalmazzuk, ahol ${\displaystyle k}$ rész elég a titok helyreállításhoz.

A cél a ${\displaystyle D}$ adat olyan megosztása (például széf kódja) ${\displaystyle n\,\!}$ darab részre ${\displaystyle D_{1},\ldots ,D_{n}\,\!}$ a következő módon:

1. ${\displaystyle k\,\!}$ vagy több ${\displaystyle D_{i}\,\!}$ rész ismerete esetén ${\displaystyle D\,\!}$ könnyen kiszámolható.
2. ${\displaystyle k-1\,\!}$ vagy kevesebb ${\displaystyle D_{i}\,\!}$ rész ismerete esetén ${\displaystyle D\,\!}$ nem meghatározható. (abban az értelemben, hogy minden lehetséges értéket felvehet).

Ez a séma a ${\displaystyle \left(k,n\right)\,\!}$ tűrés séma. Ha ${\displaystyle k=n\,\!}$ akkor minden birtokos szükséges a titok helyreállításához.

Adi Shamirtól származik az alapötlet, hogy definiálható 2 ponttal egy vonal, 3-mal egy parabola és 4 ponttal egy négyzetes görbe, ... Ez az ami lehetővé teszi, hogy ${\displaystyle k\,\!}$ pont definiáljon egy ${\displaystyle k-1\,\!}$ fokú polinomot.

A ${\displaystyle \left(k,n\right)\,\!}$ tűrés sémát szeretnénk az ${\displaystyle S\,\!}$ titok megosztásához használni az általánosság megszorítása nélkül az ${\displaystyle F}$ véges mezőn.

Kiválasztva ${\displaystyle k-1\,\!}$ tetszőleges együtthatót ${\displaystyle a_{1},\cdots ,a_{k-1}\,\!}$ in ${\displaystyle F}$, és legyen ${\displaystyle a_{0}=S\,\!}$. Állítsuk elő a az ${\displaystyle f\left(x\right)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{k-1}x^{k-1}\,\!}$ polinomot. Határozzuk meg bármelyik ${\displaystyle n\,\!}$ pontját, ahol a bemenet ${\displaystyle i=1,\cdots ,n\,\!}$ to retrieve ${\displaystyle \left(i,f\left(i\right)\right)\,\!}$. Minden titokbirtokos kap egy pontot (egy bemenő értéket és az arra a polinommal kiszámolt értéket). Bármilyen részhalmaza ezen ${\displaystyle k\,\!}$ pároknak, meghatározza az együtthatóit a görbeillesztésnek és titok az ${\displaystyle a_{0}\,\!}$ konstans rész.

Az alábbi példa illusztrálja az alapötletet. Megjegyzendő, hogy a számítások integer számítások a véges mező aritmetika helyett. Ezért a példa lenn nem ad tökéletes biztonságot és nem a teljes valós példája a Shamir-féle sémának.

Legyen a titkunk 1234 ${\displaystyle (S=1234)\,\!}$.

Fel szeretnénk bontani 6 részre ${\displaystyle (n=6)\,\!}$, ahol 3 rész ${\displaystyle (k=3)\,\!}$ elég a titok helyre állításhoz.
(Az ${\displaystyle (n=6)\,\!}$ meghatározza, hogy 6 pontot kell kiszámolnunk és szétosztanunk, míg a ${\displaystyle (k=3)\,\!}$ meghatározza, hogy az egyenlet ${\displaystyle (k-1=2)\,\!}$ fokú lesz, és hogy ${\displaystyle (k-1=2)\,\!}$ tetszőlegesen választott számra van szükségünk.)
A példában véletlennek a következő 2 számot válasszuk: 166, 94.

${\displaystyle (a_{1}=166;a_{2}=94)\,\!}$

A polinomunk ami a titokrészeket létrehozza (a pontokat) a következő:

${\displaystyle f\left(x\right)=1234+166x+94x^{2}\,\!}$

A létrehozott 6 pont a következő:

${\displaystyle \left(1,1494\right);\left(2,1942\right);\left(3,2578\right);\left(4,3402\right);\left(5,4414\right);\left(6,5614\right)\,\!}$

Minden birtokos kap egy pontot (az ${\displaystyle x\,\!}$ és ${\displaystyle f\left(x\right)\,\!}$ értékeket is).

Az összeállításhoz 3 pont már elég.

Legyenek ezek a pontok ${\displaystyle \left(x_{0},y_{0}\right)=\left(2,1942\right);\left(x_{1},y_{1}\right)=\left(4,3402\right);\left(x_{2},y_{2}\right)=\left(5,4414\right)\,\!}$.

Határozzuk meg a Lagrange polinomokat:

A Lagrange polinomok meghatározása a következő: ${\displaystyle \ell _{j}(x):=\prod _{{\begin{array}{c}0\leq f\leq k\\f\neq j\end{array}},}\left({\frac {x-x_{f}}{x_{j}-x_{f}}}\right)={\frac {(x-x_{0})}{(x_{j}-x_{0})}}\cdots {\frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{\frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}\cdots {\frac {(x-x_{k})}{(x_{j}-x_{k})}}.}$

azaz produktumot kell számítani (össze kell szorozni) a ${\displaystyle {\frac {(x-x_{f})}{(x_{j}-x_{f})}}}$ tagokat egymással, ahol azt a tagot, ahol ${\displaystyle f=j}$ ki kell hagyni mert az osztás egyébként is értelmetlen lenne.

Behelyettesítve a fentibe ${\displaystyle j=0,1,2}$ estekben a következőt kapjuk:

${\displaystyle \ell _{0}={\frac {x-x_{1}}{x_{0}-x_{1}}}\cdot {\frac {x-x_{2}}{x_{0}-x_{2}}}={\frac {x-4}{2-4}}\cdot {\frac {x-5}{2-5}}={\frac {1}{6}}x^{2}-1{\frac {1}{2}}x+3{\frac {1}{3}}\,\!}$

${\displaystyle \ell _{1}={\frac {x-x_{0}}{x_{1}-x_{0}}}\cdot {\frac {x-x_{2}}{x_{1}-x_{2}}}={\frac {x-2}{4-2}}\cdot {\frac {x-5}{4-5}}=-{\frac {1}{2}}x^{2}+3{\frac {1}{2}}x-5\,\!}$

${\displaystyle \ell _{2}={\frac {x-x_{0}}{x_{2}-x_{0}}}\cdot {\frac {x-x_{1}}{x_{2}-x_{1}}}={\frac {x-2}{5-2}}\cdot {\frac {x-4}{5-4}}={\frac {1}{3}}x^{2}-2x+2{\frac {2}{3}}\,\!}$

Mivel az interpolációs polinom a következő,

${\displaystyle f(x)=\sum _{j=0}^{2}y_{j}\cdot \ell _{j}(x)\,\!}$

${\displaystyle =1942\cdot \left({\frac {1}{6}}x^{2}-1{\frac {1}{2}}x+3{\frac {1}{3}}\right)+3402\cdot \left(-{\frac {1}{2}}x^{2}+3{\frac {1}{2}}x-5\right)+4414\cdot \left({\frac {1}{3}}x^{2}-2x+2{\frac {2}{3}}\right)\,\!}$

${\displaystyle =1234+166x+94x^{2}\,\!}$

Látható, hogy a titok a szabad együttható , azaz R${\displaystyle S=1234\,\!}$, és a visszaállítás megtörtént.

Néhány hasznos tulajdonsága a Shamir-féle ${\displaystyle \left(k,n\right)\,\!}$ tűréshatár sémának:

1. Biztonságos
2. Kicsi: A mérete az egyes részeknek nem nagyobb a titoknál.
3. Bővíthető: Ha ${\displaystyle k\,\!}$ fix marad, akkor ${\displaystyle D_{i}\,\!}$ részek dinamikusan adhatók és levehetők, anélkül, hogy a többi részt érintené.
4. Dinamikus: A titok változtatása nélkül növelhető a biztonság, a növelve a polinom fokát, és új részeket adva a birtokosoknak.
5. Igazítható: Azon szervezetekben ahol a hierarchia fontos, lehetőség van egyes emberek számára különböző mennyiségű részek átadására a betöltött fontosságnak megfelelően Például lehetséges, hogy az elnök egyedül ki tudja nyitni a széfet, de 3 titkár kell ugyanerre a feladatra.

• titokmegosztás
• Lagrange polinom

• Shamir, Adi (1979), "How to share a secret", Communications of the ACM 22 (11): 612–613, DOI 10.1145/359168.359176.
• Liu, C. L. (1968), Introduction to Combinatorial Mathematics, New York: McGraw-Hill.
• Dawson, E. & Donovan, D. (1994), "The breadth of Shamir's secret-sharing scheme", Computers & Security 13: 69–78, DOI 10.1016/0167-4048(94)90097-3.
• Knuth, D. E. (1997), The Art of Computer Programming, vol. II: Seminumerical Algorithms (3rd ed.), Addison-Wesley, p. 505.

• ssss: Ingyenes (GPL) megvalósítása a Shamir-féle sémának és online demo
• A Shamir-féle titokmegosztás Perl megvalósítása
• Secret Sharp: Ingyenes (GPL) megvalósítása a Shamir sémának Windows rendszerre
• Christophe David web alapú megvalósítása a Shamir 'How to share a Secret' sémájának
• Shamir-féle titokmegosztás Java nyelven: Ingyenes (LGPL) megvalósítása a Shamir-féle sémának Java nyelven