Împărtășirea unui secret

Partajarea secretelor este un termen în criptografie , care este înțeles ca oricare dintre metodele de distribuire a unui secret între un grup de participanți, fiecare dintre care primește o anumită cotă. Secretul poate fi recreat doar de o coaliție de participanți din grupul original și cel puțin un număr cunoscut inițial dintre ei trebuie să fie inclus în coaliție.

Schemele de partajare a secretelor sunt utilizate în cazurile în care există o probabilitate semnificativă de compromis a unuia sau mai multor deținători de secrete, dar probabilitatea unei coluziune neloială de către o parte semnificativă a participanților este considerată neglijabilă.

Schemele existente au două componente: partajarea secretelor și recuperarea secretelor. Partajarea se referă la formarea unor părți ale secretului și distribuirea lor între membrii grupului, ceea ce permite împărțirea responsabilității pentru secret între membrii săi. Schema inversă ar trebui să asigure refacerea acesteia, sub rezerva disponibilității deținătorilor săi într-un anumit număr necesar [1] .

Caz de utilizare: Protocol de vot secret bazat pe partajarea secretă [2] .

Cel mai simplu exemplu de schemă de partajare secretă

Să existe un grup de oameni și un mesaj de lungime , format din caractere binare. Dacă ridicați aleatoriu astfel de mesaje binare care în total vor fi egale și distribuiți aceste mesaje între toți membrii grupului, se dovedește că va fi posibil să citiți mesajul numai dacă toți membrii grupului se reunesc [1] . $t$ $s$ $n$ $s_{1},\ldots ,s_{t)$ $s$

Există o problemă semnificativă într-o astfel de schemă: în cazul pierderii a cel puțin unuia dintre membrii grupului, secretul se va pierde iremediabil pentru întregul grup.

Schema de prag

Spre deosebire de procedura de împărțire a secretelor, în care , în procedura de împărțire a secretelor, numărul de acțiuni care sunt necesare pentru a restabili secretul poate diferi de câte acțiuni este împărțit secretul. O astfel de schemă se numește schema de prag , unde este numărul de acțiuni în care a fost împărțit secretul și este numărul de acțiuni care sunt necesare pentru a restabili secretul. Ideile de circuite au fost propuse independent în 1979 de Adi Shamir și George Blakley . În plus, proceduri similare au fost studiate de Gus Simmons [3] [4] [5] . $t=n$ $\left(t, n\dreapta)$ $n$ $t$ $t \neq n$

Dacă coaliția de participanți este de așa natură încât au suficiente acțiuni pentru a restabili secretul, atunci coaliția se numește rezolvată. Schemele de partajare a secretelor în care coalițiile permise de participanți pot recupera secretul în mod unic, iar cele nerezolvate nu primesc nicio informație a posteriori despre valoarea posibilă a secretului, sunt numite perfecte [6] .

Schema lui Shamir

Ideea diagramei este că două puncte sunt suficiente pentru a defini o linie dreaptă , trei puncte sunt suficiente pentru a defini o parabolă , patru puncte sunt suficiente pentru a defini o parabolă cubică și așa mai departe. Pentru a specifica un polinom de grad , sunt necesare puncte . $k$ $k+1$

Pentru ca secretul să fie restaurat numai de către participanți după separare, acesta este „ascuns” în formula unui polinom de grade peste un câmp finit . Pentru a restabili în mod unic acest polinom, este necesar să-i cunoașteți valorile în puncte și, folosind un număr mai mic de puncte, nu va fi posibilă restaurarea unică a polinomului original. 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). $k$ $(k-1)$ $G$ $k$ $G$

Pe scurt, acest algoritm poate fi descris după cum urmează. Să fie dat un câmp finit . Reparăm diverse elemente non-nule non-secrete ale acestui câmp. Fiecare dintre aceste elemente este atribuit unui anumit membru al grupului. În continuare, este selectat un set arbitrar de elemente ale câmpului , din care este compus un polinom peste un câmp de grad . După obținerea polinomului, calculăm valoarea acestuia în puncte nesecrete și raportăm rezultatele membrilor corespunzători ai grupului [1] . $G$ $n$ $t$ $G$ $f(x)$ $G$ $t-1,1<t\leq n$

Pentru a recupera secretul, puteți utiliza o formulă de interpolare , cum ar fi formula Lagrange .

Un avantaj important al schemei Shamir este că este ușor scalabilă [5] . Pentru a crește numărul de utilizatori dintr-un grup, este necesar doar să adăugați numărul corespunzător de elemente nesecrete la cele existente, iar condiția pentru trebuie să fie îndeplinită . În același timp, compromisul unei părți a secretului schimbă schema de la -threshold la -threshold. $r_{i}\neq r_{j)$ $i\neq j$ $(n,t)$ $(n-1,t-1)$

Schema lui Blackley

Două drepte neparalele dintr-un plan se intersectează într-un punct. Orice două plane necoplanare se intersectează într-o linie dreaptă și trei plane necoplanare din spațiu se intersectează, de asemenea, într-un punct. În general , n hiperplanuri n - dimensionale se intersectează întotdeauna într-un punct. Una dintre coordonatele acestui punct va fi secretă. Dacă secretul este codificat ca mai multe coordonate ale unui punct, atunci deja dintr-o parte a secretului (un hiperplan) va fi posibilă obținerea unor informații despre secret, adică despre interdependența coordonatelor punctului de intersecție.


Schema lui Blackley în trei dimensiuni: fiecare parte a secretului este un plan , iar secretul este una dintre coordonatele punctului de intersecție al planurilor. Două plane nu sunt suficiente pentru a determina punctul de intersecție.

Cu ajutorul schemei lui Blackley [4] , se poate crea o schemă de partajare (t, n) -secretă pentru orice t și n : pentru a face acest lucru, trebuie să folosiți dimensiunea spațiului egală cu t și să dați fiecăruia dintre cei n jucători un hiperplan care trece prin punctul secret. Atunci orice t din n hiperplane se va intersecta în mod unic într-un punct secret.

Schema lui Blackley este mai puțin eficientă decât schema lui Shamir: în schema lui Shamir fiecare acțiune are aceeași dimensiune ca și secretul, în timp ce în schema lui Blackley fiecare acțiune este de trei ori mai mare. Există îmbunătățiri ale schemei lui Blakely pentru a-i îmbunătăți eficiența.

Scheme bazate pe teorema chineză a restului

În 1983, Maurice Mignotte , Asmuth și Bloom au propus două scheme secrete de partajare bazate pe teorema chineză a restului . Pentru un anumit număr (în schema Mignotte acesta este secretul în sine, în schema Asmuth-Bloom este un număr derivat), resturile sunt calculate după împărțirea la o succesiune de numere, care sunt distribuite părților. Din cauza restricțiilor privind succesiunea numerelor, doar un anumit număr de părți poate recupera secretul [7] [8] .

Fie numărul de utilizatori din grup . În schema Mignotte, un anumit set de numere coprime în perechi este ales astfel încât produsul celor mai mari numere să fie mai mic decât produsul celui mai mic dintre aceste numere. Fie aceste produse egale și , respectiv. Numărul se numește pragul pentru schema construită peste mulțime . Ca secret, un număr este ales astfel încât relația să fie satisfăcută . Părți din secret sunt distribuite între membrii grupului după cum urmează: fiecărui membru i se dă o pereche de numere , unde . $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})$ $r_{i}\equiv S {\pmod {m_{i}}}$

Pentru a recupera secretul, trebuie să îmbinați fragmentele. În acest caz, obținem un sistem de comparații de forma , a cărui mulțime de soluții poate fi găsită folosind teorema chineză a restului . Numărul secret aparține acestui set și îndeplinește condiția . De asemenea, este ușor să arătați că, dacă numărul de fragmente este mai mic decât , atunci pentru a găsi secretul , este necesar să sortați ordinea numerelor întregi. Cu alegerea corectă a numerelor, o astfel de căutare este aproape imposibil de implementat. De exemplu, dacă adâncimea de biți este de la 129 la 130 de biți și , atunci raportul va fi de ordinul [9] . $t\geq k$ $x\equiv r_{i}{\pmod {m_{i)}}$ $S$ $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}$

Schema Asmuth-Bloom este o schemă Mignott modificată. Spre deosebire de schema Mignotte, ea poate fi construită în așa fel încât să fie perfectă [10] .

Scheme bazate pe rezolvarea sistemelor de ecuații

În 1983, Karnin, Green și Hellman au propus schema lor de partajare secretă , care se baza pe imposibilitatea de a rezolva un sistem cu necunoscute cu mai puține ecuații [11] . $m$ $m$

În cadrul acestei scheme, vectorii -dimensionali sunt aleși astfel încât orice matrice de dimensiune compusă din acești vectori să aibă rang . Fie vectorul să aibă dimensiunea . $n+1$ $m$ $V_{0},V_{1},...,V_{n)$ $m\times m$ $m$ $U$ $m$

Secretul din circuit este produsul matricei . Acțiunile secretului sunt lucrări . $U^{T}V_{0}$ $U^{T}V_{i},1\leq i\leq n$

Având orice acțiuni, este posibil să se compună un sistem de ecuații liniare de dimensiune , în care coeficienții sunt necunoscuți . Rezolvând acest sistem, puteți găsi , iar având , puteți găsi secretul. În acest caz, sistemul de ecuații nu are o soluție dacă cotele sunt mai mici decât [12] . $m$ $m\times m$ $U$ $U$ $U$ $m$

Modalități de a înșela schema de prag

Există mai multe moduri de a întrerupe protocolul circuitului de prag:

proprietarul uneia dintre acțiuni poate interfera cu restaurarea secretului împărtășit prin dăruirea acțiunii greșite (aleatorie) la momentul potrivit [13] .
un atacator, neavând o cotă, poate fi prezent la recuperarea secretului. După ce așteaptă anunțul numărului necesar de acțiuni, el restabilește rapid secretul pe cont propriu și generează o altă acțiune, după care o prezintă restului participanților. Drept urmare, el obține acces la secret și rămâne neprins [14] .

Există și alte posibilități de întrerupere care nu sunt legate de implementarea schemei:

un atacator poate simula o situație în care dezvăluirea unui secret este necesară, aflând astfel cotele participanților [14] .

Vezi și

Note

↑ 1 2 3 Alferov, Zubov, Kuzmin et al., 2002 , p. 401.
↑ Schoenmakers, 1999 .
↑ CJ Simmons. O introducere în secrete partajate și/sau scheme de control partajat și aplicarea acestora // Contemporary Cryptology. - IEEE Press, 1991. - P. 441-497 .
↑ 12 Blakley , 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. Criptografie aplicată. - Ed. a II-a. - Triumf, 2002. - S. 590. - 816 p. - ISBN 5-89392-055-4 .
↑ Pasailă, Alexa, Iftene, 2010 .
↑ 1 2 Schneier, 2002 , p. 69.

Literatură

Schneier B. 3.7. Partajare secretă // Criptografie aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - S. 93-96. — 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .
Schneier B. 23.2 Algoritmi de partajare secretă // Criptografie aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumf, 2002. - S. 588-591. — 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .

Blakley G. R. Safeguarding cryptographic keys (english) // Proceedings of the 1979 AFIPS National Computer Conference - Montvale : AFIPS Press , 1979. - P. 313-317. doi : 10.1109/AFIPS.1979.98
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
Mignotte M. How to Share a Secret (engleză) // Criptografie : Proceedings of the Workshop on Cryptography Burg Feuerstein, Germania, 29 martie–2 aprilie 1982 / T. Beth — Berlin , Heidelberg , New York, NY , Londra [ etc. .] : Springer Berlin Heidelberg , 1983. - P. 371-375. - ( Note de curs în Informatică ; Vol. 149) - ISBN 978-3-540-11993-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-39466-4_27
Asmuth C. , Bloom J. O abordare modulară a protejării cheilor // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1983. - Vol. 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. Despre sistemele de partajare secretă // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1983. - Vol. 29, Iss. 1. - P. 35-41. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056621
Blackley D. , Kabatyansky G. A. Scheme ideale generalizate care împărtășesc un secret și matroizi // Probl. transmiterea de informații - 1997. - T. 33, nr. 3. - S. 102-110.
Schoenmakers B. A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting // Advances in Cryptology — CRYPTO' 99 :19th Annual International Cryptology Conference Santa Barbara, California, USA, August 15–19, 1999 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. Fundamentele criptografiei : Manual - ed. a 2-a, Rev. si suplimentare - M .: Helios ARV , 2002. - ISBN 978-5-85438-137-6
Moldovyan N. A. , Moldovyan A. A. Introducere în criptosistemele cu cheie publică - Sankt Petersburg. : BHV-Petersburg , 2005. - 288 p. - ( Tutorial ) - ISBN 978-5-94157-563-3
Pasailă D. , Alexa V. , Iftene S. Cheating Detection and Cheater Identification in CRT-based Secret Sharing Schemes (english) // International Journal of Computing - 2010. - Vol. 9, Iss. 2. - P. 107-117. — ISSN 2312-5381 ; 1727-6209
Shenets N. N. On ideal modular secret sharing schemes in polynomial rings in several variables // Congresul Internațional de Informatică: Sisteme și Tehnologii Informaționale : materiale ale Congresului Științific Internațional 31 oct. - Minsk : BGU , 2011. - V. 1. Articole ale Facultății de Matematică Aplicată și Informatică. - S. 169-173. — ISBN 978-985-518-563-6