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,\dots ,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 $(k,n)$ 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 $(k,n)$ 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 $(i,f\left(i\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ő:

$(1,1494);(2,1942);(3,2578);(4,3402);(5,4414);(6,5614)$

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 $(x_0,y_0)=(2,1942);(x_1,y_1)=(4,3402);(x_2,y_2)=(5,4414)$.

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\ne 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 (\frac{1}{6}{x}^2-1\frac{1}{2}x+3\frac{1}{3})+3402\cdot (-\frac{1}{2}{x}^2+3\frac{1}{2}x-5)+4414\cdot (\frac{1}{3}{x}^2-2x+2\frac{2}{3})$

$=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 $(k,n)$ 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

• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.

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