Dela en hemlighet

Hemlig delning är en term inom kryptografi , som förstås som någon av metoderna för att distribuera en hemlighet bland en grupp av deltagare, som var och en får sin egen viss andel. Hemligheten kan endast återskapas av en koalition av deltagare från den ursprungliga gruppen, och åtminstone något initialt känt antal av dem måste inkluderas i koalitionen.

System för hemlighetsdelning används i de fall där det finns en betydande sannolikhet för kompromiss från en eller flera hemlighetshållare, men sannolikheten för orättvis samverkan från en betydande del av deltagarna anses vara försumbar.

Befintliga system har två komponenter: hemlig delning och hemlig återställning. Att dela hänvisar till bildandet av delar av hemligheten och deras spridning bland medlemmarna i gruppen, vilket gör det möjligt att dela ansvaret för hemligheten mellan dess medlemmar. Det omvända schemat bör säkerställa att det återställs, under förutsättning att dess innehavare finns tillgängliga i ett visst erforderligt antal [1] .

Användningsfall: Secret Voting Protocol baserat på Secret Sharing [2] .

Det enklaste exemplet på ett hemligt delningsschema

Låt det finnas en grupp människor och ett meddelande av längd , bestående av binära tecken. Om du slumpmässigt plockar upp sådana binära meddelanden att de totalt blir lika med , och distribuerar dessa meddelanden bland alla medlemmar i gruppen, visar det sig att det kommer att vara möjligt att läsa meddelandet endast om alla medlemmar i gruppen samlas [1] . $t$ $s$ $n$ ${\displaystyle s_{1},\ldots ,s_{t))$ $s$

Det finns ett betydande problem i ett sådant system: i händelse av förlust av minst en av medlemmarna i gruppen, kommer hemligheten att gå förlorad för hela gruppen oåterkalleligt.

Tröskelschema

Till skillnad från det hemliga uppdelningsförfarandet, där , i det hemliga uppdelningsförfarandet, kan antalet aktier som behövs för att återställa hemligheten skilja sig från hur många aktier hemligheten är uppdelad i. Ett sådant system kallas tröskelsystemet , där är antalet aktier som hemligheten delades upp i, och är antalet aktier som behövs för att återställa hemligheten. Kretsidéer föreslogs oberoende 1979 av Adi Shamir och George Blakley . Dessutom studerades liknande procedurer av Gus Simmons [3] [4] [5] . $t=n$ $\left( t, n\right)$ $n$ $t$ $t \neq n$

Om koalitionen av deltagare är sådan att de har tillräckligt med aktier för att återställa hemligheten, kallas koalitionen tillåten. Hemliga delningsscheman där tillåtna koalitioner av deltagare unikt kan återställa hemligheten, och olösta sådana inte får någon information i efterhand om hemlighetens möjliga värde, kallas perfekta [6] .

Shamirs schema

Tanken med diagrammet är att två punkter räcker för att definiera en rät linje , tre punkter räcker för att definiera en parabel , fyra punkter räcker för att definiera en kubisk parabel , och så vidare. För att ange ett gradpolynom krävs poäng . $k$ $k+1$

För att hemligheten endast ska återställas av deltagarna efter separation, är den "gömd" i formeln för ett gradpolynom över ett ändligt fält . För att unikt återställa detta polynom är det nödvändigt att känna till dess värden vid punkter, och med ett mindre antal punkter kommer det inte att vara möjligt att unikt återställa det ursprungliga polynomet. Antalet olika punkter i polynomet är inte begränsat (i praktiken begränsas det av storleken på det numeriska fältet där beräkningar utförs). $k$ $(k-1)$ $G$ $k$ $G$

I korthet kan denna algoritm beskrivas enligt följande. Låt ett ändligt fält ges . Vi fixar olika icke-noll icke-hemliga element i detta fält. Var och en av dessa element tillskrivs en specifik medlem i gruppen. Därefter väljs en godtycklig uppsättning element i fältet , från vilken ett polynom över ett gradfält är sammansatt . Efter att ha erhållit polynomet beräknar vi dess värde vid icke-hemliga punkter och rapporterar resultaten till motsvarande medlemmar i gruppen [1] . $G$ $n$ $t$ $G$ $f(x)$ $G$ $t-1,1<t\leq n$

För att återställa hemligheten kan du använda en interpolationsformel , till exempel Lagrange- formeln .

En viktig fördel med Shamir-schemat är att det är lätt skalbart [5] . För att öka antalet användare i en grupp är det bara nödvändigt att lägga till motsvarande antal icke-hemliga element till de befintliga, och villkoret för måste vara uppfyllt . Samtidigt ändrar kompromiss av en del av hemligheten schemat från -tröskel till -tröskel. ${\displaystyle r_{i}\neq r_{j))$ $i\neq j$ $(n,t)$ $(n-1,t-1)$

Blackleys schema

Två icke-parallella linjer i ett plan skär varandra vid en punkt. Alla två icke-koplanära plan skär varandra i en rät linje, och tre icke-samplanära plan i rymden skär också i en punkt. I allmänhet skär n n -dimensionella hyperplan alltid vid en punkt. En av koordinaterna för denna punkt kommer att vara en hemlighet. Om hemligheten är kodad som flera koordinater för en punkt, kommer det redan från en del av hemligheten (ett hyperplan) att vara möjligt att få viss information om hemligheten, det vill säga om det ömsesidiga beroendet mellan koordinaterna för skärningspunkten.


Blackleys schema i tre dimensioner: varje del av hemligheten är ett plan , och hemligheten är en av koordinaterna för planens skärningspunkt. Två plan räcker inte för att bestämma skärningspunkten.

Med hjälp av Blackleys schema [4] kan man skapa ett (t, n) -hemligt delningsschema för vilket t och n som helst : för att göra detta måste man använda rymddimensionen lika med t , och ge var och en av de n spelarna ett hyperplan som passerar genom den hemliga punkten. Då kommer vilket t av n hyperplan som helst att skära varandra vid en hemlig punkt.

Blackleys system är mindre effektivt än Shamirs system: i Shamirs system är varje aktie lika stor som hemligheten, medan i Blackleys system är varje aktie t gånger större. Det finns förbättringar av Blakelys system för att förbättra dess effektivitet.

Schema baserade på den kinesiska restsatsen

År 1983 föreslog Maurice Mignotte , och Bloom två hemliga delningsscheman baserade på den kinesiska restsatsen . För ett visst tal (i Mignotte-schemat är detta hemligheten i sig, i Asmuth-Bloom- schemat är det något derivatnummer) beräknas resten efter att ha dividerat med en talföljd, som delas ut till parterna. På grund av begränsningar av nummersekvensen kan endast ett visst antal parter återfå hemligheten [7] [8] .

Låt antalet användare i gruppen vara . I Mignotte-schemat väljs en viss uppsättning parvisa samprimtal så att produkten av de största talen är mindre än produkten av det minsta av dessa tal. Låt dessa produkter vara lika och , respektive. Numret kallas tröskeln för det konstruerade schemat över uppsättningen . Som en hemlighet väljs ett nummer så att relationen är uppfylld . Delar av hemligheten fördelas bland gruppmedlemmarna enligt följande: varje medlem får ett par nummer , där . $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))))$

För att återställa hemligheten måste du slå samman fragmenten. I det här fallet får vi ett system av jämförelser av formen , vars uppsättning lösningar kan hittas med hjälp av den kinesiska restsatsen . Det hemliga numret tillhör denna uppsättning och uppfyller villkoret . Det är också lätt att visa att om antalet fragment är mindre än , då för att hitta hemligheten , är det nödvändigt att sortera genom heltalsordningen. Med rätt val av nummer är en sådan sökning nästan omöjlig att genomföra. Till exempel, om bitdjupet är från 129 till 130 bitar, och , kommer förhållandet att vara av storleksordningen [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}}$ $mi$ $mi$ $k<15$ ${\frac {N}{M}}$ $2^{100}$

Asmuth-Bloom-schemat är ett modifierat Mignott-schema. Till skillnad från Mignotte-schemat kan det konstrueras på ett sådant sätt att det är perfekt [10] .

Schema baserade på att lösa ekvationssystem

1983 föreslog Karnin, Green och Hellman sitt hemliga delningsschema , som var baserat på omöjligheten att lösa ett system med okända med färre ekvationer [11] . $m$ $m$

Inom ramen för detta schema väljs dimensionella vektorer så att vilken storleksmatris som helst som består av dessa vektorer har rang . Låt vektorn ha dimension . $n+1$ $m$ ${\displaystyle V_{0},V_{1},...,V_{n))$ $m\times m$ $m$ $U$ $m$

Hemligheten i kretsen är matrisprodukten . Hemlighetens andelar är verk . $U^{T}V_{0}$ $U^{T}V_{i},1\leq i\leq n$

Med några aktier är det möjligt att komponera ett system av linjära dimensionsekvationer , där koefficienterna är okända . Genom att lösa detta system kan du hitta , och med , kan du hitta hemligheten. I det här fallet har ekvationssystemet ingen lösning om andelarna är mindre än [12] . $m$ $m\times m$ $U$ $U$ $U$ $m$

Sätt att lura tröskelschemat

Det finns flera sätt att bryta protokollet för tröskelkretsen:

ägaren till en av aktierna kan störa återställandet av den delade hemligheten genom att ge bort fel (slumpmässig) andel vid rätt tidpunkt [13] .
en angripare, som inte har en del, kan vara närvarande vid återvinningen av hemligheten. Efter att ha väntat på tillkännagivandet om det nödvändiga antalet aktier återställer han snabbt hemligheten på egen hand och genererar ytterligare en aktie, varefter han presenterar den för resten av deltagarna. Som ett resultat får han tillgång till hemligheten och förblir ofrånkomlig [14] .

Det finns också andra möjligheter till avbrott som inte är relaterade till genomförandet av systemet:

en angripare kan simulera en situation där avslöjande av en hemlighet är nödvändig och därigenom ta reda på deltagares andelar [14] .

Se även

Anteckningar

↑ 1 2 3 Alferov, Zubov, Kuzmin et al., 2002 , sid. 401.
↑ Schoenmakers, 1999 .
↑ CJ Simmons. En introduktion till delade hemliga och/eller delade kontrollscheman och deras tillämpning // 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 , sid. 225.
↑ Shenets, 2011 .
↑ Karnin, Greene, Hellman, 1983 .
↑ Schneier B. Tillämpad kryptografi. - 2:a uppl. - Triumph, 2002. - S. 590. - 816 sid. - ISBN 5-89392-055-4 .
↑ Pasailă, Alexa, Iftene, 2010 .
↑ 1 2 Schneier, 2002 , sid. 69.

Litteratur

Schneier B. 3.7. Hemlig delning // Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code i C. - M . : Triumph, 2002. - S. 93-96. — 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .
Schneier B. 23.2 Algoritmer för hemlig delning // Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code i C. - M . : Triumf, 2002. - S. 588-591. — 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .

Blakley G. R. Safeguarding cryptographic keys (engelska) // Proceedings of the 1979 AFIPS National Computer Conference - Montvale : AFIPS Press , 1979. - P. 313-317. doi : 10.1109/AFIPS.1979.98
Shamir A. Hur man delar en hemlighet // 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 (engelska) // Cryptography : Proceedings of the Workshop on Cryptography Burg Feuerstein, Tyskland, 29 mars–2 april 1982 / T. Beth — Berlin , Heidelberg , New York, NY , London [ etc. .] : Springer Berlin Heidelberg , 1983. - P. 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. Ett modulärt tillvägagångssätt för nyckelskydd // IEEE Trans . inf. Theory / 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. On Secret Sharing Systems // IEEE Trans . inf. Theory / 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. Generaliserade idealscheman som delar en hemlighet och matroider // Probl. överföring av information - 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, Kalifornien, USA, 15–19 augusti, 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 : Textbook - 2nd ed., Rev. och ytterligare - M .: Helios ARV , 2002. - ISBN 978-5-85438-137-6
Moldovyan N. A. , Moldovyan A. A. Introduktion till kryptosystem för offentliga nyckel - St. Petersburg. : BHV-Petersburg , 2005. - 288 sid. - ( Handledning ) - ISBN 978-5-94157-563-3
Pasailă D. , Alexa V. , Iftene S. Fuskupptäckt och fuskidentifiering i CRT-baserade hemliga delningsscheman (engelska) // International Journal of Computing - 2010. - Vol. 9, Iss. 2. - S. 107-117. — ISSN 2312-5381 ; 1727-6209
Shenets N. N. Om idealiska modulära hemlighetsdelningsscheman i polynomringar i flera variabler // International Congress on Informatics: Information Systems and Technologies : material of the International Scientific Congress 31 okt. - Minsk : BGU , 2011. - V. 1. Artiklar från fakulteten för tillämpad matematik och informatik. - S. 169-173. — ISBN 978-985-518-563-6