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 $k$ rész elég a titok helyreállításhoz.

Matematikai definíció

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

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

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

A Shamir-féle titokmegosztási séma

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 $k\,\!$ pont definiáljon egy $k-1\,\!$ fokú polinomot.

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

Kiválasztva $k-1\,\!$ tetszőleges együtthatót $a_{1},\cdots ,a_{k-1}\,\!$ in $F$, és legyen $a_{0}=S\,\!$. Állítsuk elő a az $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 $n\,\!$ pontját, ahol a bemenet $i=1,\cdots ,n\,\!$ to retrieve $\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 $k\,\!$ pároknak, meghatározza az együtthatóit a görbeillesztésnek és titok az $a_{0}\,\!$ konstans rész.

Használat

Példa

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.

Szétosztás

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

Fel szeretnénk bontani 6 részre $(n=6)\,\!$, ahol 3 rész $(k=3)\,\!$ elég a titok helyre állításhoz.
(Az $(n=6)\,\!$ meghatározza, hogy 6 pontot kell kiszámolnunk és szétosztanunk, míg a $(k=3)\,\!$ meghatározza, hogy az egyenlet $(k-1=2)\,\!$ fokú lesz, és hogy $(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.

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

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

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

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

$\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 $x\,\!$ és $f\left(x\right)\,\!$ értékeket is).

Összeállítás

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

Legyenek ezek a pontok $\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ő: $\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 ${\frac {(x-x_{f})}{(x_{j}-x_{f})}}$ tagokat egymással, ahol azt a tagot, ahol $f=j$ ki kell hagyni mert az osztás egyébként is értelmetlen lenne.

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

$\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}}\,\!$

$\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\,\!$

$\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ő,

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

$=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)\,\!$

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

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

Tulajdonságok

Néhány hasznos tulajdonsága a Shamir-féle $\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 $k\,\!$ fix marad, akkor $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.

Lásd még

• titokmegosztás
• Lagrange polinom

Források

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

További információk

• 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