Schema vectorială de partajare secretă

O schemă de partajare secretă vectorială , sau schema lui Blakley , este o schemă de partajare secretă între părți, bazată pe utilizarea punctelor într-un spațiu multidimensional. Propus de George Blackley în 1979 . Schema lui Blakely vă permite să creați ( t , n )-prag de partajare secretă pentru orice t , n .

Idee

Secretul împărtășit în schema lui Blackley este una dintre coordonatele punctului din spațiul -dimensional. Părțile secretului dat părților sunt ecuațiile hiperplanurilor dimensionale . Pentru a restabili un punct, este necesar să se cunoască ecuațiile hiperplanelor. Mai puțin de două părți nu pot recupera secretul, deoarece setul de intersecție al avioanelor este o linie, iar secretul nu poate fi recuperat. $m$ $(m-1)$ $m$ $m$ $m-1$


Un exemplu de 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.

Trebuie remarcat faptul că descrierea geometrică și ilustrațiile sunt date pentru a înțelege ideea principală a schemei. Cu toate acestea, procesul de partajare a secretelor în sine are loc în câmpuri finite folosind un aparat matematic similar, dar diferit.

Descriere

Generarea punctelor

Să fie necesară implementarea unei scheme -threshold, adică împărțirea secretului între părți, astfel încât oricare dintre ele să poată restabili secretul. Pentru a face acest lucru, se alege un număr prim mare , modulo căruia va fi construit câmpul . Dealer aleatoriu $(k,n)$ $M$ $n$ $k$ $p>M$ $GF(p)$ [ cine? ] selectează numere . Aceasta stabilește un punct în spațiul -dimensional, a cărui primă coordonată este un secret. $b_{2},\puncte,b_{k}\în GF(p)$ $(M,b_{2},\dots,b_{k})$ $k$

Partajarea unui secret

Pentru fiecare parte , coeficienții selectați aleatoriu sunt distribuiți uniform pe teren . Deoarece ecuația planului are forma , pentru fiecare latură este necesar să se calculeze coeficienții : $P_{i},i=(1,\dots,n)$ $a_{{1i}},a_{{2i}},\dots ,a_{{ki}}$ $GF(p)$ $a_{1i}\cdot x_{1}+a_{2i}\cdot x_{2}+\dots +a_{ki}\cdot x_{k}+d_{i}=0$ $d_{i}$

{\begin{aligned}d_{1}&=-(a_{11}\cdot M+a_{21}\cdot b_{2}+\dots +a_{k1}\cdot b_{k}) {\bmod {p)),\\d_{2}&=-(a_{12}\cdot M+a_{22}\cdot b_{2}+\dots +a_{k2}\cdot b_{k} ){\bmod {p)),\\&~\vdots \\d_{i}&=-(a_{1i}\cdot M+a_{2i}\cdot b_{2}+\dots +a_{ki }\cdot b_{k}){\bmod {p)),\\&~\vdots \\d_{n}&=-(a_{1n}\cdot M+a_{2n}\cdot b_{2} +\dots +a_{kn}\cdot b_{k}){\bmod {p}}.\\\end{aligned}}

În acest caz, este necesar să se asigure că orice ecuații sunt liniar independente. Ca părți ale secretului, părților li se oferă un set de coeficienți care definesc ecuația hiperplanului. $k$

Restaurarea secretului

Pentru a restabili secretul, orice părți trebuie să se reunească și să folosească părțile disponibile ale secretului pentru a face ecuații pentru a găsi punctul de intersecție al hiperplanelor: $k$

\left\{{\begin{aligned}(a_{11}\cdot x_{1}+a_{21}\cdot x_{2}+\dots +a_{k1}\cdot x_{k}+ d_{1}){\bmod {p}}&=0,\\(a_{12}\cdot x_{1}+a_{22}\cdot x_{2}+\dots +a_{k2}\cdot x_{k}+d_{2}){\bmod {p}}&=0,\\&\vdots \\(a_{1k}\cdot x_{1}+a_{2k}\cdot x_{2} +\dots +a_{kk}\cdot x_{k}+d_{k}){\bmod {p}}&=0.\\\end{aliniat}}\right.

Soluția sistemului dă un punct în spațiul -dimensional, a cărui primă coordonată este secretul comun. Sistemul poate fi rezolvat prin orice metodă cunoscută, de exemplu, prin metoda Gauss , dar este necesar să se efectueze calcule în teren . $k$ $GF(p)$

Dacă numărul de participanți la întâlnire este mai mic de , de exemplu, , atunci rezultatul rezolvării sistemului de ecuații, compus din setul disponibil de coeficienți, va fi o linie dreaptă în spațiu -dimensional. Astfel, setul de valori secrete permise care satisfac sistemul rezultat se potrivește exact cu numărul total de elemente ale câmpului , iar secretul poate lua orice valoare din acest câmp cu probabilitate egală. Astfel, participanții, strânși împreună, nu vor primi informații noi despre secretul partajat. $k$ $k-1$ $k$ $GF(p)$

Proprietăți

Schema imperfectă : Numărul de participanți va crește, numărul de posibilități pentru punctul secret va scădea. De exemplu, pentru t − 1 participanții cunosc linia care conține punctul secret.

Circuitul compartimentelor : Participanții sunt împărțiți în subgrupe numite compartimente. Pentru a primi un secret, este necesar un cvorum de sloturi, dar pentru ca un slot să participe la un cvorum, este necesar un alt cvorum de acțiuni.

Scheme pe niveluri: Participanții sunt împărțiți în două niveluri ordonate. Pentru a restabili un secret, este necesar un cvorum mai mic la un nivel superior. În plus, fiecare membru de nivel superior poate înlocui membrii de nivel inferior.

Unii participanți nu pot obține secretul.

Exemplu

Să fie necesar să partajați secretul „6” între 4 părți, în timp ce oricare 3 ar trebui să îl poată restaura. Cu alte cuvinte, este necesar să se implementeze -threshold secret sharing. $(3,4)$

Pentru a face acest lucru, să setăm un punct în spațiul tridimensional, de exemplu, . Prima coordonată a punctului este secretul partajat, 4 și 2 sunt numere aleatorii. În acest caz, vom lucra în câmpul , adică toate numerele vor fi calculate ca restul împărțirii cu . $(6,4,2)$ $GF(11)$ $p=11$

Fiecare latură trebuie să primească o ecuație pentru un plan care trece printr-un punct dat. În spațiul tridimensional, ecuația unui plan este specificată folosind 4 parametri: , unde sunt coordonatele și sunt parametrii repartizați pe laturi. Pentru a selecta parametrii, puteți proceda după cum urmează: selectați valorile aleatoriu (în acest caz, este necesar ca planurile rezultate să nu se dovedească a fi coplanare ) și calculați coeficientul liber pentru fiecare latură folosind un punct dat și coeficienții selectați. $a_{1}\cdot x_{1}+a_{2}\cdot x_{2}+a_{3}\cdot x_{3}+d=0$ $x_{1},x_{2},x_{3}$ $(a_{1},a_{2},a_{3},d)$ $(a_{1},a_{2},a_{3})$

De exemplu, să alegem parametrii după cum urmează:

Partea 1: ,

(4,8,2,d_{1})

A doua parte: ,

(2,6,8,d_{2})

partea a 3-a: ,

(6,8,4,d_{3})

Partea a 4-a: .

(3,10,1,d_{4})

Pentru a calcula parametrii necunoscuți, folosim valorile coordonatelor punctului selectat: $d$

{\begin{aligned}d_{1}&=-(4\cdot 6+8\cdot 4+2\cdot 2){\bmod {1}}1=6,\\d_{2}& =-(2\cdot 6+6\cdot 4+8\cdot 2){\bmod {1}}1=3,\\d_{3}&=-(6\cdot 6+8\cdot 4+4 \cdot 2){\bmod {1}}1=1,\\d_{4}&=-(3\cdot 6+10\cdot 4+1\cdot 2){\bmod {1}}1=6 .\\\end{aliniat}}

După aceea, părțile din secret, împreună cu numărul , sunt distribuite părților. $p=11$

Pentru a restabili secretul, oricare trei participanți trebuie să găsească punctul de intersecție al planurilor ale căror ecuații au fost date. De exemplu, primele trei părți care recuperează secretul vor trebui să rezolve sistemul de ecuații

\left\{{\begin{aligned}(4\cdot x_{1}+8\cdot x_{2}+2\cdot x_{3}+6){\bmod {1}}1=0 ,\\(2\cdot x_{1}+6\cdot x_{2}+8\cdot x_{3}+3){\bmod {1}}1=0,\\(6\cdot x_{1 }+8\cdot x_{2}+4\cdot x_{3}+1){\bmod {1}}1=0.\\\end{aliniat}}\right.

Sistemul poate fi rezolvat în orice mod, fără a uita că calculele sunt efectuate în teren . Este ușor să vă asigurați că punctul este soluția sistemului, prima sa coordonată „6” este secretul partajat. $GF(11)$ $(6,4,2)$

Literatură

Schneier B. 23.2 Algoritmi pentru partajarea unui secret. Schemă vectorială // Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - S. 589. - 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