Salaisuuden jakaminen

Salainen jakaminen on termi kryptografiassa , jolla tarkoitetaan mitä tahansa menetelmää salaisuuden jakamiseksi osallistujaryhmän kesken, joista jokainen saa oman tietyn osuutensa. Salaisuuden voi luoda uudelleen vain alkuperäisen ryhmän osallistujien koalitio, ja ainakin osa alun perin tiedossa olevaa määrää heistä tulee olla koalitiossa.

Salaisia jakamisjärjestelmiä käytetään tapauksissa, joissa yhden tai useamman salaisuuden ylläpitäjän vaarantumisen todennäköisyys on huomattava , mutta todennäköisyyttä, että merkittävä osa osallistujista tekee epäreilua yhteistoimintaa, pidetään merkityksettömänä.

Olemassa olevissa järjestelmissä on kaksi osaa: salainen jakaminen ja salainen palautus. Jakamisella tarkoitetaan salaisuuden osien muodostamista ja niiden jakamista ryhmän jäsenten kesken, mikä mahdollistaa vastuun jakamisen salaisuudesta sen jäsenten kesken. Käänteisen järjestelmän pitäisi varmistaa sen palauttaminen edellyttäen, että sen pitäjiä on käytettävissä tietty määrä [1] .

Käyttötapaus: Salainen äänestysprotokolla perustuu salaiseen jakamiseen [2] .

Yksinkertaisin esimerkki salaisesta jakamisjärjestelmästä

Olkoon joukko ihmisiä ja pitkä viesti , joka koostuu binäärimerkeistä. Jos poimit satunnaisesti sellaisia binääriviestejä , että ne ovat yhteensä , ja jaat nämä viestit kaikkien ryhmän jäsenten kesken, käy ilmi, että viesti on mahdollista lukea vain, jos kaikki ryhmän jäsenet kokoontuvat yhteen [1] . $t$ $s$ $n$ ${\displaystyle s_{1},\ldots ,s_{t))$ $s$

Tällaisessa järjestelmässä on merkittävä ongelma: jos vähintään yksi ryhmän jäsenistä katoaa, salaisuus katoaa koko ryhmän osalta peruuttamattomasti.

Kynnyskaavio

Toisin kuin salaisen jakamisen menettelyssä, jossa salaisuuden jakamismenettelyssä salaisuuden palauttamiseen tarvittavien osuuksien määrä voi poiketa siitä, kuinka moneen osaan salaisuus on jaettu. Tällaista järjestelmää kutsutaan kynnysohjelmaksi , jossa on osakkeiden lukumäärä, joihin salaisuus on jaettu, ja osakkeiden lukumäärä, jotka tarvitaan salaisuuden palauttamiseen. Adi Shamir ja George Blakley ehdottivat piiriideoita itsenäisesti vuonna 1979 . Lisäksi samanlaisia menetelmiä tutki Gus Simmons [3] [4] [5] . $t = n$ $\vasen (t, n\oikea)$ $n$ $t$ $t \neq n$

Jos osallistujien koalitio on sellainen, että heillä on tarpeeksi osakkeita salaisuuden palauttamiseksi, liittoumaa kutsutaan ratkaistuksi. Salaisia jakamisjärjestelmiä, joissa osallistujien sallitut koalitiot voivat yksilöllisesti palauttaa salaisuuden, ja ratkaisemattomat eivät saa jälkikäteen tietoa salaisuuden mahdollisesta arvosta, kutsutaan täydellisiksi [6] .

Shamirin järjestelmä

Kaavion ideana on, että kaksi pistettä riittää määrittämään suoran , kolme pistettä riittää määrittelemään paraabelin , neljä pistettä riittää määrittämään kuutioparaabeli ja niin edelleen. Astepolynomin määrittämiseen tarvitaan pisteitä . $k$ $k+1$

Jotta vain osallistujat voisivat palauttaa salaisuuden erotuksen jälkeen, se "piilotetaan" rajallisen kentän astepolynomin kaavaan . Tämän polynomin ainutkertaiseksi palauttamiseksi on tarpeen tietää sen arvot pisteissä, ja käyttämällä pienempää määrää pisteitä ei ole mahdollista palauttaa yksiselitteisesti alkuperäistä polynomia. Polynomin eri pisteiden määrää ei ole rajoitettu (käytännössä sitä rajoittaa sen numeerisen kentän koko , jossa laskutoimitukset suoritetaan). $k$ $(k-1)$ $G$ $k$ $G$

Lyhyesti sanottuna tämä algoritmi voidaan kuvata seuraavasti. Olkoon äärellinen kenttä annettu . Korjaamme tämän kentän erilaisia nollasta poikkeavia ei-salaisia elementtejä. Jokainen näistä elementeistä on liitetty tietylle ryhmän jäsenelle. Seuraavaksi valitaan mielivaltainen joukko kentän elementtejä , joista muodostetaan polynomi astekentän yli . Kun polynomi on saatu, laskemme sen arvon ei-salaisissa kohdissa ja raportoimme tulokset ryhmän vastaaville jäsenille [1] . $G$ $n$ $t$ $G$ $f(x)$ $G$ $t-1,1<t\leq n$

Salaisuuden palauttamiseksi voit käyttää interpolointikaavaa , kuten Lagrangen kaavaa .

Shamir-järjestelmän tärkeä etu on, että se on helposti skaalautuva [5] . Ryhmän käyttäjien määrän lisäämiseksi tarvitsee vain lisätä vastaava määrä ei-salaisia elementtejä olemassa oleviin elementteihin, ja ehdon tulee täyttyä . Samaan aikaan salaisuuden yhden osan kompromissi muuttaa järjestelmän -kynnysarvosta -kynnykseen. ${\displaystyle r_{i}\neq r_{j))$ $i\neq j$ ${\näyttötyyli (n,t)}$ ${\näyttötyyli (n-1,t-1)}$

Blackleyn järjestelmä

Tasossa kaksi ei-rinnakkaista suoraa leikkaavat yhdessä pisteessä. Mitkä tahansa kaksi ei-koplanaarista tasoa leikkaavat yhdessä suorassa, ja myös kolme ei-samantasoista tasoa avaruudessa leikkaavat yhdessä pisteessä. Yleensä n n - ulotteista hypertasoa leikkaa aina yhdessä pisteessä. Yksi tämän pisteen koordinaateista on salainen. Jos salaisuus on koodattu useiksi pisteen koordinaatteiksi, niin jo yhdestä salaisuuden osuudesta (yhdestä hypertasosta) on mahdollista saada tietoa salaisuudesta, eli leikkauspisteen koordinaattien keskinäisestä riippuvuudesta.


Blackleyn kaavio kolmessa ulottuvuudessa: jokainen salaisuuden osuus on taso ja salaisuus on yksi tasojen leikkauspisteen koordinaateista. Kaksi tasoa ei riitä määrittämään leikkauspistettä.

Blackleyn skeeman [4] avulla voidaan luoda (t, n) -salainen jakoskeema mille tahansa t :lle ja n :lle: tätä varten on käytettävä avaruusulottuvuutta, joka on yhtä suuri kuin t , ja annettava kullekin n :stä pelaajasta yksi hypertaso, joka kulkee salaisen pisteen läpi. Silloin mikä tahansa t n: stä hypertasosta leikkaa yksiselitteisesti salaisessa pisteessä.

Blackleyn järjestelmä on vähemmän tehokas kuin Shamirin järjestelmä: Shamirin järjestelmässä jokainen osake on yhtä suuri kuin salaisuus, kun taas Blackleyn järjestelmässä kukin osake on t kertaa suurempi. Blakelyn järjestelmään on tehty parannuksia sen tehokkuuden parantamiseksi.

Kaaviot, jotka perustuvat kiinalaiseen jäännöslauseeseen

Vuonna 1983 Maurice Mignotte Asmuth ja Bloom ehdottivat kahta salaista jakamisjärjestelmää, jotka perustuivat kiinalaiseen jäännöslauseeseen . Tietylle luvulle ( Mignotte-kaaviossa tämä on itse salaisuus, Asmuth-Bloom -kaaviossa se on jokin johdannaisluku), jäännökset lasketaan numerosarjalla jakamisen jälkeen, jotka jaetaan osapuolille. Numerosarjan rajoitusten vuoksi vain tietty määrä osapuolia voi palauttaa salaisuuden [7] [8] .

Olkoon ryhmän käyttäjien määrä . Mignotte-kaaviossa valitaan tietty joukko parittaisia alkulukuja siten, että suurimpien lukujen tulo on pienempi kuin pienimmän näistä luvuista. Olkoon nämä tuotteet yhtä suuria ja vastaavasti. Lukua kutsutaan joukon yli rakennetun kaavion kynnysarvoksi . Salaisuutena valitaan luku siten, että relaatio täyttyy . Salaisuuden osat jaetaan ryhmän jäsenten kesken seuraavasti: jokaiselle jäsenelle annetaan numeropari , jossa . $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$ ${\näyttötyyli (r_{i},m_{i})}$ ${\displaystyle r_{i}\equiv S{\pmod {m_{i))))$

Salaisuuden palauttamiseksi sinun on yhdistettävä fragmentit. Tässä tapauksessa saadaan muodon vertailujärjestelmä, jonka ratkaisujoukko löytyy kiinalaisen jäännöslauseen avulla . Salainen numero kuuluu tähän joukkoon ja täyttää ehdon . On myös helppo osoittaa, että jos fragmenttien määrä on pienempi kuin , niin salaisuuden löytämiseksi on tarpeen lajitella kokonaislukujen järjestystä. Oikealla numerovalinnalla tällainen haku on lähes mahdotonta toteuttaa. Esimerkiksi jos bittisyvyys on 129 - 130 bittiä ja , suhde on suuruusluokkaa [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-kaavio on modifioitu Mignott-kaavio. Toisin kuin Mignotte-kaavio, se voidaan rakentaa niin, että se on täydellinen [10] .

Kaaviot, jotka perustuvat yhtälöjärjestelmien ratkaisemiseen

Vuonna 1983 Karnin, Green ja Hellman ehdottivat salaista jakamissuunnitelmaansa , joka perustui mahdottomuuteen ratkaista tuntemattomien järjestelmää vähemmällä yhtälöllä [11] . $m$ $m$

Tämän kaavion puitteissa valitaan -ulotteiset vektorit siten, että millä tahansa näistä vektoreista koostuvan kokoisen matriisin arvo on . Olkoon vektorilla ulottuvuus . $n+1$ $m$ ${\displaystyle V_{0},V_{1},...,V_{n))$ $m\times m$ $m$ $U$ $m$

Piirin salaisuus on matriisitulo . Salaisuuden osakkeet ovat teoksia . $U^{T}V_{0}$ $U^{T}V_{i},1\leq i\leq n$

Omilla osuuksilla on mahdollista muodostaa lineaarinen ulottuvuusyhtälöjärjestelmä , jossa kertoimet ovat tuntemattomia . Ratkaisemalla tämän järjestelmän voit löytää , ja kun sinulla on , voit löytää salaisuuden. Tässä tapauksessa yhtälöjärjestelmällä ei ole ratkaisua, jos osuudet ovat pienempiä kuin [12] . $m$ $m\times m$ $U$ $U$ $U$ $m$

Tapoja huijata kynnysjärjestelmä

On olemassa useita tapoja rikkoa kynnyspiirin protokolla:

yhden osakkeen omistaja voi puuttua jaetun salaisuuden palauttamiseen luovuttamalla väärän (satunnaisen) osuuden oikeaan aikaan [13] .
hyökkääjä, jolla ei ole osuutta, voi olla läsnä salaisuuden palauttamisessa. Odotettuaan tarvittavan osakemäärän ilmoitusta hän palauttaa nopeasti salaisuuden itse ja luo uuden osuuden, jonka jälkeen hän esittelee sen muille osallistujille. Tämän seurauksena hän saa pääsyn salaisuuksiin ja pysyy vailla [14] .

On myös muita häiriöitä, jotka eivät liity järjestelmän toteuttamiseen:

Hyökkääjä voi simuloida tilannetta, jossa salaisuuden paljastaminen on välttämätöntä, ja siten saada selville osallistujien osuudet [14] .

Katso myös

Muistiinpanot

↑ 1 2 3 Alferov, Zubov, Kuzmin et ai., 2002 , s. 401.
↑ Schoenmakers, 1999 .
↑ CJ Simmons. Johdatus jaettuihin salaisiin ja/tai yhteisiin ohjausjärjestelmiin ja niiden sovelluksiin // Contemporary Cryptology. - IEEE Press, 1991. - s. 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. Sovellettu kryptografia. - 2. painos - Triumph, 2002. - S. 590. - 816 s. - ISBN 5-89392-055-4 .
↑ Pasailă, Alexa, Iftene, 2010 .
↑ 1 2 Schneier, 2002 , s. 69.

Kirjallisuus

Schneier B. 3.7. Salainen jakaminen // Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M . : Triumph, 2002. - S. 93-96. — 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .
Schneier B. 23.2 Salaiset jakamisalgoritmit // Applied Cryptography. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodit julkaisussa C. - M . : Triumf, 2002. - S. 588-591. — 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .

Blakley G. R. Safeguarding cryptographic keys (englanti) // Proceedings of the 1979 AFIPS National Computer Conference - Montvale : AFIPS Press , 1979. - P. 313-317. doi : 10.1109/AFIPS.1979.98
Shamir A. Kuinka jakaa salaisuus // Commun . ACM - [New York] : Association for Computing Machinery , 1979. - Voi. 22, Iss. 11. - s. 612-613. — ISSN 0001-0782 — doi:10.1145/359168.359176
Mignotte M. Kuinka jakaa salaisuus (englanniksi) // Kryptografia : Salaustyöpajan julkaisut Burg Feuerstein, Saksa, 29. maaliskuuta – 2. huhtikuuta 1982 / T. Beth – Berliini , Heidelberg , New York, NY , Lontoo [ jne . .] : 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. Modulaarinen lähestymistapa avainten turvaamiseen // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1983. - Voi. 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. Secret Sharing Systems // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1983. - Voi. 29, Iss. 1. - s. 35-41. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056621
Blackley D. , Kabatyansky G. A. Yleistetyt ideaaliset mallit, joilla on yhteinen salaisuus ja matroidit // Probl. tiedon siirto - 1997. - T. 33, no. 3. - S. 102-110.
Schoenmakers B. Yksinkertainen julkisesti todennettavissa oleva salainen jakamisjärjestelmä ja sen soveltaminen sähköiseen äänestykseen // Advances in Cryptology – CRYPTO' 99 :19th Annual International Cryptology Conference Santa Barbara, Kalifornia, USA, 15.–19. elokuuta 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. Salauksen perusteet : Oppikirja - 2. painos, Rev. ja ylimääräistä - M .: Helios ARV , 2002. - ISBN 978-5-85438-137-6
Moldovyan N. A. , Moldovyan A. A. Johdatus julkisen avaimen salausjärjestelmiin - Pietari. : BHV-Petersburg , 2005. - 288 s. - ( Opetusohjelma ) - ISBN 978-5-94157-563-3
Pasailă D. , Alexa V. , Iftene S. Huijaamisen havaitseminen ja huijaajien tunnistaminen CRT-pohjaisissa salaisissa jakamisjärjestelmissä (englanniksi) // International Journal of Computing - 2010. - Voi. 9, Iss. 2. - s. 107-117. — ISSN 2312-5381 ; 1727-6209
Shenets N. N. Ihanteellisista modulaarisista salajakamisjärjestelmistä polynomirenkaissa useissa muuttujissa // International Congress on Informatics: Information Systems and Technologies : materiaalit kansainvälisestä tiedekongressista 31. lokakuuta. - Minsk : BGU , 2011. - V. 1. Soveltavan matematiikan ja informatiikan tiedekunnan artikkelit. - S. 169-173. — ISBN 978-985-518-563-6