Salainen jakamisvektorijärjestelmä

Vektorin salainen jakojärjestelmä tai Blakleyn järjestelmä on salainen jakamisjärjestelmä osapuolten välillä , joka perustuu pisteiden käyttöön moniulotteisessa avaruudessa. George Blackleyn ehdotus vuonna 1979 . Blakelyn menetelmän avulla voit luoda ( t , n )-kynnyksen salaisen jaon mille tahansa t , n :lle .

Idea

Jaettu salaisuus Blackleyn mallissa on yksi pisteen koordinaateista -ulotteisessa avaruudessa. Osapuolille annetut salaisuuden osuudet ovat -ulotteisten hypertasojen yhtälöitä . Pisteen palauttamiseksi on tarpeen tietää hypertasojen yhtälöt. Alle kaksi puolta ei voi palauttaa salaisuutta, koska tasojen leikkausjoukko on suora, eikä salaisuutta voida palauttaa. $m$ $(m-1)$ $m$ $m$ $m-1$


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

On huomattava, että geometrinen kuvaus ja kuvat on annettu järjestelmän pääidean ymmärtämiseksi. Itse salainen jakamisprosessi kuitenkin tapahtuu äärellisissä kentissä käyttämällä samanlaista, mutta erilaista matemaattista laitteistoa.

Kuvaus

Pisteiden luominen

Olkoon tarpeen toteuttaa -kynnysjärjestelmä, eli jakaa salaisuus osapuolten kesken niin, että kuka tahansa voi palauttaa salaisuuden. Tätä varten valitaan suuri alkuluku , jonka modulo kenttä rakennetaan . Satunnainen jakaja $(k,n)$ $M$ $n$ $k$ $p>M$ $GF(p)$ [ kuka? ] valitsee numerot . Tämä asettaa pisteen -ulotteiseen avaruuteen , jonka ensimmäinen koordinaatti on salainen. $b_{2},\pisteet ,b_{k}\in GF(p)$ $(M,b_{2},\pisteet ,b_{k})$ $k$

Salaisuuden jakaminen

Kummallekin puolelle satunnaisesti valitut kertoimet jaetaan tasaisesti kenttään . Koska tason yhtälöllä on muoto , jokaiselle puolelle on laskettava kertoimet : $P_{i},i=(1,\pisteet ,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} +\pisteet +a_{kn}\cdot b_{k}){\bmod {p}}.\\\end{aligned}}

Tässä tapauksessa on tarpeen varmistaa, että kaikki yhtälöt ovat lineaarisesti riippumattomia. Salaisuuden osuuksina osapuolille annetaan joukko kertoimia, jotka määrittelevät hypertason yhtälön. $k$

Salaisuuden palauttaminen

Salaisuuden palauttamiseksi kaikkien osapuolten tulee kokoontua yhteen ja käyttää salaisuuden käytettävissä olevia osuuksia tehdäkseen yhtälöitä hypertasojen leikkauspisteen löytämiseksi: $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} +\pisteet +a_{kk}\cdot x_{k}+d_{k}){\bmod {p}}&=0.\\\end{aligned}}\right.

Järjestelmän ratkaisu antaa -ulotteisessa avaruudessa pisteen, jonka ensimmäinen koordinaatti on yhteinen salaisuus. Järjestelmä voidaan ratkaista millä tahansa tunnetulla menetelmällä, esimerkiksi Gaussin menetelmällä , mutta laskelmia on suoritettava kentällä . $k$ $GF(p)$

Jos kokouksen osallistujien määrä on pienempi kuin esimerkiksi , niin käytettävissä olevasta kerroinjoukosta koostuvan yhtälöjärjestelmän ratkaisun tulos on suora viiva -ulotteisessa avaruudessa. Näin ollen sallittujen salaisten arvojen joukko, joka tyydyttää tuloksena olevan järjestelmän, vastaa tarkasti kentän elementtien kokonaismäärää , ja salaisuus voi saada minkä tahansa arvon tästä kentästä yhtä todennäköisyydellä. Näin ollen yhteen kokoontuneet osallistujat eivät saa uutta tietoa yhteisestä salaisuudesta. $k$ $k-1$ $k$ $GF(p)$

Ominaisuudet

Epätäydellinen järjestelmä : Osallistujien määrä kasvaa, salaisen pisteen mahdollisuuksien määrä vähenee. Esimerkiksi t − 1:lle osallistujat tietävät salaisen pisteen sisältävän rivin.

Osastopiiri : Osallistujat on jaettu alaryhmiin, joita kutsutaan osastoiksi. Salaisuuden saamiseksi vaaditaan päätösvaltaisuus, mutta osallistuakseen päätösvaltaisuuteen tarvitaan toinen päätösvaltaisuus osakkeista.

Porrastetut järjestelmät : Osallistujat on jaettu kahteen järjestetylle tasolle. Salaisuuden palauttamiseksi vaaditaan vähemmän päätösvaltaisuutta korkeammalla tasolla. Lisäksi jokainen korkeamman tason jäsen voi korvata alemman tason jäseniä.

Jotkut osallistujat eivät voi ymmärtää salaisuutta.

Esimerkki

Olkoon tarpeen jakaa salaisuus "6" 4 osapuolen välillä, kun taas minkä tahansa 3:n pitäisi pystyä palauttamaan se. Toisin sanoen on välttämätöntä toteuttaa -kynnyksen salajako. $(3.4)$

Tätä varten asetetaan piste kolmiulotteiseen avaruuteen, esimerkiksi . Pisteen ensimmäinen koordinaatti on jaettu salaisuus, 4 ja 2 ovat satunnaislukuja. Tässä tapauksessa työskentelemme kentässä , eli kaikki luvut lasketaan jaon jäännökseksi . $(6,4,2)$ $GF(11)$ $p = 11$

Jokaiselle sivulle on annettava yhtälö tietyn pisteen läpi kulkevalle tasolle. Kolmiulotteisessa avaruudessa tason yhtälö määritellään 4 parametrin avulla: , missä ovat koordinaatit ja sivuille jaetut parametrit. Parametrien valitsemiseksi voit edetä seuraavasti: valitse arvot satunnaisesti (tässä tapauksessa on välttämätöntä, että tuloksena olevat tasot eivät ole samassa tasossa ) ja laske kummankin puolen vapaa kerroin käyttämällä annettu piste ja valitut kertoimet. $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})$

Valitsemme parametrit esimerkiksi seuraavasti:

1. puoli: ,

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

2. puoli: ,

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

3. puoli: ,

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

4. puoli: .

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

Tuntemattomien parametrien laskemiseksi käytämme valitun pisteen koordinaattien arvoja: $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{aligned}}

Tämän jälkeen salaisuuden osuudet numeron kanssa jaetaan osapuolille. $p = 11$

Salaisuuden palauttamiseksi kaikkien kolmen osallistujan on löydettävä niiden tasojen leikkauspisteet, joiden yhtälöt niille annettiin. Esimerkiksi kolmen ensimmäisen salaisuuden palauttavan osapuolen on ratkaistava yhtälöjärjestelmä

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

Järjestelmä voidaan ratkaista millä tahansa tavalla, unohtamatta, että laskelmat suoritetaan kentällä . On helppo varmistaa, että piste on järjestelmän ratkaisu, sen ensimmäinen koordinaatti "6" on yhteinen salaisuus. $GF(11)$ $(6,4,2)$

Kirjallisuus

Schneier B. 23.2 Algoritmit salaisuuden jakamiseen. Vektorikaavio // Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - S. 589. - 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