Shamirin salainen jakamisjärjestelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. lokakuuta 2018 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Lagrangen interpolaatiopolynomijärjestelmä ( Shamir- salaisuusjärjestelmä tai Shamir - malli ) on salaustekniikassa laajalti käytetty salainen jakamismenetelmä . Shamirin järjestelmä mahdollistaa salaisen viestin (salaisuus) jakamisen kynnyksen osapuolten kesken siten, että vain yksi tai useampi osapuoli ( ≤ ) voi palauttaa salaisuuden. Tässä tapauksessa kaikki osapuolet eivät pysty palauttamaan salaisuutta. $(k,n)$ $n$ $k$ $k$ $n$ $k-1$

Historia

Vuonna 1979 israelilainen kryptanalyytikko Adi Shamir ehdotti kynnysjärjestelmää salaisuuden jakamiseksi osapuolten välillä, mikä mahdollistaa jakamisen siten, että [1] : $n$

Salaisuuden palauttamiseksi riittää useampi kuin yksi puoli. $k$
Yksikään ja harvempi osapuoli voi saada mitään tietoa salaisuudesta. ${\näyttötyyli (k-1)}$

Idea

Pisteitä tarvitaan astepolynomin interpoloimiseen . Esimerkiksi kaksi pistettä riittää määrittämään suoran , kolme pistettä riittää määrittelemään paraabelin ja niin edelleen. $k-1$ $k$

Tämän järjestelmän pääideana on, että interpolointi on mahdotonta , jos tunnetaan pienempi määrä pisteitä [1] .

Jos haluamme jakaa salaisuuden ihmisten kesken siten, että vain henkilö ( ≤ ) voi palauttaa sen, "piilotamme" sen astepolynomikaavassa . Tämä polynomi ja alkuperäinen salaisuus on mahdollista palauttaa vain pisteillä. Polynomin eri pisteiden määrää ei ole rajoitettu (käytännössä sitä rajoittaa sen numeerisen kentän koko, jossa laskutoimitukset suoritetaan) [2] . $n$ $k$ $k$ $n$ $k-1$ $k$

Kuvaus

Valmisteluvaihe

Olkoon salaisuus jaettava osapuolten kesken siten, että kuka tahansa osallistuja voisi palauttaa salaisuuden (eli on tarpeen toteuttaa - kynnysjärjestelmä ). $M$ $n$ $k$ $(k,n)$

Valitaan jokin alkuluku . Tämä numero voidaan ilmoittaa avoimesti kaikille osallistujille. Se määrittää lopullisen kokokentän . Rakennamme tämän kentän päälle astepolynomin (eli valitsemme satunnaisesti kaikki polynomin kertoimet paitsi ) [3] : $p>M$ $s$ $k-1$ $M$

F\left(x\right)=\left(a_{k-1}x^{k-1}+a_{k-2}x^{k-2}+\pisteet +a_{1} x+M\oikea)\mod p

Tässä polynomissa tämä on jaettu salaisuus, ja loput kertoimet ovat joitain satunnaislukuja, jotka on "unohdettava" salaisuuden jakamismenettelyn päätyttyä [3] . $M$ ${\displaystyle a_{k-1},a_{k-2},\dots ,a_{1))$

Salaisten osuuksien luominen

Nyt laskemme "osuudet" - yllä rakennetun polynomin arvot eri kohdissa ja ≠ [3] : $n$ ${\näyttötyyli (x}$ ${\näyttötyyli 0)}$

{\begin{aligned}k_{1}&=&F\left(1\right)&=&\left(a_{k-1}\cdot 1^{k-1}+a_{k-2 }\cdot 1^{k-2}+\dots +a_{1}\cdot 1+M\right)&\mod p\\k_{2}&=&F\left(2\right)&=&\ vasen(a_{k-1}\cpiste 2^{k-1}+a_{k-2}\cpiste 2^{k-2}+\pisteet +a_{1}\cpiste 2+M\oikea)& \mod p\\&&\dots \\k_{i}&=&F\left(i\right)&=&\left(a_{k-1}\cdot i^{k-1}+a_{k- 2}\cdot i^{k-2}+\dots +a_{1}\cdot i+M\right)&\mod p\\&&\dots \\k_{n}&=&F\left(n\ oikea)&=&\left(a_{k-1}\cpiste n^{k-1}+a_{k-2}\cpiste n^{k-2}+\pisteet +a_{1}\cpiste n +M\oikea)&\mod p\\\end{tasattu}}

Polynomin argumenttien (salaisuuksien lukumäärät) ei tarvitse olla järjestyksessä, pääasia, että ne kaikki ovat erilaisia modulo :ssa . $s$

Tämän jälkeen kukin salaisuuden jakamiseen osallistuva osapuoli saa osuuden salaisuudesta numeron kanssa . Lisäksi kaikille osapuolille ilmoitetaan polynomin aste ja kentän koko . Satunnaiset kertoimet ja itse salaisuus "unohdetaan" [3] . ${\displaystyle k_{i))$ $i$ $k-1$ $s$ ${\displaystyle a_{k-1},a_{k-2},\dots ,a_{1))$ $M$

Salaisuuden palauttaminen

Nyt kaikki osallistujat, jotka tietävät polynomin eri pisteiden koordinaatit, voivat palauttaa polynomin ja kaikki sen kertoimet, mukaan lukien viimeinen niistä - jaettu salaisuus [3] . $k$ $k$

Järjestelmän piirre on, että mielivaltaisten osakkeiden tapauksessa salaisuuden paljastumisen todennäköisyys on . Toisin sanoen pisteittäisen interpoloinnin tuloksena mikä tahansa kentän elementti yhtä suurella todennäköisyydellä voi olla salaisuus [2] . Samaan aikaan yritys luetella kaikki mahdolliset varjot eivät anna hyökkääjille mahdollisuutta saada lisätietoja salaisuudesta. $k-1$ $p^{-1}$ $k-1$

Polynomin kertoimien suoraviivainen rekonstruointi yhtälöjärjestelmän ratkaisun kautta voidaan korvata Lagrangen interpolaatiopolynomin laskennalla (tästä yksi menetelmän nimistä). Polynomikaava näyttää tältä [3] :

{\begin{aligned}F\left(x\right)&=&\sum \limits _{i}{l_{i}\left(x\right)y_{i}}&\mod p\ \l_{i}\left(x\right)&=&\prod \limits _{i\neq j}{\frac {x-x_{j}}{x_{i}-x_{j}}}& \mod p\\\end{aligned}}

missä ovat polynomin pisteiden koordinaatit. Kaikki toiminnot suoritetaan myös viimeisessä kentässä [3] . $\left(x_{i},y_{i}\right)$ $s$

Ominaisuudet

Tämän salaisen jakamisjärjestelmän etuja ovat [1] :

Ihanteellinen: ei redundanssia — salaisuuden kunkin osuuden koko on yhtä suuri kuin salaisuuden koko.
Skaalautuvuus: skeemaolosuhteissa salaisten osuuksien omistajien määrä voi kasvaa edelleen aina asti , missä on laskelmia suorittavan kentän koko. Tässä tapauksessa salaisuuden saamiseksi vaadittavien osakkeiden määrä pysyy ennallaan. $(k,n)$ $n$ $s$ $s$ $k$
Dynaaminen: Voit ajoittain muuttaa käytettyä polynomia ja laskea varjot uudelleen pitäen salaisuuden (vapaa jäsen) ennallaan. Tässä tapauksessa tietoturvaloukkauksen todennäköisyys vuotavien varjojen vuoksi pienenee, koska salaisuuden saamiseksi tarvitset polynomin yhdestä versiosta saatuja varjoja. $k$
Joustavuus: tapauksissa, joissa sivut eivät ole tasa-arvoisia, järjestelmä sallii tämän huomioimisen antamalla useita varjoja yhdelle puolelle kerralla. Esimerkiksi ballistisen ohjuksen laukaisukoodi voidaan jakaa kaavion mukaan siten, että vain kolme yhdessä kokoontuvaa kenraalia voi laukaista ohjuksen, tai yksi presidentti, jolle annettiin kolme varjoa kerralla salaisuuden erottamisessa. ${\näyttötyyli (3,6)}$

Haitat [4] :

Epäluotettava jälleenmyyjä: Oletuksena järjestelmä olettaa, että varjojen luoja ja jakaja on luotettava, mikä ei aina pidä paikkaansa.
Sivujen varjojen oikeellisuutta ei ole varmistettu: jakoon osallistuva puoli ei voi varmuudella sanoa, että sen varjo on aito - vaihtamalla alkuperäiseen polynomiin saadaan oikea yhtäläisyys.

Käyttö

Tämä menetelmä on löytänyt sovelluksen laitteiston salausmoduuleissa, joissa sitä käytetään usean käyttäjän valtuutukseen julkisen avaimen infrastruktuurissa [5] .

Kaavaa käytetään myös digitaalisessa steganografiassa tietojen salaiseen siirtämiseen digitaalisissa kuvissa [6] [7] [8] [9] , torjumaan hyökkäyksiä kolmannen osapuolen kanavien kautta toteutettaessa AES - algoritmia [10] .

Lisäksi Shamir-mallia voidaan käyttää digitaalisen vesileiman lisäämiseen digitaalisen videolähetyksen aikana [11] ja henkilökohtaisen salausavaimen luomiseen biometrisissa todennusjärjestelmissä [12] .

Esimerkki

Sinun on jaettava salainen "11" 5 osapuolen kesken. Tässä tapauksessa minkä tahansa kolmen osapuolen pitäisi pystyä palauttamaan tämä salaisuus. Eli on tarpeen toteuttaa - kynnysjärjestelmä [3] . ${\näyttötyyli (3,5)}$

Otetaan alkuluku . Muodostetaan astepolynomi : $p=13$ $k-1=3-1=2$

F\left(x\right)=\left(7x^{2}+8x+11\right)\mod 13

Tässä polynomissa tämä on jaettu salaisuus, ja loput kertoimet 7 ja 8 ovat joitain satunnaislukuja, jotka on "unohdettava" salaisuuden jakamisen jälkeen. $yksitoista$

Nyt laskemme 5 eri pisteen koordinaatit:

{\begin{aligned}k_{1}&=F\left(1\right)&=\left(7\cdot 1^{2}+8\cdot 1+11\right)\mod 13&= 0\\k_{2}&=F\left(2\right)&=\left(7\cdot 2^{2}+8\cdot 2+11\right)\mod 13&=3\\k_{3 }&=F\left(3\right)&=\left(7\cdot 3^{2}+8\cdot 3+11\right)\mod 13&=7\\k_{4}&=F\left (4\oikea)&=\vasen(7\cdot 4^{2}+8\cdot 4+11\right)\mod 13&=12\\k_{5}&=F\left(5\right)& =\left(7\cdot 5^{2}+8\cdot 5+11\right)\mod 13&=5\\\end{aligned}}

Tämän jälkeen avaimet (yhdessä niiden numeron, polynomin numeron ja asteen kanssa ) jaetaan osapuolille. Satunnaiset kertoimet ja itse salaisuus "unohdetaan". $p=13$ $k-1=2$ $7.8$ $M=11$

Nyt kaikki 3 osallistujaa voivat palauttaa polynomin ja kaikki sen kertoimet, mukaan lukien viimeinen, jaettu salaisuus. Esimerkiksi polynomin palauttamiseksi kolmessa osassa heidän on ratkaistava järjestelmä: ${\displaystyle k_{2},k_{3},k_{5))$

\left\{{\begin{aligned}\left(a_{2}\cdot 2^{2}+a_{1}\cdot 2+M\right)&\mod 13&=3\\\left (a_{2}\cpiste 3^{2}+a_{1}\cpiste 3+M\oikea)&\mod 13&=7\\\vasen(a_{2}\cpiste 5^{2}+a_{ 1}\cdot 5+M\right)&\mod 13&=5\\\end{aligned}}\right.

Ilmeisesti pienemmällä määrällä tunnettuja salaisuuksia saadaan vähemmän yhtälöitä ja järjestelmää ei voida ratkaista (edes ratkaisujen tyhjentävällä luettelolla).

Muodostetaan Lagrangen interpolaatiopolynomi :

{\begin{aligned}F\left(x\right)&=\sum \limits _{i}{l_{i}\left(x\right)y_{i}}&\mod p\\ l_{i}\left(x\right)&=\prod \limits _{i\neq j}{\frac {x-x_{j}}{x_{i}-x_{j}}}&\mod p\\\loppu{yhdistetty}}

{\begin{aligned}l_{1}\left(x\right)&={\frac {x-x_{2}}{x_{1}-x_{2}}}\cdot {\frac {x-x_{3}}{x_{1}-x_{3}}}={\frac {x-3}{2-3}}\cdot {\frac {x-5}{2-5} }={\frac {1}{3}}\left({x^{2}-8x+15}\right)=9\left({x^{2}+5x+2}\right)=9x ^{2}+6x+5\mod 13\\l_{2}\left(x\right)&={\frac {x-x_{1}}{x_{2}-x_{1}}}\ cdot {\frac {x-x_{3}}{x_{2}-x_{3}}}={\frac {x-2}{3-2}}\cdot {\frac {x-5}{ 3-5}}={\frac {1}{11}}\left({x^{2}-7x+10}\right)=6\left({x^{2}+6x+10}\ oikea)=6x^{2}+10x+8\mod 13\\l_{3}\left(x\right)&={\frac {x-x_{1}}{x_{3}-x_{1 ))}\cdot {\frac {x-x_{2}}{x_{3}-x_{2}}}={\frac {x-2}{5-2}}\cdot {\frac {x -3}{5-3}}={\frac {1}{6}}\left({x^{2}-5x+6}\right)=11\left({x^{2}+8x +6}\right)=11x^{2}+10x+1\mod 13\end{aligned}}}

Saamme alkuperäisen polynomin:

{\begin{aligned}F\left(x\right)&=3\cdot l_{1}\left(x\right)+7\cdot l_{2}\left(x\right)+5 \cdot l_{3}\left(x\right)\mod p\\a_{2}&=9\cdot 3+6\cdot 7+11\cdot 5=7\mod 13\\a_{1}& =6\cpiste 3+10\cpiste 7+10\cpiste 5=8\mod 13\\M&=5\cdot 3+8\cdot 7+1\cdot 5=11\mod 13\\F\left(x \right)&=7x^{2}+8x+11\mod 13\end{aligned}}

Polynomin viimeinen kerroin - - on salaisuus [3] . $M=11$

Katso myös

Muistiinpanot

↑ 1 2 3 Shamir A. Kuinka jakaa salaisuus // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Voi. 22, Iss. 11. - s. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
↑ 1 2 Chmora A.L. Nykyaikainen sovellettu kryptografia. - 2. painos, poistettu .. - M . : Helios ARV, 2002. - S. 123-124. — 256 s. — ISBN 5-85438-046-3 .
↑ 1 2 3 4 5 6 7 8 9 Schneier B. 23.2 Salaiset jakamisalgoritmit. Lagrangen interpolaatiopolynomien kaavio // Applied Cryptography. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M . : Triumf, 2002. - S. 588-589. — 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
↑ Dawson E. , Donovan D. Shamirin salaisuuksien jakamisjärjestelmän laajuus (englanniksi) // Computers & Security - Elsevier BV , 1994. - Voi. 13, Iss. 1, 69-78. — ISSN 0167-4048 ; 1872-6208 - doi:10.1016/0167-4048(94)90097-3
↑ P. Luo, A. Yu-Lun Lin, Z. Wang, M. Karpovsky. Secure Shamir's Secret Sharing Scheme -laitteiston toteutus // HASE '14 Proceedings of 2014 IEEE 15th International Symposium on High-Assurance Systems Engineering : Proceedings. - Washington, DC, USA: IEEE Computer Society, 2014. - P. 193-200. — ISSN 978-1-4799-3466-9 . - doi : 10.1109/HASE.2014.34 .
↑ Chia-Chun Wu, Shang-Juh Kao, Wen-Chung Kuo, Min-Shiang Hwang. Käännettävä salainen kuvien jakaminen Shamirin suunnitelman perusteella // IIH-MSP '09 2009 viidennen kansainvälisen älykästä tiedon piilottamista ja multimediasignaalien käsittelyä käsittelevän konferenssin julkaisut: Jatketaan. - Washington, DC, USA: IEEE Computer Society, 2009. - P. 1014-1017. - ISBN 978-0-7695-3762-7 . - doi : 10.1109/IIH-MSP.2009.158 .
↑ Ulutas M. , Ulutaş G. , Nabiyev V. V. Lääketieteellinen kuvaturvallisuus ja EPR:n piilottaminen Shamirin salaisen jakamisjärjestelmän avulla (englanniksi) // J. Syst. Ohjelmisto - Elsevier BV , 2011. - Voi. 84, Iss. 3. - s. 341-353. — ISSN 0164-1212 ; 1873-1228 - doi:10.1016/J.JSS.2010.11.928
↑ S. Salim, S. Suresh, R. Gokul, Reshma S. Shamirin salaisen jakamisjärjestelmän soveltaminen salaisten tietojen piilottamiseen ja todentamiseen // International Journal of Advanced Research in Computer Science & Technology : Journal. - 2014. - Vol. 2, ei. 2 . - s. 220-224. — ISSN 2347-8446 .
↑ Che-Wei Lee, Wen-Hsiang Tsai. Tietojen piilotusmenetelmä, joka perustuu tietojen jakamiseen PNG-kuvien kautta värikuvien todentamisen ja metatietojen upottamisen sovelluksiin // Signal Processing : Journal. - Amsterdam, Alankomaat: Elsevier North-Holland, Inc., 2013. - Voi. 93, nro. 7 . - s. 2010-2025. — ISSN 0165-1684 . - doi : 10.1016/j.sigpro.2013.01.009 .
↑ Goubin L. , Martinelli A. AES:n suojaaminen Shamirin salaisella jakamisjärjestelmällä // Salauslaitteistot ja sulautetut järjestelmät - CHES 2011 : 13th International Workshop, Nara, Japani, 28. syyskuuta - 1. lokakuuta 2011, Proceedings / B. Preneel , T. Takagi - Berliini , Heidelberg , New York, NY , Lontoo [jne.] : Springer Science+Business Media , 2011. - s. 79-94. — 524 s. - ( Lecture Notes in Computer Science ; Vol. 6917) - ISBN 978-3-642-23950-2 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-642-23951-9_6
↑ Xiao S. , Ling H. , Zou F. , Lu Z. Salainen jakamiseen perustuva videovesileima-algoritmi useille käyttäjille // Digitaalinen vesileima : 7th International Workshop , IWDW 2008, Busan, Korea, 10.-12.11.2008 , Selected Papers // H. J. Kim , S. Katzenbeisser , A. T. S. Ho - Berliini , Heidelberg , New York, NY , Lontoo [jne.] : Springer Berlin Heidelberg , 2009. - P. 303-312. — 472 s. - ( Lecture Notes in Computer Science ; Vol. 5450) - ISBN 978-3-642-04437-3 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-642-04438-0_26
↑ A. Teoh, D. Ngo, A. Goh. Henkilökohtainen salausavainten luominen FaceHashingin perusteella // Tietokoneet ja turvallisuus : Journal. - Elsevier Advanced Technology Publications Oxford, 2004. - Voi. 23, ei. 7 . - s. 606-614. — ISSN 0167-4048 . - doi : 10.1016/j.cose.2004.06.002 .

Kirjallisuus

Shamir A. Kuinka jakaa salaisuus // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Voi. 22, Iss. 11. - s. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
Schneier B. 23.2 Algoritmit salaisuuden jakamiseen. Lagrangen interpolaatiopolynomien kaavio // Applied Cryptography. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M . : Triumf, 2002. - S. 588-589. — 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
Chmora A.L. Nykyaikainen sovellettu kryptografia. - 2. painos, poistettu .. - M . : Helios ARV, 2002. - S. 123-124. — 256 s. — ISBN 5-85438-046-3 .
Yhteensä alle toim. Jaštšenko V.V. Johdatus kryptografiaan. - 2. painos, Rev. - M .: MTSNMO: "Chero", 1999. - S. 118-125. — 272 s. - ISBN 5-900916-40-5 .

Linkit

ssss: Shamirin salaisuuden jakamisjärjestelmän toteutus interaktiivisella demolla.