Sdílení tajemství

Tajné sdílení je termín v kryptografii , který je chápán jako jakákoliv metoda distribuce tajemství mezi skupinu účastníků, z nichž každý dostane svůj určitý podíl. Tajemství může být znovu vytvořeno pouze koalicí účastníků z původní skupiny a alespoň nějaký původně známý počet z nich musí být zahrnut do koalice.

Schémata tajného sdílení se používají v případech, kdy existuje značná pravděpodobnost kompromitace jednoho nebo více držitelů tajemství, ale pravděpodobnost nekalé tajné dohody ze strany významné části účastníků je považována za zanedbatelnou.

Stávající schémata mají dvě složky: tajné sdílení a tajné obnovení. Sdílením se rozumí vytváření částí tajemství a jejich distribuce mezi členy skupiny, což umožňuje sdílet odpovědnost za tajemství mezi jejími členy. Inverzní schéma by mělo zajistit jeho obnovu za předpokladu, že jeho držitelé budou k dispozici v určitém požadovaném počtu [1] .

Use Case: Secret Voting Protocol založený na Secret Sharing [2] .

Nejjednodušší příklad tajného schématu sdílení

Nechť existuje skupina lidí a zpráva délky , skládající se z binárních znaků. Pokud náhodně seberete takové binární zprávy , že se v součtu budou rovnat , a rozdělíte tyto zprávy mezi všechny členy skupiny, ukáže se, že zprávu bude možné přečíst pouze v případě, že se všichni členové skupiny sejdou [1] . $t$ $s$ $n$ ${\displaystyle s_{1},\ldots ,s_{t))$ $s$

V takovém schématu je značný problém: v případě ztráty alespoň jednoho z členů skupiny se nenávratně ztratí tajemství pro celou skupinu.

Schéma prahu

Na rozdíl od procedury tajného dělení, kde se v proceduře tajného dělení může počet sdílených položek, které jsou potřebné k obnovení tajného klíče, lišit od toho, na kolik sdílených položek je tajný klíč rozdělen. Takové schéma se nazývá prahové schéma , kde je počet podílů, do kterých bylo tajemství rozděleno, a počet podílů, které jsou potřebné k obnovení tajemství. Nápady obvodu byly nezávisle navrženy v roce 1979 Adi Shamir a George Blakley . Podobné postupy navíc studoval Gus Simmons [3] [4] [5] . $t=n$ $\left( t, n\right)$ $n$ $t$ $t \neq n$

Pokud je koalice účastníků taková, že mají dostatek podílů na obnovení tajemství, pak se koalice nazývá povolená. Schémata tajného sdílení, ve kterých mohou povolené koalice účastníků jedinečně získat tajemství a nevyřešené nedostávají žádnou aposteriorní informaci o možné hodnotě tajemství, se nazývají perfektní [6] .

Shamirovo schéma

Myšlenka diagramu je taková, že dva body stačí k definování přímky , tři body stačí k definování paraboly , čtyři body stačí k definování kubické paraboly a tak dále. Pro určení polynomu stupně jsou vyžadovány body . $k$ $k+1$

Aby bylo tajemství po oddělení obnoveno pouze účastníky, je „skryto“ ve vzorci polynomu stupně nad konečným polem . Pro jednoznačné obnovení tohoto polynomu je nutné znát jeho hodnoty v bodech a při použití menšího počtu bodů nebude možné jednoznačně obnovit původní polynom. Počet různých bodů polynomu není omezen (v praxi je omezen velikostí číselného pole , ve kterém se výpočty provádějí). $k$ $(k-1)$ $G$ $k$ $G$

Stručně lze tento algoritmus popsat následovně. Nechť je dáno konečné pole . Opravujeme různé nenulové neutajené prvky tohoto pole. Každý z těchto prvků je připisován konkrétnímu členu skupiny. Dále se vybere libovolná množina prvků oboru , ze které se skládá polynom nad oborem stupně . Po získání polynomu vypočítáme jeho hodnotu v neutajených bodech a výsledky nahlásíme odpovídajícím členům skupiny [1] . $G$ $n$ $t$ $G$ $f(x)$ $G$ $t-1,1<t\leq n$

K obnovení tajného klíče můžete použít interpolační vzorec, jako je Lagrangeův vzorec .

Důležitou výhodou schématu Shamir je, že je snadno škálovatelné [5] . Pro zvýšení počtu uživatelů ve skupině stačí pouze přidat odpovídající počet neutajených prvků ke stávajícím a musí být splněna podmínka pro . Kompromis jedné části tajemství zároveň změní schéma z -threshold na -threshold. ${\displaystyle r_{i}\neq r_{j))$ $i\neq j$ $(n,t)$ $(n-1,t-1)$

Blackleyho schéma

Dvě nerovnoběžné přímky v rovině se protínají v jednom bodě. Jakékoli dvě nekoplanární roviny se protínají v jedné přímce a tři nekoplanární roviny v prostoru se také protínají v jednom bodě. Obecně platí , že n n -rozměrných nadrovin se vždy protíná v jednom bodě. Jedna ze souřadnic tohoto bodu bude tajemstvím. Pokud je tajenka zakódována jako několik souřadnic bodu, pak již z jednoho podílu tajenky (jedné nadroviny) bude možné získat nějaké informace o tajence, tedy o vzájemné závislosti souřadnic průsečíku.


Blackleyho schéma ve třech rozměrech: každý podíl tajemství je rovina a tajemství je jednou ze souřadnic průsečíku rovin. Dvě roviny k určení průsečíku nestačí.

S pomocí Blackleyho schématu [4] lze vytvořit (t, n) -tajné schéma sdílení pro libovolné t a n : k tomu je třeba použít prostorovou dimenzi rovnou t a dát každému z n hráčů jedna nadrovina procházející tajným bodem. Potom se libovolné t z n nadrovin jednoznačně protnou v tajném bodě.

Blackleyho schéma je méně efektivní než Shamirovo schéma: v Shamirově schématu má každá akcie stejnou velikost jako tajemství, zatímco v Blackleyho schématu je každá akcie tkrát větší . Blakelyho schéma má vylepšení pro zlepšení jeho efektivity.

Schémata založená na čínské větě o zbytku

V roce 1983 Maurice Mignotte , Asmuth a Bloom navrhli dvě tajná schémata sdílení založená na čínské větě o zbytku . Pro určité číslo (ve schématu Mignotte je to samotné tajemství, ve schématu Asmuth-Bloom je to nějaké odvozené číslo) se vypočítá zbytek po vydělení posloupností čísel, která se rozdělí stranám. Kvůli omezení posloupnosti čísel může tajemství získat zpět pouze určitý počet stran [7] [8] .

Nechte počet uživatelů ve skupině být . V Mignotte schématu je určitá množina párových prvočísel vybrána tak, že součin největších čísel je menší než součin nejmenšího z těchto čísel. Nechť jsou tyto produkty rovné a , resp. Číslo se nazývá práh pro vytvořené schéma nad množinou . Jako tajemství je vybráno takové číslo, aby byl vztah splněn . Části tajenky jsou rozděleny mezi členy skupiny následovně: každý člen dostane dvojici čísel , kde . $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))))$

Chcete-li obnovit tajemství, musíte fragmenty sloučit. V tomto případě dostaneme systém srovnání formy , jehož množinu řešení lze najít pomocí čínské věty o zbytku . Tajné číslo patří do této sady a splňuje podmínku . Je také snadné ukázat, že pokud je počet fragmentů menší než , pak pro nalezení tajenky je nutné seřadit pořadí celých čísel. Při správné volbě čísel je takové vyhledávání téměř nemožné realizovat. Pokud je například bitová hloubka od 129 do 130 bitů a , pak bude poměr řádu [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}$

Schéma Asmuth-Bloom je upravené Mignotovo schéma. Na rozdíl od Mignotteho schématu jej lze zkonstruovat tak, aby bylo dokonalé [10] .

Schémata založená na řešení soustav rovnic

V roce 1983 Karnin, Green a Hellman navrhli své schéma tajného sdílení , které bylo založeno na nemožnosti vyřešit systém s neznámými s menším počtem rovnic [11] . $m$ $m$

V rámci tohoto schématu jsou -rozměrné vektory voleny tak, že jakákoli matice velikosti složená z těchto vektorů má rank . Nechť má vektor rozměr . $n+1$ $m$ ${\displaystyle V_{0},V_{1},...,V_{n))$ $m\times m$ $m$ $U$ $m$

Tajemstvím obvodu je maticový produkt . Podíly tajemství jsou díla . $U^{T}V_{0}$ $U^{T}V_{i},1\leq i\leq n$

S libovolnými podíly je možné sestavit soustavu lineárních rovnic rozměru , ve které jsou koeficienty neznámé . Vyřešením tohoto systému můžete najít , a mít , můžete najít tajemství. V tomto případě soustava rovnic nemá řešení, pokud jsou podíly menší než [12] . $m$ $m\times m$ $U$ $U$ $U$ $m$

Způsoby, jak podvádět schéma prahů

Existuje několik způsobů, jak přerušit protokol prahového obvodu:

vlastník jedné z akcií může zasáhnout do obnovy sdíleného tajemství tím, že ve správný čas vydá nesprávnou (náhodnou) akcii [13] .
útočník, který nemá podíl, může být přítomen při získávání tajemství. Po čekání na oznámení potřebného počtu sdílení rychle sám obnoví tajenku a vygeneruje další sdílení, načež jej předloží zbytku účastníků. Díky tomu získá přístup k tajemství a zůstane v pasti [14] .

Existují také další možnosti narušení, které nesouvisejí s prováděním systému:

útočník může simulovat situaci, kdy je nutné prozrazení tajemství, a tím zjistit podíly účastníků [14] .

Viz také

Poznámky

↑ 1 2 3 Alferov, Zubov, Kuzmin et al., 2002 , str. 401.
↑ Schoenmakers, 1999 .
↑ CJ Simmons. Úvod do sdílených tajných a/nebo sdílených kontrolních schémat a jejich aplikace // Současná kryptologie. - IEEE Press, 1991. - S. 441-497 .
↑ 12. Blakley , 1979 .
↑ 12 Shamir , 1979 .
↑ Blackley, Kabatiansky, 1997 .
↑ Mignotte, 1982 .
↑ Asmuth, Bloom, 1983 .
↑ Moldavsko, Moldavsko, 2005 , str. 225.
↑ Shenets, 2011 .
↑ Karnin, Greene, Hellman, 1983 .
↑ Schneier B. Aplikovaná kryptografie. - 2. vyd. - Triumph, 2002. - S. 590. - 816 s. - ISBN 5-89392-055-4 .
↑ Pasailă, Alexa, Iftene, 2010 .
↑ 1 2 Schneier, 2002 , str. 69.

Literatura

Schneier B. 3.7. Tajné sdílení // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M .: Triumph, 2002. - S. 93-96. — 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Schneier B. 23.2 Secret Sharing Algorithms // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M .: Triumf, 2002. - S. 588-591. — 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .

Blakley G. R. Safeguarding cryptographic keys (anglicky) // Proceedings of the 1979 AFIPS National Computer Conference - Montvale : AFIPS Press , 1979. - S. 313-317. doi : 10.1109/AFIPS.1979.98
Shamir A. Jak sdílet tajemství // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Sv. 22, Iss. 11. - S. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
Mignotte M. How to Share a Secret (anglicky) // Cryptography : Proceedings of the Workshop on Cryptography Burg Feuerstein, Německo, 29. března – 2. dubna 1982 / T. Beth — Berlín , Heidelberg , New York, NY , Londýn [ atd .] : 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. Modulární přístup k ochraně klíčů // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1983. - Sv. 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. Teorie / F. Kschischang - IEEE , 1983. - Sv. 29, Iss. 1. - S. 35-41. — ISSN 0018-9448 ; 1557-9654 – doi:10.1109/TIT.1983.1056621
Blackley D. , Kabatyansky G. A. Zobecněná ideální schémata, která sdílejí tajemství a matroidy // Problém. přenos informací - 1997. - T. 33, no. 3. - S. 102-110.
Schoenmakers B. Jednoduché veřejně ověřitelné schéma tajného sdílení a jeho aplikace na elektronické hlasování // Pokroky v kryptologii — CRYPTO' 99 :19. výroční mezinárodní kryptologická konference Santa Barbara, Kalifornie, USA, 15.–19. srpna 1999 sborník / 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. Základy kryptografie : Učebnice - 2. vyd., Rev. a doplňkové - M .: Helios ARV , 2002. - ISBN 978-5-85438-137-6
Moldovyan N. A. , Moldovyan A. A. Úvod do kryptosystémů s veřejným klíčem - Petrohrad. : BHV-Petersburg , 2005. - 288 s. - ( Výukový program ) - ISBN 978-5-94157-563-3
Pasailă D. , Alexa V. , Iftene S. Detekce podvodů a identifikace podvodníků v tajných schématech sdílení založených na CRT (anglicky) // International Journal of Computing - 2010. - Vol. 9, Iss. 2. - S. 107-117. — ISSN 2312-5381 ; 1727-6209
Shenets N. N. O ideálních modulárních schématech sdílení tajných informací v polynomiálních kruzích v několika proměnných // Mezinárodní kongres o informatice: Informační systémy a technologie : materiály Mezinárodního vědeckého kongresu 31. - Minsk : BGU , 2011. - V. 1. Statuty Fakulty aplikované matematiky a informatiky. - S. 169-173. — ISBN 978-985-518-563-6