Shamir's Secret Sharing Scheme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 11. oktober 2018; verifikation kræver 1 redigering .

Lagrange-interpolationspolynomiet ( Shamirs hemmelige delingsskema eller Shamir- skemaet ) er et hemmeligt delingsskema, der er meget udbredt i kryptografi . Shamirs skema gør det muligt at implementere en tærskeldeling af en hemmelig besked (hemmelighed) mellem parter, så kun en eller flere parter ( ≤ ) kan genvinde hemmeligheden. I dette tilfælde vil enhver eller mindre part ikke være i stand til at genoprette hemmeligheden. $(k,n)$ $n$ $k$ $k$ $n$ $k-1$

Historie

I 1979 foreslog den israelske kryptoanalytiker Adi Shamir en tærskelordning for deling af en hemmelighed mellem parter, som tillader deling på en sådan måde, at [1] : $n$

For at genoprette hemmeligheden er mere end én side nok. $k$
Ingen og færre parter vil kunne få nogen information om hemmeligheden. $(k-1)$

Idé

Der kræves point for at interpolere et gradpolynomium . For eksempel er to punkter nok til at definere en lige linje , tre punkter er nok til at definere en parabel , og så videre. $k-1$ $k$

Hovedideen med dette skema er, at interpolation er umulig , hvis et mindre antal punkter er kendt [1] .

Hvis vi ønsker at dele en hemmelighed mellem mennesker på en sådan måde, at kun en person ( ≤ ) kan genfinde den, "skjuler" vi den i gradpolynomialformlen . Det er kun muligt at gendanne dette polynomium og den oprindelige hemmelighed med point. Antallet af forskellige punkter i polynomiet er ikke begrænset (i praksis er det begrænset af størrelsen af det numeriske felt, som beregningerne udføres i) [2] . $n$ $k$ $k$ $n$ $k-1$ $k$

Beskrivelse

Forberedende fase

Lad det være nødvendigt at dele hemmeligheden mellem parterne på en sådan måde, at enhver deltager kan genoprette hemmeligheden (det vil sige, at det er nødvendigt at implementere - tærskelordningen ). $M$ $n$ $k$ $(k,n)$

Lad os vælge et primtal . Dette nummer kan meddeles åbent til alle deltagere. Det specificerer det endelige størrelsesfelt . Vi konstruerer et gradspolynomium over dette felt (det vil sige, vi vælger tilfældigt alle polynomiets koefficienter, undtagen ) [3] : $p>M$ $s$ $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 dette polynomium er dette den delte hemmelighed, og de resterende koefficienter er nogle tilfældige tal, der skal "glemmes", efter at proceduren for hemmelig deling er afsluttet [3] . $M$ ${\displaystyle a_{k-1},a_{k-2},\dots ,a_{1))$

Generering af hemmelige aktier

Nu beregner vi "andele" - værdierne af polynomiet konstrueret ovenfor, på forskellige punkter, og ≠ [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)&=&\ venstre(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\venstre(n\ højre)&=&\venstre(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}}

Argumenterne for polynomiet (antal hemmeligheder) behøver ikke at være i orden, det vigtigste er, at de alle er forskellige i modulo . $s$

Derefter får hver part, der deltager i deling af hemmeligheden, en del af hemmeligheden sammen med et nummer . Derudover er alle parter informeret om graden af polynomiet og størrelsen af feltet . Tilfældige koefficienter og selve hemmeligheden er "glemt" [3] . ${\displaystyle k_{i))$ $jeg$ $k-1$ $s$ ${\displaystyle a_{k-1},a_{k-2},\dots ,a_{1))$ $M$

Gendannelse af hemmeligheden

Nu vil enhver deltager, der kender koordinaterne for forskellige punkter i polynomiet, være i stand til at gendanne polynomiet og alle dets koefficienter, inklusive den sidste af dem - den fælles hemmelighed [3] . $k$ $k$

Et kendetegn ved ordningen er, at sandsynligheden for at afsløre hemmeligheden i tilfælde af vilkårlige aktier estimeres til . Det vil sige, som et resultat af interpolation for punkt, kan ethvert element i feltet med lige stor sandsynlighed være en hemmelighed [2] . Samtidig vil et forsøg på at opregne alle mulige skygger ikke tillade angribere at få yderligere oplysninger om hemmeligheden. $k-1$ $p^{-1}$ $k-1$

Retlineær rekonstruktion af koefficienterne for et polynomium gennem løsning af et ligningssystem kan erstattes af beregningen af Lagrange-interpolationspolynomiet (deraf et af metodens navne). Polynomialformlen vil se sådan ud [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}}

hvor er koordinaterne for polynomiets punkter. Alle operationer udføres også i det sidste felt [3] . $\left(x_{i},y_{i}\right)$ $s$

Egenskaber

Fordelene ved denne hemmelige delingsordning inkluderer [1] :

Ideel: ingen redundans - størrelsen af hver andel af hemmeligheden er lig med størrelsen af hemmeligheden.
Skalerbarhed: under skemaforhold kan antallet af ejere af hemmelige aktier øges yderligere op til , hvor er størrelsen af det felt, hvor beregningerne udføres. I dette tilfælde vil antallet af aktier , der kræves for at opnå hemmeligheden, forblive uændret. $(k,n)$ $n$ $s$ $s$ $k$
Dynamisk: Du kan periodisk ændre det anvendte polynomium og genberegne skyggerne, mens hemmeligheden (gratis medlem) bevares uændret. I dette tilfælde vil sandsynligheden for sikkerhedsbrud ved at lække skygger falde, da for at opnå en hemmelighed skal du have skygger opnået på en version af polynomiet. $k$
Fleksibilitet: i tilfælde, hvor siderne ikke er ens, giver ordningen mulighed for at tage højde for dette ved at udstede flere skygger til den ene side på én gang. For eksempel kan affyringskoden for et ballistisk missil opdeles i henhold til skemaet, så kun tre generaler, der kommer sammen, kan affyre missilet, eller en præsident, som fik tre skygger på én gang, da hemmeligheden adskilles. $(3,6)$

Ulemper [4] :

Upålidelig forhandler: Som standard antager ordningen, at den, der genererer og distribuerer skyggerne, er pålidelig, hvilket ikke altid er sandt.
Der er ingen verifikation af rigtigheden af sidernes skygger: den side , der deltager i opdelingen, kan ikke med sikkerhed sige, at dens skygge er ægte - når der erstattes med det oprindelige polynomium, opnås den korrekte lighed.

Brug

Denne ordning har fundet anvendelse i hardware kryptografiske moduler, hvor den bruges til flerbrugerautorisation i en offentlig nøgleinfrastruktur [5] .

Skemaet bruges også i digital steganografi til skjult transmission af information i digitale billeder [6] [7] [8] [9] , for at imødegå angreb gennem tredjepartskanaler ved implementering af AES - algoritmen [10] .

Derudover kan Shamir-ordningen bruges til at anvende et digitalt vandmærke under digital videotransmission [11] og generere en personlig kryptografisk nøgle , der bruges i biometriske autentificeringssystemer [12] .

Eksempel

Lad dig dele hemmeligheden "11" mellem 5 parter. I dette tilfælde bør alle tre parter være i stand til at genoprette denne hemmelighed. Det vil sige, at det er nødvendigt at implementere - tærskelordningen [3] . $(3,5)$

Lad os tage et primtal . Lad os konstruere et gradspolynomium : $p=13$ $k-1=3-1=2$

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

I dette polynomium er dette den delte hemmelighed, og de resterende koefficienter 7 og 8 er nogle tilfældige tal, der skal "glemmes", efter at proceduren for hemmelig deling er afsluttet. $elleve$

Nu beregner vi koordinaterne for 5 forskellige 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\venstre (4\right)&=\left(7\cdot 4^{2}+8\cdot 4+11\right)\mod 13&=12\\k_{5}&=F\left(5\right)& =\venstre(7\cdot 5^{2}+8\cdot 5+11\right)\mod 13&=5\\\end{aligned}}

Derefter fordeles nøglerne (sammen med deres nummer, antallet og graden af polynomiet ) til parterne. Tilfældige koefficienter og selve hemmeligheden er "glemt". $p=13$ $k-1=2$ $7.8$ $M=11$

Nu vil alle tre deltagere være i stand til at gendanne polynomiet og alle dets koefficienter, inklusive den sidste, den delte hemmelighed. For at genskabe et polynomium i tre dele skal de for eksempel løse 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\\\venstre (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.

Med et mindre antal kendte hemmeligheder vil der naturligvis blive opnået færre ligninger, og systemet vil ikke kunne løses (selv ved udtømmende opregning af løsninger).

Lad os konstruere Lagrange-interpolationspolynomiet :

{\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øjre)=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 oprindelige polynomium:

{\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\venstre(x \right)&=7x^{2}+8x+11\mod 13\end{aligned}}

Den sidste koefficient af polynomiet - - er hemmeligheden [3] . $M=11$

Se også

Noter

↑ 1 2 3 Shamir A. Sådan deler du en hemmelighed // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Vol. 22, Iss. 11. - S. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
↑ 1 2 Chmora A.L. Moderne anvendt kryptografi. - 2. udg., slettet .. - 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 Algoritmer til hemmelig deling. Skema for Lagrange-interpolationspolynomier // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumf, 2002. - S. 588-589. — 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
↑ Dawson E. , Donovan D. Bredden af Shamirs hemmelighedsdelingsplan (engelsk) // 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. Hardwareimplementering af Secure Shamir's Secret Sharing Scheme // HASE '14 Proceedings of the 2014 IEEE 15th International Symposium on High-Assurance 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 hemmelig billeddeling baseret på Shamirs skema // 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. - S. 1014-1017. - ISBN 978-0-7695-3762-7 . - doi : 10.1109/IIH-MSP.2009.158 .
↑ Ulutas M. , Ulutaş G. , Nabiyev V. V. Medicinsk billedsikkerhed og EPJ-skjul ved hjælp af Shamirs hemmelige delingsskema (engelsk) // J. Syst. Software - 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. Anvendelse af Shamir Secret Sharing Scheme for hemmelige dataskjul og godkendelse // International Journal of Advanced Research in Computer Science & Technology : Journal. - 2014. - Bd. 2, nr. 2 . - S. 220-224. — ISSN 2347-8446 .
↑ Che-Wei Lee, Wen-Hsiang Tsai. En dataskjulningsmetode baseret på informationsdeling via PNG-billeder til anvendelser af farvebilledgodkendelse og metadataindlejring // Signal Processing : Journal. - Amsterdam, Holland: Elsevier North-Holland, Inc., 2013. - Vol. 93, nr. 7 . - S. 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 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. Hemmelig delingsbaseret videovandmærkealgoritme for flere brugere // Digital Watermarking : 7th International Workshop , IWDW 2008, Busan, Korea, November 10-12, 2008 , Selected Papers / H. J. Kim , S. Katzenbeisser , A. T. S. Ho - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 2009. - S. 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. Personlig kryptografisk nøglegenerering baseret på FaceHashing // Computere og sikkerhed: 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. Sådan deler du en hemmelighed // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Vol. 22, Iss. 11. - S. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
Schneier B. 23.2 Algoritmer til at dele en hemmelighed. Skema for Lagrange-interpolationspolynomier // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumf, 2002. - S. 588-589. — 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Chmora A.L. Moderne anvendt kryptografi. - 2. udg., slettet .. - M . : Helios ARV, 2002. - S. 123-124. — 256 s. — ISBN 5-85438-046-3 .
Under total udg. Yashchenko V.V. Introduktion til kryptografi. - 2. udg., Rev. - M .: MTSNMO: "Chero", 1999. - S. 118-125. — 272 s. - ISBN 5-900916-40-5 .

Links

ssss: En implementering af Shamirs hemmelighedsdelingsplan med en interaktiv demo.