Shamirs hemliga delningsschema

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 11 oktober 2018; verifiering kräver 1 redigering .

Lagrange-interpolationspolynomschemat ( Shamirs hemliga delningsschema eller Shamir- schemat ) är ett hemligt delningsschema som ofta används inom kryptografi . Shamirs schema tillåter att implementera en tröskeldelning av ett hemligt meddelande (hemligt) mellan parter så att endast någon eller flera parter ( ≤ ) kan återställa hemligheten. I det här fallet kommer alla och färre parter inte att kunna återställa hemligheten. $(k,n)$ $n$ $k$ $k$ $n$ $k-1$

Historik

År 1979 föreslog den israeliska kryptoanalytikern Adi Shamir ett tröskelschema för att dela en hemlighet mellan parter, vilket tillåter delning på ett sådant sätt att [1] : $n$

För att återställa hemligheten räcker det med mer än en sida. $k$
Inga och färre parter kommer att kunna få någon information om hemligheten. $(k-1)$

Idé

Poäng krävs för att interpolera ett gradpolynom . Till exempel räcker två punkter för att definiera en rak linje , tre punkter räcker för att definiera en parabel , och så vidare. $k-1$ $k$

Huvudtanken med detta schema är att interpolation är omöjlig om ett mindre antal punkter är kända [1] .

Om vi vill dela en hemlighet mellan människor på ett sådant sätt att bara en person ( ≤ ) kan återställa den, "gömmer" vi den i gradpolynomformeln . Det är möjligt att återställa detta polynom och den ursprungliga hemligheten endast med poäng. Antalet olika punkter i polynomet är inte begränsat (i praktiken begränsas det av storleken på det numeriska fältet där beräkningarna utförs) [2] . $n$ $k$ $k$ $n$ $k-1$ $k$

Beskrivning

Förberedande fas

Låt det vara nödvändigt att dela hemligheten mellan parterna på ett sådant sätt att alla deltagare kan återställa hemligheten (det vill säga det är nödvändigt att implementera - tröskelschemat ). $M$ $n$ $k$ $(k,n)$

Låt oss välja något primtal . Detta nummer kan kommuniceras öppet till alla deltagare. Den anger det slutliga storleksfältet . Vi konstruerar ett gradpolynom över detta fält (det vill säga vi väljer slumpmässigt alla koefficienter för polynomet, förutom ) [3] : $p>M$ $sid$ $k-1$ $M$

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

I detta polynom är detta den delade hemligheten, och de återstående koefficienterna är några slumpmässiga tal som kommer att behöva "glöms bort" efter att proceduren för hemlighetsdelning har slutförts [3] . $M$ ${\displaystyle a_{k-1},a_{k-2},\dots ,a_{1))$

Generering av hemliga aktier

Nu beräknar vi "andelarna" - värdena för polynomet konstruerat ovan, vid olika punkter, och ≠ [3] : $n$ $(x$ $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)&=&\ vänster(a_{k-1}\cdot 2^{k-1}+a_{k-2}\cdot 2^{k-2}+\dots +a_{1}\cdot 2+M\right)& \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\ höger)&=&\left(a_{k-1}\cdot n^{k-1}+a_{k-2}\cdot n^{k-2}+\dots +a_{1}\cdot n +M\right)&\mod p\\\end{aligned}}

Argumenten för polynomet (antal hemligheter) behöver inte vara i ordning, huvudsaken är att de alla är olika i modulo . $sid$

Därefter får varje part som deltar i delning av hemligheten en del av hemligheten tillsammans med ett nummer . Dessutom informeras alla parter om graden av polynomet och storleken på fältet . Slumpmässiga koefficienter och själva hemligheten "glöms bort" [3] . ${\displaystyle k_{i))$ $i$ $k-1$ $sid$ ${\displaystyle a_{k-1},a_{k-2},\dots ,a_{1))$ $M$

Återställer hemligheten

Nu kommer alla deltagare, som känner till koordinaterna för olika punkter i polynomet, att kunna återställa polynomet och alla dess koefficienter, inklusive den sista av dem - den delade hemligheten [3] . $k$ $k$

Ett kännetecken för systemet är att sannolikheten att avslöja hemligheten vid godtyckliga aktier uppskattas till . Det vill säga, som ett resultat av interpolation med punkt, kan vilket element i fältet som helst med lika sannolikhet vara en hemlighet [2] . Samtidigt kommer ett försök att räkna upp alla möjliga skuggor inte att tillåta angripare att få ytterligare information om hemligheten. $k-1$ $p^{-1}$ $k-1$

Riktlinjär rekonstruktion av koefficienterna för ett polynom genom lösningen av ett ekvationssystem kan ersättas med beräkningen av Lagrange-interpolationspolynomet (därav ett av metodens namn). Polynomformeln kommer att se ut så här [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}}

var är koordinaterna för polynomets punkter. Alla operationer utförs också i det sista fältet [3] . $\left(x_{i},y_{i}\right)$ $sid$

Egenskaper

Fördelarna med detta hemliga delningsschema inkluderar [1] :

Idealisk: ingen redundans — storleken på varje del av hemligheten är lika med storleken på hemligheten.
Skalbarhet: under schemaförhållanden kan antalet ägare av hemliga aktier öka ytterligare upp till , där är storleken på fältet där beräkningar utförs. I detta fall kommer antalet aktier som krävs för att erhålla hemligheten att förbli oförändrat. $(k,n)$ $n$ $sid$ $sid$ $k$
Dynamisk: Du kan med jämna mellanrum ändra det använda polynomet och räkna om skuggorna samtidigt som du behåller hemligheten (fri medlem) oförändrad. I det här fallet kommer sannolikheten för säkerhetsintrång genom läckande skuggor att minska, eftersom för att få en hemlighet behöver du skuggor som erhållits på en version av polynomet. $k$
Flexibilitet: i fall där sidorna inte är lika, tillåter schemat att ta hänsyn till detta genom att ge flera skuggor åt ena sidan samtidigt. Till exempel kan uppskjutningskoden för en ballistisk missil delas upp enligt schemat så att endast tre generaler som kommer tillsammans kan avfyra missilen, eller en president, som fick tre skuggor på en gång när hemligheten separerades. $(3,6)$

Nackdelar [4] :

Otillförlitlig återförsäljare: Som standard antar schemat att den som genererar och distribuerar skuggorna är pålitlig, vilket inte alltid är sant.
Det finns ingen verifiering av riktigheten av sidornas skuggor: sidan som deltar i uppdelningen kan inte med säkerhet säga att dess skugga är äkta - när den ersätts med det ursprungliga polynomet erhålls den korrekta likheten.

Användning

Detta schema har funnit tillämpning i kryptografiska hårdvarumoduler, där det används för auktorisering av flera användare i en infrastruktur för offentlig nyckel [5] .

Dessutom används schemat i digital steganografi för hemlig överföring av information i digitala bilder [6] [7] [8] [9] , för att motverka attacker genom tredjepartskanaler när AES - algoritmen implementeras [10] .

Dessutom kan Shamir-schemat användas för att applicera en digital vattenstämpel under digital videoöverföring [11] och generera en personlig kryptografisk nyckel som används i biometriska autentiseringssystem [12] .

Exempel

Låt dig behöva dela hemligheten "11" mellan 5 parter. I det här fallet bör alla tre parter kunna återställa denna hemlighet. Det vill säga, det är nödvändigt att implementera - tröskelsystemet [3] . $(3,5)$

Låt oss ta ett primtal . Låt oss konstruera ett gradpolynom : $p=13$ $k-1=3-1=2$

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

I detta polynom är detta den delade hemligheten, och de återstående koefficienterna 7 och 8 är några slumpmässiga tal som kommer att behöva "glöms bort" efter att proceduren för hemlighetsdelning har slutförts. $elva$

Nu beräknar vi koordinaterna för 5 olika punkter:

{\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\right)&=\left(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}}

Därefter fördelas nycklarna (tillsammans med deras nummer, numret och graden av polynomet ) till parterna. Slumpmässiga koefficienter och själva hemligheten "glöms". $p=13$ $k-1=2$ $7.8$ $M=11$

Nu kommer vilka tre deltagare som helst att kunna återställa polynomet och alla dess koefficienter, inklusive den sista, den delade hemligheten. Till exempel, för att återställa ett polynom i tre delar måste de lösa systemet: ${\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}\cdot 3^{2}+a_{1}\cdot 3+M\right)&\mod 13&=7\\\left(a_{2}\cdot 5^{2}+a_{ 1}\cdot 5+M\right)&\mod 13&=5\\\end{aligned}}\right.

Uppenbarligen, med ett mindre antal kända hemligheter, kommer färre ekvationer att erhållas och systemet kommer inte att kunna lösas (även genom en uttömmande uppräkning av lösningar).

Låt oss konstruera Lagrange-interpolationspolynomet :

{\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}}

{\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}\ höger)=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}}}

Vi får det ursprungliga polynomet:

{\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\cdot 3+10\cdot 7+10\cdot 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}}

Den sista koefficienten för polynomet - - är hemligheten [3] . $M=11$

Se även

Anteckningar

↑ 1 2 3 Shamir A. Hur man delar en hemlighet // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Vol. 22, Iss. 11. - P. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
↑ 1 2 Chmora A.L. Modern tillämpad kryptografi. - 2:a uppl., raderad .. - M . : Helios ARV, 2002. - S. 123-124. — 256 sid. — ISBN 5-85438-046-3 .
↑ 1 2 3 4 5 6 7 8 9 Schneier B. 23.2 Algoritmer för hemlighetsdelning. Schema för Lagrange-interpolationspolynom // Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code i C. - M . : Triumf, 2002. - S. 588-589. — 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .
↑ Dawson E. , Donovan D. Bredden av Shamirs hemlighetsdelningssystem (engelska) // Computers & Security - Elsevier BV , 1994. - Vol. 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. Hårdvaruimplementering av Secure Shamir's Secret Sharing Scheme // HASE '14 Proceedings of the 2014 IEEE 15th International Symposium on High-Asurance Systems Engineering: Proceeding. - Washington, DC, USA: IEEE Computer Society, 2014. - S. 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. Reversibel hemlig bilddelning baserat på Shamirs schema // IIH-MSP '09 Proceedings of the 2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing : Proceeding. - 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. Medicinsk bildsäkerhet och EPR-döljning med Shamirs hemliga delningsschema (engelska) // J. Syst. Programvara - Elsevier BV , 2011. - Vol. 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. Tillämpning av Shamir Secret Sharing Scheme för hemlig datadöljning och autentisering // International Journal of Advanced Research in Computer Science & Technology: Journal. - 2014. - Vol. 2, nr. 2 . - S. 220-224. — ISSN 2347-8446 .
↑ Che-Wei Lee, Wen-Hsiang Tsai. En datadöljningsmetod baserad på informationsdelning via PNG-bilder för tillämpningar av färgbildsautentisering och inbäddning av metadata // Signal Processing : Journal. - Amsterdam, Nederländerna: Elsevier North-Holland, Inc., 2013. - Vol. 93, nr. 7 . - P. 2010-2025. — ISSN 0165-1684 . - doi : 10.1016/j.sigpro.2013.01.009 .
↑ Goubin L. , Martinelli A. Protecting AES with Shamir's Secret Sharing Scheme // Cryptographic Hardware and Embedded Systems - CHES 2011 : 13th International Workshop, Nara, Japan, 28 september - 1 oktober 2011, Proceedings / B. Preneel , T. Takagi - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Science+Business Media , 2011. - S. 79-94. — 524 sid. - ( 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. Hemlig delningsbaserad videovattenstämpelalgoritm för flera användare // Digital Watermarking : 7th International Workshop , IWDW 2008, Busan, Korea, 10-12 november 2008 , Selected Papers / H. J. Kim , S. Katzenbeisser , A. T. S. Ho - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 2009. - P. 303-312. — 472 sid. - ( 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. Personlig kryptografisk nyckelgenerering baserad på FaceHashing // Datorer och säkerhet : Journal. - Elsevier Advanced Technology Publications Oxford, 2004. - Vol. 23, nr. 7 . - s. 606-614. — ISSN 0167-4048 . - doi : 10.1016/j.cose.2004.06.002 .

Litteratur

Shamir A. Hur man delar en hemlighet // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Vol. 22, Iss. 11. - P. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
Schneier B. 23.2 Algoritmer för att dela en hemlighet. Schema för Lagrange-interpolationspolynom // Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code i C. - M . : Triumf, 2002. - S. 588-589. — 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .
Chmora A.L. Modern tillämpad kryptografi. - 2:a uppl., raderad .. - M . : Helios ARV, 2002. - S. 123-124. — 256 sid. — ISBN 5-85438-046-3 .
Under totalt ed. Jasjtjenko V.V. Introduktion till kryptografi. - 2nd ed., Rev. - M .: MTSNMO: "Chero", 1999. - S. 118-125. — 272 sid. - ISBN 5-900916-40-5 .

Länkar

ssss: En implementering av Shamirs hemlighetsdelningssystem med en interaktiv demo.