Schema de partajare secretă a lui Shamir

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 11 octombrie 2018; verificarea necesită 1 editare .

Schema polinomială de interpolare Lagrange ( schema de partajare secretă Shamir sau schema Shamir ) este o schemă de partajare secretă utilizată pe scară largă în criptografie . Schema lui Shamir permite implementarea unui prag de partajare a unui mesaj secret (secret) între părți, astfel încât numai oricare sau mai multe părți ( ≤ ) să poată recupera secretul. În acest caz, oricare și mai puține părți nu vor putea restabili secretul. $(k,n)$ $n$ $k$ $k$ $n$ $k-1$

Istorie

În 1979, criptoanalistul israelian Adi Shamir a propus o schemă de prag pentru partajarea unui secret între părți, care permite partajarea în așa fel încât [1] : $n$

Pentru a restabili secretul , este suficientă mai mult de o parte. $k$
Nu și mai puține părți vor putea obține informații despre secret. $(k-1)$

Idee

Sunt necesare puncte pentru a interpola un polinom de grade . De exemplu, două puncte sunt suficiente pentru a defini o linie dreaptă , trei puncte sunt suficiente pentru a defini o parabolă și așa mai departe. $k-1$ $k$

Ideea principală a acestei scheme este că interpolarea este imposibilă dacă se cunoaște un număr mai mic de puncte [1] .

Dacă vrem să împărtășim un secret între oameni în așa fel încât doar o persoană ( ≤ ) să-l poată recupera, îl „ascundem” în formula polinomială de grad . Este posibil să restabiliți acest polinom și secretul original doar prin puncte. Numărul de puncte diferite ale polinomului nu este limitat (în practică, este limitat de mărimea câmpului numeric în care se efectuează calculele) [2] . $n$ $k$ $k$ $n$ $k-1$ $k$

Descriere

Faza pregătitoare

Să fie necesar să se partajeze secretul între părți în așa fel încât orice participant să poată restaura secretul (adică este necesar să se implementeze - schema de prag ). $M$ $n$ $k$ $(k,n)$

Să alegem un număr prim . Acest număr poate fi comunicat deschis tuturor participanților. Specifică câmpul de dimensiune finală . Construim un polinom de grad peste acest câmp (adică alegem aleatoriu toți coeficienții polinomului, cu excepția ) [3] : $p>M$ $p$ $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\dreapta)\mod p

În acest polinom , acesta este secretul partajat, iar coeficienții rămași sunt niște numere aleatorii care vor trebui „uitate” după finalizarea procedurii de partajare a secretelor [3] . $M$ $a_{k-1}, a_{k-2},\dots, a_{1)$

Generarea de acțiuni secrete

Acum calculăm „acțiunile” - valorile polinomului construit mai sus, în diferite puncte, și ≠ [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)&=&\ stânga(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\ dreapta)&=&\left(a_{k-1}\cdot n^{k-1}+a_{k-2}\cdot n^{k-2}+\dots +a_{1}\cdot n +M\dreapta)&\mod p\\\end{aliniat}}

Argumentele polinomului (numerele de secrete) nu trebuie să fie în ordine, principalul lucru este că toate să fie diferite în modulo . $p$

După aceea, fiecărei părți care participă la partajarea secretului i se dă o parte din secret împreună cu un număr . În plus, toate părțile sunt informate cu privire la gradul polinomului și dimensiunea câmpului . Coeficienții aleatori și secretul în sine sunt „uitați” [3] . $k_{i)$ $i$ $k-1$ $p$ $a_{k-1}, a_{k-2},\dots, a_{1)$ $M$

Restaurarea secretului

Acum, orice participant, cunoscând coordonatele diferitelor puncte ale polinomului, va putea restabili polinomul și toți coeficienții săi, inclusiv ultimul dintre ei - secretul partajat [3] . $k$ $k$

O caracteristică a schemei este că probabilitatea dezvăluirii secretului în cazul acțiunilor arbitrare este estimată ca . Adică, ca urmare a interpolării prin punct, orice element al câmpului cu probabilitate egală poate fi un secret [2] . În același timp, o încercare de a enumera toate umbrele posibile nu va permite atacatorilor să obțină informații suplimentare despre secret. $k-1$ $p^{-1}$ $k-1$

Reconstructia rectilinie a coeficientilor unui polinom prin solutia unui sistem de ecuatii poate fi inlocuita cu calculul polinomului de interpolare Lagrange (de unde si una dintre denumirile metodei). Formula polinomială va arăta astfel [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{aliniat}}

unde sunt coordonatele punctelor polinomului. Toate operațiile se execută și în câmpul final [3] . $\left(x_{i},y_{i}\right)$ $p$

Proprietăți

Avantajele acestei scheme de partajare secretă includ [1] :

Ideal: fără redundanță — dimensiunea fiecărei părți a secretului este egală cu dimensiunea secretului.
Scalabilitate: în condiții de schemă, numărul deținătorilor de acțiuni secrete poate crește în continuare până la , unde este dimensiunea câmpului în care se efectuează calculele. În acest caz, numărul de acțiuni necesare pentru obținerea secretului va rămâne neschimbat. $(k,n)$ $n$ $p$ $p$ $k$
Dinamic: Puteți schimba periodic polinomul utilizat și recalcula umbrele păstrând secretul (membru liber) neschimbat. În acest caz, probabilitatea de încălcare a securității prin scurgeri de umbre va scădea, deoarece pentru a obține un secret, aveți nevoie de umbre obținute pe o versiune a polinomului. $k$
Flexibilitate: în cazurile în care laturile nu sunt egale, schema permite ca acest lucru să fie luat în considerare prin emiterea mai multor umbre pe o parte deodată. De exemplu, codul de lansare al unei rachete balistice poate fi împărțit în funcție de schemă, astfel încât doar trei generali care se adună să poată lansa racheta, sau un președinte, căruia i s-au dat trei umbre deodată la separarea secretului. $(3,6)$

Dezavantaje [4] :

Dealer nesigur: În mod implicit, schema presupune că cel care generează și distribuie umbrele este de încredere, ceea ce nu este întotdeauna adevărat.
Nu există nicio verificare a corectitudinii umbrelor laturilor: partea care participă la împărțire nu poate spune cu certitudine că umbra sa este autentică - atunci când se înlocuiește în polinomul original, se obține egalitatea corectă.

Utilizare

Această schemă și-a găsit aplicație în modulele criptografice hardware, unde este utilizată pentru autorizarea multi-utilizator într- o infrastructură cu cheie publică [5] .

De asemenea, schema este utilizată în steganografia digitală pentru transmiterea sub acoperire a informațiilor în imagini digitale [6] [7] [8] [9] , pentru a contracara atacurile prin canale terțe la implementarea algoritmului AES [10] .

În plus, schema Shamir poate fi utilizată pentru a aplica un filigran digital în timpul transmisiei video digitale [11] și pentru a genera o cheie criptografică personală utilizată în sistemele de autentificare biometrică [12] .

Exemplu

Vă permite să împărtășiți secretul „11” între 5 părți. În acest caz, oricare 3 părți ar trebui să poată restabili acest secret. Adică, este necesară implementarea - schema de prag [3] . $(3,5)$

Să luăm un număr prim . Să construim un polinom de grad : $p=13$ $k-1=3-1=2$

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

În acest polinom , acesta este secretul partajat, iar coeficienții rămași 7 și 8 sunt niște numere aleatorii care vor trebui „uitate” după finalizarea procedurii de partajare a secretelor. $unsprezece$

Acum calculăm coordonatele a 5 puncte diferite:

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

După aceea, cheile (împreună cu numărul lor, numărul și gradul polinomului ) sunt distribuite părților. Coeficienții aleatori și secretul în sine sunt „uitați”. $p=13$ $k-1=2$ $7.8$ $M=11$

Acum oricare 3 participanți vor putea recupera polinomul și toți coeficienții acestuia, inclusiv ultimul, secretul partajat. De exemplu, pentru a recupera un polinom în trei părți , vor trebui să rezolve sistemul: ${\displaystyle k_{2},k_{3},k_{5))$

\left\{{\begin{aliniat}\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{aliniat}}\right.

Evident, cu un număr mai mic de secrete cunoscute, se vor obține mai puține ecuații și sistemul nu va putea fi rezolvat (chiar prin enumerarea exhaustivă a soluțiilor).

Să construim polinomul de interpolare Lagrange :

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

{\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}\ dreapta)=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}}

Obținem polinomul original:

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

Ultimul coeficient al polinomului - - este secretul [3] . $M=11$

Vezi și

Note

↑ 1 2 3 Shamir A. Cum să împărtășești un secret // 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. Criptografia aplicată modernă. - Ed. a II-a, șters .. - M . : Helios ARV, 2002. - S. 123-124. — 256 p. — ISBN 5-85438-046-3 .
↑ 1 2 3 4 5 6 7 8 9 Schneier B. 23.2 Algoritmi de partajare a secretelor. Schema polinoamelor de interpolare Lagrange // Criptografie aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumf, 2002. - S. 588-589. — 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
↑ Dawson E. , Donovan D. The breadth of Shamir's secret-sharing scheme (engleză) // 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. Implementarea hardware a Secure Shamir's Secret Sharing Scheme // HASE '14 Proceedings of the 2014 IEEE 15th International Symposium on High-Assurance Systems Engineering : Proceeding. - Washington, DC, SUA: 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. Partajare reversibilă a imaginilor secrete pe baza schemei lui Shamir // IIH-MSP '09 Proceedings of the 2009 Fifth International Conference on Intelligent Information Ascunderea și Multimedia Signal Processing: Proceeding. - Washington, DC, SUA: 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. Medical image security and EPR hiding using Shamir's secret sharing scheme (en engleză) // J. Syst. Software - Elsevier BV , 2011. - Vol. 84, Iss. 3. - P. 341-353. — ISSN 0164-1212 ; 1873-1228 - doi:10.1016/J.JSS.2010.11.928
↑ S. Salim, S. Suresh, R. Gokul, Reshma S. Application of Shamir Secret Sharing Scheme for Secret Data Hiding and Authentication // International Journal of Advanced Research in Computer Science & Technology : Journal. - 2014. - Vol. 2, nr. 2 . - P. 220-224. — ISSN 2347-8446 .
↑ Che-Wei Lee, Wen-Hsiang Tsai. O metodă de ascundere a datelor bazată pe partajarea informațiilor prin imagini PNG pentru aplicații de autentificare a imaginilor color și încorporare a metadatelor // Procesare semnal : Jurnal. - Amsterdam, Țările de Jos: 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, Japonia, 28 septembrie - 1 octombrie 2011, Proceedings / B. Preneel , T. Takagi - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer Science+Business Media , 2011. - P. 79-94. — 524 p. - ( Note de curs în Informatică ; 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. Secret Sharing Based Video Watermark Algorithm for Multiuser // Digital Watermarking : 7th International Workshop , IWDW 2008, Busan, Korea, 10-12 noiembrie 2008 , Selected Papers / H. J. Kim , S. Katzenbeisser , A. T. S. Ho - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer Berlin Heidelberg , 2009. - P. 303-312. — 472 p. - ( Note de curs în Informatică ; 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. Generare personalizată de chei criptografice bazată pe FaceHashing // Calculatoare și securitate : Jurnal. - Elsevier Advanced Technology Publications Oxford, 2004. - Vol. 23, nr. 7 . - P. 606-614. — ISSN 0167-4048 . - doi : 10.1016/j.cose.2004.06.002 .

Literatură

Shamir A. Cum să împărtășești un secret // 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 Algoritmi pentru partajarea unui secret. Schema polinoamelor de interpolare Lagrange // Criptografie aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumf, 2002. - S. 588-589. — 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Chmora A.L. Criptografia aplicată modernă. - Ed. a II-a, șters .. - M . : Helios ARV, 2002. - S. 123-124. — 256 p. — ISBN 5-85438-046-3 .
Sub total ed. Iascenko V.V. Introducere în criptografie. - ed. a II-a, Rev. - M .: MTSNMO: „Chero”, 1999. - S. 118-125. — 272 p. - ISBN 5-900916-40-5 .

Link -uri

ssss: O implementare a schemei de partajare a secretelor lui Shamir cu o demonstrație interactivă.