Egy titok megosztása

A titkos megosztás egy olyan kifejezés a kriptográfiában , amely alatt a titok elosztásának bármely módszerét értjük a résztvevők csoportja között, amelyek mindegyike megkapja a saját bizonyos részesedését. A titkot csak az eredeti csoport résztvevőiből álló koalíció teremtheti újra, és közülük legalább néhány, kezdetben ismert számot be kell vonni a koalícióba.

A titkos megosztási sémákat olyan esetekben alkalmazzák, amikor jelentős a valószínűsége egy vagy több titkos őrző kompromittálásának , de a résztvevők jelentős része tisztességtelen összejátszásának valószínűsége elhanyagolható.

A meglévő rendszereknek két összetevője van: a titkos megosztás és a titkos helyreállítás. A megosztás a titok részeinek kialakítását és azok elosztását jelenti a csoport tagjai között, ami lehetővé teszi a titokért való felelősség megosztását a csoport tagjai között. Az inverz sémának biztosítania kell annak helyreállítását, feltéve, hogy a fenntartói egy bizonyos számban rendelkezésre állnak [1] .

Használati eset: Titkos megosztáson alapuló titkos szavazási protokoll [2] .

A titkos megosztási séma legegyszerűbb példája

Legyen egy embercsoport és egy hosszú üzenet , amely bináris karakterekből áll. Ha véletlenszerűen olyan bináris üzeneteket vesz fel , amelyek összességében megegyeznek a -val , és elosztja ezeket az üzeneteket a csoport összes tagja között, akkor kiderül, hogy csak akkor lehet elolvasni az üzenetet, ha a csoport összes tagja összejön [1] . $t$ $s$ $n$ ${\displaystyle s_{1},\ldots ,s_{t))$ $s$

Egy ilyen sémában van egy jelentős probléma: a csoport legalább egy tagjának elvesztése esetén a titok az egész csoport számára helyrehozhatatlanul elveszik.

Küszöb séma

Ellentétben a titkos felosztási eljárással, ahol a titkos felosztási eljárásban a titok visszaállításához szükséges megosztások száma eltérhet attól, hogy a titok hány megosztásra van felosztva. Az ilyen sémát küszöbsémának nevezik , ahol a megosztások száma, amelyekre a titkot felosztották, és a titok visszaállításához szükséges megosztások száma. Az áramköri ötleteket 1979-ben egymástól függetlenül Adi Shamir és George Blakley javasolta . Ezenkívül hasonló eljárásokat tanulmányozott Gus Simmons [3] [4] [5] . $t=n$ $\left(t, n\jobb)$ $n$ $t$ $t \neq n$

Ha a résztvevők koalíciója olyan, hogy elegendő részesedéssel rendelkeznek a titok helyreállításához, akkor a koalíciót megoldottnak nevezik. Tökéletesnek nevezzük azokat a titkos megosztási sémákat, amelyekben a résztvevők engedélyezett koalíciói egyedileg visszaszerezhetik a titkot, a fel nem oldottak pedig nem kapnak utólag információt a titok lehetséges értékéről [6] .

Shamir séma

A diagram lényege, hogy két pont elég egy egyenes meghatározásához , három pont elegendő egy parabola meghatározásához , négy pont elég egy köbös parabola meghatározásához , és így tovább. Fokozatú polinom megadásához pontok szükségesek . $k$ $k+1$

Annak érdekében, hogy a titkot az elválasztás után csak a résztvevők állíthassák helyre , egy véges mező feletti fokpolinom képletében „rejtve” van . Ennek a polinomnak az egyedi visszaállításához ismerni kell az értékeket a pontokban, és kisebb számú pont használatával nem lehet egyedileg visszaállítani az eredeti polinomot. A polinom különböző pontjainak száma nincs korlátozva (a gyakorlatban annak a numerikus mezőnek a mérete korlátozza , amelyben a számításokat végezzük). $k$ $(k-1)$ $G$ $k$ $G$

Ez az algoritmus röviden a következőképpen írható le. Legyen adott egy véges mező . Ennek a mezőnek a különböző, nullától eltérő, nem titkos elemeit javítjuk . Ezen elemek mindegyike a csoport egy-egy tagjához van rendelve. Ezután a mező egy tetszőleges elemkészletét választjuk ki , amelyből egy fokszámmező feletti polinom épül . A polinom megszerzése után a nem titkos pontokon kiszámítjuk az értékét, és az eredményeket jelentjük a csoport megfelelő tagjainak [1] . $G$ $n$ $t$ $G$ $f(x)$ $G$ $t-1,1<t\leq n$

A titok helyreállításához használhat interpolációs képletet, például a Lagrange -képletet .

A Shamir séma fontos előnye, hogy könnyen méretezhető [5] . Egy csoport felhasználói számának növeléséhez csak a megfelelő számú nem titkos elemet kell hozzáadni a meglévőkhöz, és a feltételnek teljesülnie kell . Ugyanakkor a titok egy részének kompromittálódása megváltoztatja a sémát -threshold-ról -threshold-ra. ${\displaystyle r_{i}\neq r_{j))$ $i\neq j$ ${\megjelenítési stílus (n,t)}$ ${\megjelenítési stílus (n-1,t-1)}$

Blackley séma

Egy síkban két nem párhuzamos egyenes metszi egymást egy pontban. Bármely két nem egysíkú sík egy egyenesben metszi egymást, és a térben három nem egysíkú sík is egy pontban metszi egymást. Általában n n - dimenziós hipersík mindig egy pontban metszi egymást. Ennek a pontnak az egyik koordinátája titok lesz. Ha a titkot egy pont több koordinátájaként kódoljuk, akkor már a titok egy részéből (egy hipersíkból) lehet információt szerezni a titokról, vagyis a metszéspont koordinátáinak kölcsönös függéséről.


Blackley séma három dimenzióban: a titok minden része egy sík , a titok pedig a síkok metszéspontjának egyik koordinátája. Két sík nem elég a metszéspont meghatározásához.

Blackley séma [4] segítségével létrehozhat egy (t, n) -titkos megosztási sémát bármely t és n értékűre: ehhez a t -vel egyenlő térdimenziót kell használni , és meg kell adni mind az n játékost . egy hipersík, amely áthalad a titkos ponton. Ekkor n hipersík közül bármelyik t egyedileg metszi egymást egy titkos pontban.

Blackley séma kevésbé hatékony, mint Shamir séma: Shamir sémájában minden részvény akkora, mint a titok, míg Blackley rendszerében minden részvény t - szer nagyobb. Fejlesztések történtek Blakely rendszerében a hatékonyság javítása érdekében.

A kínai maradéktételen alapuló sémák

1983-ban Maurice Mignotte , Asmuth és Bloom két titkos megosztási sémát javasolt a kínai maradék tételen alapulóan . Egy bizonyos számra ( a Mignotte sémában ez maga a titok, az Asmuth-Bloom sémában valamilyen származékos szám) a maradékokat számsorral való elosztás után számítjuk ki, amit szétosztunk a felek között. A számsor korlátozása miatt csak bizonyos számú fél tudja visszaállítani a titkot [7] [8] .

Legyen a csoportban lévő felhasználók száma . A Mignotte-sémában a páronkénti koprímszámok egy bizonyos halmazát úgy választják meg , hogy a legnagyobb számok szorzata kisebb, mint a legkisebb számok szorzata. Legyenek ezek a termékek egyenlőek és . A számot a halmaz feletti összeállított séma küszöbének nevezzük . Titokként olyan számot választanak ki , hogy az összefüggés teljesüljön . A titok részei a következőképpen oszlanak meg a csoport tagjai között: minden tag kap egy számpárt , ahol . $n$ ${\displaystyle \{m_{1},m_{2},...,m_{n}\))$ $k-1$ $k$ $M$ $N$ $k$ ${\displaystyle \{m_{1},m_{2},...,m_{n}\))$ $S$ $M<S<N$ $(r_{i},m_{i})$ ${\displaystyle r_{i}\equiv S{\pmod {m_{i))))$

A titok helyreállításához össze kell olvasztani a töredékeket. Ebben az esetben a forma összehasonlítási rendszerét kapjuk , amelynek megoldási halmazát a kínai maradéktétel segítségével találhatjuk meg . A titkos szám ehhez a halmazhoz tartozik, és megfelel a feltételnek . Az is könnyen kimutatható, hogy ha a töredékek száma kisebb, mint , akkor a titok megtalálásához az egész számok sorrendjét kell rendezni . A számok helyes megválasztásával egy ilyen keresést szinte lehetetlen megvalósítani. Például, ha a bitmélység 129 és 130 bit között van, és , akkor az arány [9] nagyságrendű lesz . $t\geq k$ ${\displaystyle x\equiv r_{i}{\pmod {m_{i))))$ $S$ ${\displaystyle S<m_{1}\cdot m_{2}\cdot ...\cdot m_{t))$ $k$ $S$ ${\frac {N}{M}}$ $m_i$ $m_i$ $k<15$ ${\frac {N}{M}}$ $2^{100}$

Az Asmuth-Bloom séma egy módosított Mignott-séma. A Mignotte-sémától eltérően úgy is megszerkeszthető, hogy tökéletes legyen [10] .

Egyenletrendszerek megoldásán alapuló sémák

1983-ban Karnin, Green és Hellman javasolta titkos megosztási sémájukat , amely azon alapult, hogy egy ismeretlen rendszert kevesebb egyenlettel megoldani lehetetlen [11] . $m$ $m$

A séma keretein belül a -dimenziós vektorokat úgy választjuk meg, hogy az ezekből a vektorokból álló méretű mátrixok rangja legyen . Legyen a vektor dimenziója . $n+1$ $m$ ${\displaystyle V_{0},V_{1},...,V_{n))$ $m\times m$ $m$ $U$ $m$

Az áramkör titka a mátrixszorzat . A titok megosztásai művek . $U^{T}V_{0}$ $U^{T}V_{i},1\leq i\leq n$

Bármilyen megosztással létre lehet hozni egy dimenziós lineáris egyenletrendszert , amelyben az együtthatók ismeretlenek . Ennek a rendszernek a megoldásával megtalálhatja , és birtokában megtalálhatja a titkot. Ebben az esetben az egyenletrendszernek nincs megoldása, ha a részesedések kisebbek, mint [12] . $m$ $m\times m$ $U$ $U$ $U$ $m$

A küszöbrendszer megtévesztésének módjai

Számos módja van a küszöbáramkör protokolljának megszakítására:

az egyik részvény tulajdonosa a hibás (véletlen) részesedés megfelelő időben történő átadásával beavatkozhat a megosztott titok helyreállításába [13] .
a titok visszaszerzésénél jelen lehet egy támadó, aki nem rendelkezik részesedéssel. Miután megvárta a szükséges megosztási szám bejelentését, gyorsan visszaállítja a titkot, és generál egy másik megosztást, majd bemutatja a többi résztvevőnek. Ennek eredményeként hozzáfér a titokhoz, és csapdák nélkül marad [14] .

Vannak más zavarási lehetőségek is, amelyek nem kapcsolódnak a rendszer végrehajtásához:

a támadó szimulálhat egy olyan szituációt, amelyben egy titok felfedése szükséges, ezáltal megtudhatja a résztvevők részesedését [14] .

Lásd még

Jegyzetek

↑ 1 2 3 Alferov, Zubov, Kuzmin et al., 2002 , p. 401.
↑ Schoenmakers, 1999 .
↑ CJ Simmons. Bevezetés a megosztott titkos és/vagy megosztott vezérlési sémákba és azok alkalmazásába // Contemporary Cryptology. - IEEE Press, 1991. - P. 441-497 .
↑ Blakley 12. , 1979 .
↑ 12 Shamir , 1979 .
↑ Blackley, Kabatiansky, 1997 .
↑ Mignotte, 1982 .
↑ Asmuth, Bloom, 1983 .
↑ Moldovyan, Moldovyan, 2005 , p. 225.
↑ Shenets, 2011 .
↑ Karnin, Greene, Hellman, 1983 .
↑ Schneier B. Alkalmazott kriptográfia. - 2. kiadás - Triumph, 2002. - S. 590. - 816 p. - ISBN 5-89392-055-4 .
↑ Pasailă, Alexa, Iftene, 2010 .
↑ 1 2 Schneier, 2002 , p. 69.

Irodalom

Schneier B. 3.7. Titkos megosztás // Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód: C. - M . : Triumph, 2002. - S. 93-96. — 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .
Schneier B. 23.2 Titkos megosztási algoritmusok // Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód: C. - M . : Triumf, 2002. - S. 588-591. — 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .

Blakley G. R. Safeguarding cryptographic keys (angol) // Proceedings of the 1979 AFIPS National Computer Conference - Montvale : AFIPS Press , 1979. - P. 313-317. doi : 10.1109/AFIPS.1979.98
Shamir A. Hogyan osszunk meg egy titkot // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Vol. 22, Iss. 11. - P. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
Mignotte M. Hogyan osszunk meg egy titkot (angol) // Kriptográfia : Proceedings of the Workshop on Cryptography Burg Feuerstein, Németország, 1982. március 29–április 2. / T. Beth – Berlin , Heidelberg , New York, NY , London [ stb . .] : Springer Berlin Heidelberg , 1983. - P. 371-375. - ( Számítástechnikai előadások jegyzetei ; 149. kötet) - ISBN 978-3-540-11993-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-39466-4_27
Asmuth C. , Bloom J. A kulcsok védelmének moduláris megközelítése // IEEE Trans . inf. Elmélet / F. Kschischang - IEEE , 1983. - 1. kötet. 29, Iss. 2. - P. 208-210. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056651
Karnin E. D. , Greene J. W. , Hellman M. E. A titkos megosztási rendszerekről // IEEE Trans . inf. Elmélet / F. Kschischang - IEEE , 1983. - 1. kötet. 29, Iss. 1. - P. 35-41. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056621
Blackley D. , Kabatyansky G. A. Általánosított ideális sémák, amelyeknek közös a titka és a matroidok // Probl. információ továbbítása - 1997. - T. 33. sz. 3. - S. 102-110.
Schoenmakers B. Egy egyszerű nyilvánosan ellenőrizhető titkos megosztási rendszer és alkalmazása az elektronikus szavazásra // Advances in Cryptology — CRYPTO' 99 :19th Annual International Cryptology Conference Santa Barbara, California, USA, 1999. augusztus 15–19. Proceedings / M. Wiener - Springer Berlin Heidelberg , 1999. - P. 148-164. — ISBN 978-3-540-66347-8 — doi:10.1007/3-540-48405-1_10
Alferov A. P. , Zubov A. Yu. , Kuzmin A. S. , Cheremushkin A. V. A kriptográfia alapjai : Tankönyv - 2. kiadás, Rev. és további - M .: Helios ARV , 2002. - ISBN 978-5-85438-137-6
Moldovyan N. A. , Moldovyan A. A. Bevezetés a nyilvános kulcsú kriptorendszerekbe - Szentpétervár. : BHV-Petersburg , 2005. - 288 p. - ( Oktatóanyag ) - ISBN 978-5-94157-563-3
Pasailă D. , Alexa V. , Iftene S. Csalásészlelés és csalók azonosítása CRT-alapú titkos megosztási sémákban (angol) // International Journal of Computing - 2010. - Vol. 9, Iss. 2. - P. 107-117. — ISSN 2312-5381 ; 1727-6209
Shenets N. N. Az ideális moduláris titkos megosztási sémákról polinomiális gyűrűkben több változóban // International Congress on Informatics: Information Systems and Technologies : materials of the International Scientific Congress 31 Oct. - Minsk : BGU , 2011. - V. 1. Az Alkalmazott Matematikai és Informatikai Kar cikkei. - S. 169-173. — ISBN 978-985-518-563-6