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

Matematikai definíció[szerkesztés]

A cél a adat olyan megosztása (például széf kódja) darab részre a következő módon:

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

Ez a séma a tűrés séma. Ha akkor minden birtokos szükséges a titok helyre állításához.

A Shamir-féle titokmegosztá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 pont definiáljon egy fokú polinomot.

A tűrés sémát szeretnénk az titok megosztásához használni, az általánosság elvesztése nélkül egy az véges mezőn.

Kiválasztva tetszőleges együtthatót in , és legyen . Állítsuk elő a az polinomot. Határozzuk meg bármelyik pontját, ahol a bemenet to retrieve . Minden titokbirtokos kap egy pontot (egy bemenő értéket és az arra a polinommal kiszámolt értéket). Bármilyen részhalmaza ezen pároknak, meghatározza az együtthatóit a görbeillesztésnek és titok az 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 Shamir-féle sémának.

Szétosztás[szerkesztés]

Legyen a titkunk 1234 .

Fel szeretnénk bontani 6 részre , ahol 3 rész elég a titok helyre állításhoz.
(Az meghatározza, hogy 6 pontot kell kiszámolnunk és szétosztanunk, míg a meghatározza, hogy az egyenlet fokú lesz, és hogy 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 polinomunk ami a titokrészeket létrehozza (a pontokat) a következő:

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

Minden birtokos kap egy pontot (az és értékeket is).

Összeállítás[szerkesztés]

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

Legyenek ezek a pontok .

Határozzuk meg a Lagrange polinomokat:

A Lagrange polinomok meghatározása a következő:

azaz produktumot kell számítani (össze kell szorozni) a tagokat egymással, ahol azt a tagot, ahol ki kell hagyni mert az osztás egyébként is értelmetlen lenne.

Behelyettesítve a fentibe estekben a következőt kapjuk:

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

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

Tulajdonságok[szerkesztés]

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