Shamir-féle titokmegosztás

A Wikipédiából, a szabad enciklopédiából

A Shamir-féle titokmegosztás egy kriptográfiai algoritmus. Ennél a fajta titok megosztá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.

Tartalomjegyzék

Matematikai definíció [szerkesztés]

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 titok megosztási séma [szerkesztés]

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 elvesztése nélkül egy 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_1x+a_2x^2+a_3x^3+\cdots+a_{k-1}x^{k-1}\,\! polinomot. Határozzuk meg bármelyik n\,\! poontjá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 [szerkesztés]

Példa [szerkesztés]

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 a Shamir-féle sémának.

Szétosztás [szerkeszté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 [szerkeszté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\le f\le 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 RS=1234\,\!, és a visszaállítás megtörtént.

Tulajdonságok [szerkesztés]

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 [szerkesztés]

Források [szerkesztés]

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 [szerkesztés]

A lap eredeti címe: „http://hu.wikipedia.org/w/index.php?title=Shamir-féle_titokmegosztás&oldid=13275286”