Deler en hemmelighed

Hemmelig deling er et begreb i kryptografi , der forstås som enhver af metoderne til at distribuere en hemmelighed blandt en gruppe deltagere, som hver får sin egen bestemte andel. Hemmeligheden kan kun genskabes af en koalition af deltagere fra den oprindelige gruppe, og i det mindste et oprindeligt kendt antal af dem skal inkluderes i koalitionen.

Hemmelige deleordninger anvendes i tilfælde, hvor der er en betydelig sandsynlighed for kompromittering af en eller flere hemmelige vogtere, men sandsynligheden for illoyal samordning fra en væsentlig del af deltagerne anses for at være ubetydelig.

Eksisterende ordninger har to komponenter: hemmelig deling og hemmelig gendannelse. Deling refererer til dannelsen af dele af hemmeligheden og deres fordeling blandt medlemmerne af gruppen, hvilket gør det muligt at dele ansvaret for hemmeligheden mellem dens medlemmer. Den omvendte ordning bør sikre dens genoprettelse, afhængigt af tilgængeligheden af dens brugere i et vist påkrævet antal [1] .

Use Case: hemmelig afstemningsprotokol baseret på hemmelig deling [2] .

Det enkleste eksempel på et hemmeligt delingsskema

Lad der være en gruppe mennesker og et budskab af længde , bestående af binære tegn. Hvis du tilfældigt opfanger sådanne binære beskeder , at de i alt er lig med , og fordeler disse beskeder blandt alle medlemmer af gruppen, viser det sig, at det kun vil være muligt at læse beskeden, hvis alle medlemmer af gruppen samles [1] . $t$ $s$ $n$ ${\displaystyle s_{1},\ldots ,s_{t))$ $s$

Der er et betydeligt problem i en sådan ordning: i tilfælde af tab af mindst et af medlemmerne af gruppen, vil hemmeligheden gå tabt for hele gruppen uigenkaldeligt.

Tærskelskema

I modsætning til den hemmelige spaltningsprocedure, hvor , i den hemmelige spaltningsprocedure, kan antallet af aktier, der skal til for at genoprette hemmeligheden, afvige fra hvor mange andele hemmeligheden er opdelt i. En sådan ordning kaldes tærskelordningen , hvor er antallet af aktier, som hemmeligheden blev opdelt i, og er antallet af aktier, der skal til for at genoprette hemmeligheden. Kredsløbsideer blev uafhængigt foreslået i 1979 af Adi Shamir og George Blakley . Derudover blev lignende procedurer undersøgt af Gus Simmons [3] [4] [5] . $t=n$ $\venstre( t, n\højre)$ $n$ $t$ $t \neq n$

Hvis koalitionen af deltagere er sådan, at de har nok aktier til at genoprette hemmeligheden, kaldes koalitionen tilladt. Hemmelige deleordninger, hvor tilladte koalitioner af deltagere entydigt kan genvinde hemmeligheden, og uafklarede ikke modtager nogen efterfølgende information om hemmelighedens mulige værdi, kaldes perfekte [6] .

Shamirs plan

Ideen med diagrammet er, at to punkter er nok til at definere en ret linje , tre punkter er nok til at definere en parabel , fire punkter er nok til at definere en kubisk parabel , og så videre. For at angive et gradpolynomium kræves der point . $k$ $k+1$

For at hemmeligheden kun skal genoprettes af deltagerne efter adskillelse, er den "gemt" i formlen for et gradpolynomium over et begrænset felt . For entydigt at gendanne dette polynomium er det nødvendigt at kende dets værdier ved punkter, og ved at bruge et mindre antal punkter vil det ikke være muligt at gendanne det originale polynomium entydigt. Antallet af forskellige punkter i polynomiet er ikke begrænset (i praksis er det begrænset af størrelsen af det numeriske felt , hvori beregningerne udføres). $k$ $(k-1)$ $G$ $k$ $G$

Kort fortalt kan denne algoritme beskrives som følger. Lad et endeligt felt være givet . Vi reparerer forskellige ikke-nul ikke-hemmelige elementer i dette felt. Hvert af disse elementer tilskrives et bestemt medlem af gruppen. Dernæst vælges et vilkårligt sæt af elementer i feltet , hvorfra et polynomium over et gradfelt er sammensat . Efter at have opnået polynomiet, beregner vi dets værdi ved ikke-hemmelige punkter og rapporterer resultaterne til de tilsvarende medlemmer af gruppen [1] . $G$ $n$ $t$ $G$ $f(x)$ $G$ $t-1,1<t\leq n$

For at gendanne hemmeligheden kan du bruge en interpolationsformel , såsom Lagrange- formlen .

En vigtig fordel ved Shamir-ordningen er, at den er let skalerbar [5] . For at øge antallet af brugere i en gruppe er det kun nødvendigt at tilføje det tilsvarende antal ikke-hemmelige elementer til de eksisterende, og betingelsen for skal være opfyldt . Samtidig ændrer kompromittering af en del af hemmeligheden ordningen fra -tærskel til -tærskel. ${\displaystyle r_{i}\neq r_{j))$ $i\neq j$ $(n,t)$ $(n-1,t-1)$

Blackleys plan

To ikke-parallelle linjer i et plan skærer hinanden i et punkt. Alle to ikke-koplanære planer skærer hinanden i en lige linje, og tre ikke-koplanære planer i rummet skærer også hinanden i et punkt. Generelt skærer n n - dimensionelle hyperplaner altid et punkt. En af koordinaterne for dette punkt vil være en hemmelighed. Hvis hemmeligheden er kodet som flere koordinater af et punkt, vil det allerede fra én del af hemmeligheden (et hyperplan) være muligt at få nogle oplysninger om hemmeligheden, det vil sige om den indbyrdes afhængighed af koordinaterne til skæringspunktet.


Blackleys skema i tre dimensioner: hver del af hemmeligheden er et plan , og hemmeligheden er en af koordinaterne for flyernes skæringspunkt. To planer er ikke nok til at bestemme skæringspunktet.

Ved hjælp af Blackleys skema [4] kan man skabe et (t, n) -hemmeligt delingsskema for enhver t og n : for at gøre dette skal man bruge rumdimensionen lig med t , og give hver af de n spillere ét hyperplan, der passerer gennem det hemmelige punkt. Så vil enhver t af n hyperplaner entydigt skære hinanden ved et hemmeligt punkt.

Blackleys ordning er mindre effektiv end Shamirs ordning: I Shamirs ordning har hver aktie samme størrelse som hemmeligheden, mens hver aktie i Blackleys ordning er t gange større. Der er forbedringer til Blakelys plan for at forbedre effektiviteten.

Skemaer baseret på den kinesiske restsætning

I 1983 foreslog Maurice Mignotte , Asmuth og Bloom to hemmelige deleplaner baseret på den kinesiske restsætning . For et bestemt tal (i Mignotte-skemaet er dette selve hemmeligheden, i Asmuth-Bloom- skemaet er det et eller andet afledt tal), beregnes resten efter at have divideret med en talrække, som fordeles til parterne. På grund af begrænsninger på rækkefølgen af numre kan kun et vist antal parter genfinde hemmeligheden [7] [8] .

Lad antallet af brugere i gruppen være . I Mignotte-skemaet vælges et bestemt sæt parvise coprimtal således , at produktet af de største tal er mindre end produktet af det mindste af disse tal. Lad disse produkter være lige og hhv. Nummeret kaldes tærsklen for det konstruerede skema over sættet . Som en hemmelighed vælges et tal således, at relationen er opfyldt . Dele af hemmeligheden fordeles blandt gruppemedlemmerne som følger: Hvert medlem får et par tal , hvor . $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})$ ${\displaystyle r_{i}\equiv S{\pmod {m_{i))))$

For at gendanne hemmeligheden skal du flette fragmenterne. I dette tilfælde får vi et system af sammenligninger af formen , hvis sæt af løsninger kan findes ved hjælp af den kinesiske restsætning . Det hemmelige nummer hører til dette sæt og opfylder betingelsen . Det er også let at vise, at hvis antallet af fragmenter er mindre end , så for at finde hemmeligheden , er det nødvendigt at sortere i rækkefølgen af heltal. Med det rigtige valg af tal er en sådan søgning næsten umulig at implementere. For eksempel, hvis bitdybden er fra 129 til 130 bit, og , så vil forholdet være af størrelsesordenen [9] . $t\geq k$ ${\displaystyle x\equiv r_{i}{\pmod {m_{i))))$ $S$ ${\displaystyle 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}$

Asmuth-Bloom-ordningen er en modificeret Mignott-ordning. I modsætning til Mignotte-skemaet kan det konstrueres på en sådan måde, at det er perfekt [10] .

Skemaer baseret på løsning af ligningssystemer

I 1983 foreslog Karnin, Green og Hellman deres hemmelige delingsskema , som var baseret på umuligheden af at løse et system med ukendte med færre ligninger [11] . $m$ $m$

Inden for rammerne af dette skema vælges dimensionelle vektorer således, at enhver matrix af størrelse sammensat af disse vektorer har rang . Lad vektoren have dimension . $n+1$ $m$ ${\displaystyle V_{0},V_{1},...,V_{n))$ $m\times m$ $m$ $U$ $m$

Hemmeligheden i kredsløbet er matrixproduktet . Hemmelighedens aktier er værker . $U^{T}V_{0}$ $U^{T}V_{i},1\leq i\leq n$

Med nogen aktier, er det muligt at sammensætte et system af lineære dimensionsligninger , hvor koefficienterne er ukendte . Ved at løse dette system kan du finde , og have , du kan finde hemmeligheden. I dette tilfælde har ligningssystemet ikke en løsning, hvis andele er mindre end [12] . $m$ $m\times m$ $U$ $U$ $U$ $m$

Måder at snyde tærskelordningen

Der er flere måder at bryde protokollen for tærskelkredsløbet på:

ejeren af en af aktierne kan blande sig i genoprettelsen af den delte hemmelighed ved at give den forkerte (tilfældige) andel væk på det rigtige tidspunkt [13] .
en angriber, der ikke har en andel, kan være til stede ved gendannelsen af hemmeligheden. Efter at have ventet på meddelelsen om det nødvendige antal aktier, genopretter han hurtigt hemmeligheden på egen hånd og genererer endnu en aktie, hvorefter han præsenterer den for resten af deltagerne. Som et resultat får han adgang til hemmeligheden og forbliver ufanget [14] .

Der er også andre afbrydelsesmuligheder, som ikke er relateret til implementeringen af ordningen:

en angriber kan simulere en situation, hvor afsløring af en hemmelighed er nødvendig, og derved finde ud af deltagernes andele [14] .

Se også

Noter

↑ 1 2 3 Alferov, Zubov, Kuzmin et al., 2002 , s. 401.
↑ Schoenmakers, 1999 .
↑ CJ Simmons. En introduktion til delte hemmelige og/eller delte kontrolsystemer og deres anvendelse // 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 , s. 225.
↑ Shenets, 2011 .
↑ Karnin, Greene, Hellman, 1983 .
↑ Schneier B. Anvendt kryptografi. - 2. udg. - Triumph, 2002. - S. 590. - 816 s. - ISBN 5-89392-055-4 .
↑ Pasailă, Alexa, Iftene, 2010 .
↑ 1 2 Schneier, 2002 , s. 69.

Litteratur

Schneier B. 3.7. Hemmelig deling // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumph, 2002. - S. 93-96. — 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Schneier B. 23.2 Algoritmer til hemmelig deling // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumf, 2002. - S. 588-591. — 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .

Blakley G. R. Safeguarding cryptographic keys (engelsk) // Proceedings of the 1979 AFIPS National Computer Conference - Montvale : AFIPS Press , 1979. - P. 313-317. doi : 10.1109/AFIPS.1979.98
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
Mignotte M. How to Share a Secret (engelsk) // Cryptography : Proceedings of the Workshop on Cryptography Burg Feuerstein, Tyskland, 29. marts–2. april 1982 / T. Beth — Berlin , Heidelberg , New York, NY , London [ osv . .] : Springer Berlin Heidelberg , 1983. - S. 371-375. - ( Lecture Notes in Computer Science ; 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. En modulær tilgang til nøglesikring // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1983. - Vol. 29, Iss. 2. - S. 208-210. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056651
Karnin E. D. , Greene J. W. , Hellman M. E. On Secret Sharing Systems // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1983. - Vol. 29, Iss. 1. - S. 35-41. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056621
Blackley D. , Kabatyansky G. A. Generaliserede ideelle planer, der deler en hemmelighed og matroider // Probl. overførsel af information - 1997. - T. 33, no. 3. - S. 102-110.
Schoenmakers B. A Simple Publicly Verificable Secret Sharing Scheme and its application to Electronic Voting // Advances in Cryptology — CRYPTO' 99 :19th Annual International Cryptology Conference Santa Barbara, Californien, USA, 15.-19. august 1999 Proceedings / M. Wiener - Springer Berlin Heidelberg , 1999. - S. 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. Fundamentals of cryptography : Lærebog - 2. udgave, Rev. og yderligere - M .: Helios ARV , 2002. - ISBN 978-5-85438-137-6
Moldovyan N. A. , Moldovyan A. A. Introduktion til offentlige nøglekryptosystemer - St. Petersborg. : BHV-Petersburg , 2005. - 288 s. - ( Selvstudium ) - ISBN 978-5-94157-563-3
Pasailă D. , Alexa V. , Iftene S. Snyddetektion og snyderidentifikation i CRT-baserede hemmelige delingsskemaer (engelsk) // International Journal of Computing - 2010. - Vol. 9, Iss. 2. - S. 107-117. — ISSN 2312-5381 ; 1727-6209
Shenets N. N. Om ideelle modulære hemmelige deleskemaer i polynomialringe i flere variabler // International Congress on Informatics: Information Systems and Technologies : Materials of the International Scientific Congress 31. okt. - Minsk : BGU , 2011. - V. 1. Artikler fra Fakultetet for Anvendt Matematik og Informatik. - S. 169-173. — ISBN 978-985-518-563-6