ANDOS (salaus)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8. heinäkuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

ANDOS ( All or Nothing Disclosure Of Secrets ) on salausprotokolla "salaisuuksien salaiseen myyntiin" . Anna S - salaisuuksien myyjälle luettelo kysymyksistä ja laita myyntiin vastaukset mihin tahansa niistä. Oletetaan, että ostaja B haluaa ostaa salaisuuden, mutta ei halua paljastaa, mitä. Protokolla takaa, että B saa tarvitsemansa salaisuuden eikä mitään muuta, kun taas S ei tiedä tarkalleen, minkä salaisuuden B sai .

Algoritmi

Olkoon S :n hallussa olevat salaisuudet , jokainen niistä sisältää vähän. Jokaiselle S julkaisee salaisuuden kuvauksen. Oletetaan, että ostajat B ja C haluavat ostaa salaisuuksia ja vastaavasti . Ajatuksena on, että ostajilla on yksilölliset yksisuuntaiset toiminnot ja jokainen niistä toimii toisen vastaanottamilla numeroilla. ${\displaystyle s_{1},...,s_{k))$ $n$ $s_{j}$ $s_{j}$ ${\displaystyle s_{j'))$

Vaihe 1. S antaa B :lle ja C :lle yksittäiset yksisuuntaiset funktiot f ja g , mutta pitää niiden käänteisfunktiot itselleen. Vaihe 2. B kertoo C :lle (vastaavasti C - B ) satunnaiset bittiluvut (vastaavasti ).

k

n

{\displaystyle x_{1},...,x_{k))

x_{1'},...,x_{k'}

Jos , joka yhdistää -bittiluvut -bittisiin lukuihin ja -bitin numero , sano, että indeksi on Fixed Bit Index (FBI) , joka vastaa paria, jos -th bit in on yhtä suuri kuin -th bit in . On selvää, että paria vastaava IFB on, jos se on paria vastaava IFB . Jos se käyttäytyy melko satunnaisesti bittejä vaihtaessaan (kuten hyvät salaustoiminnot), niin satunnaiselle voidaan karkeasti arvioida, että suunnilleen indeksit ovat IFB:itä, jotka vastaavat $f$ $n$ $n$ $n$ $x$ $i,1\leqslant i\leqslant n$ ${\näyttötyyli (x, f)}$ $i$ $x$ $i$ $f(x)$ $i$ ${\näyttötyyli (x, f)}$ ${\näyttötyyli (f(x),f^{-1})}$ $f$ $x$ $x$ ${\frac {n}{2))$ ${\näyttötyyli (x, f).}$

Vaihe 3. B kertoo C :lle (vastaavasti C - B ) IFB- indeksien joukon, joka vastaa vastaavasti IFB- indeksien joukkoa, joka vastaa

{\näyttötyyli _{B}}

(x'_{j},f)(

{\näyttötyyli _{C}}

(x_{j'},g)).

Vaihe 4. B (vastaavasti C ) kertoo S numeroa (vastaavasti , missä on tulos, joka saadaan korvaamalla jokainen bitti kohdassa , jonka indeksi ei ole IFB , sen vastineella (vastaavasti saatu vastaavalla tavalla).

{\displaystyle y_{1},...,y_{k))

y_{k'},...,y_{k'}

y_{i}

x_{i}

{\näyttötyyli _{C}}

{\displaystyle y'_{i))

{\näyttötyyli x'_{i))

Vaihe 5. S kertoo B (vastaavasti C ) numerot

s_{i}\oplus f^{-1}(y'_{i})(

vastaavasti , .

s_{i}\oplus g^{-1}(y_{i}))

i=1,...,k

Vaihe 6. B (vastaavasti C ) osaa laskea (vastaavasti ), koska ne tunnetaan vastaavasti

s_{j}

{\displaystyle s'_{j))

x'_{j}=f^{-1}(y'_{j})(

x_{j'}=g^{-1}(y_{j'})).

B ja C oppivat tarvitsemansa salaisuudet. S ei oppinut valinnastaan mitään. Myöskään B ja C eivät oppineet enempää kuin yhtä toistensa salaisuuksista tai valinnoista. B :n ja C :n välinen salaliitto johtaa siihen, että he voivat oppia kaikki salaisuudet. S :n ja yhden ostajan välinen salaliitto voi paljastaa, minkä salaisuuden toinen ostaja haluaa.

Suurin ongelma on siis salaliitto. Jos ostajia on kuitenkin vähintään kolme, niin yksi rehellinen ostaja riittää, jotta muiden huijaaminen on mahdotonta salaustoimintojen käytön ansiosta, koska jokainen S :ltä ostajille lähetettävä sekvenssin bitti on erittäin riippuvainen biteistä. rehellisen ostajan tarjoama.

Jos ostajia on useita , protokolla toimii täsmälleen samalla tavalla, mutta jokainen ostaja saa myyjältä toiminnon sekä numerosarjat muilta ostajilta. $t\geqslant 3$ $t-1$

Esimerkkejä

Otetaan RSA yksisuuntaisten funktioiden perustaksi . $f$ $g$

Valitaan . Oletetaan, että S :llä on myytävänä seuraavat 8 12-bittistä salaisuutta:

k=8,n=12

s_{1}=1990,

s_{2}=471,

s_{3}=3860,

s_{4}=1487,

s_{5}=2235,

s_{6}=3751,

s_{7}=2546,

s_{8}=4043.

Vaihe 1. S antaa B :lle ja C :lle yksittäiset yksisuuntaiset funktiot f ja g alkulukujen (vastaavasti ), modulo (vastaavasti ) perusteella. Avoin ja suljettu eksponentti ovat yhtä suuret (vastaavasti ).

p_{1}=83,q_{1}=89

p_{2}=67,q_{2}=41

n_{1}=7387

n_{2}=2747

e_{1}=5145,d_{1}=777

e_{2}=1421,d_{2}=2261

Vaihe 2 B kertoo C : lle kahdeksan 12-bittistä numeroa :

x_{i},1\leqslant i\leqslant 8

x_{1}=743,

x_{2}=1988,

x_{3}=4001,

x_{4}=2942,

x_{5}=3421,

x_{6}=2210,

x_{7}=2306,

x_{8}=912.

C kertoo B : lle kahdeksan 12-bittistä numeroa :

x'_{i},1\leqslant i\leqslant 8

x'_{1}=1708,

x'_{2}=711,

x'_{3}=1969,

x'_{4}=3112,

x'_{5}=4014,

x'_{6}=2308,

x'_{7}=2212,

x'_{8}=222.

Vaihe 3 Anna B :n ostaasalaisuuden . Hän laskee

{\displaystyle s_{7))

f(x'_{7})=(x'_{7})^{e_{1}}{\pmod {n_{1}}=2212^{5145}{\pmod {7387} }=5928.

Vertaamalla binääriesitystä ja

{\displaystyle x'_{7))

f(x'_{7}),

2212=0100010100100

5928=1011100101000

B kertoo C :lle joukon IFB:itä vastaavasta

_{B}=\{0,1,4,5,6\}

(x'_{7},f).

Anna C haluaa ostaasalaisuuden . Laskelmien jälkeen C kertoo B :lle joukon IFB:itä vastaavasta

s_{2}

{\displaystyle _{C}=\{0,1,2,6,9,10\))

{\näyttötyyli (x_{2},g).}

Vaihe 4 B kertoo S :lle luvun , jossa on tulos, joka saadaan korvaamalla jokainen bitti kohdassa , jonka indeksi ei kuulu , päinvastoin, esimerkiksi:

y_{i},1\leqslant i\leqslant 8

y_{i}

x_{i}

{\näyttötyyli \{0,1,2,6,9,10\))

y_{2}=0110011111100=1660.

C kertoo S :lle luvut , missä on tulos, joka saadaan korvaamalla jokainen bitti kohdassa , jonka indeksi ei kuulu , päinvastoin, esimerkiksi:

y'_{i},1\leqslant i\leqslant 8

{\displaystyle y'_{i))

{\näyttötyyli x'_{i))

{\näyttötyyli \{0,1,4,5,6\))

y'_{7}=1011100101000=5928.

Vaihe 5 S kertoo B : lle käänteisfunktion , esimerkiksi:

s_{i}\oplus f^{-1}(y'_{i}),1\leqslant i\leqslant 8(

f^{-1}(y')=y'^{d_{1}}{\pmod {n_{1}}}=y'^{777}{\pmod {7387}})

s_{7}=2546=0100111110010

f^{-1}(y'_{7})=2212=0100010100100

s_{7}\oplus f^{-1}(y'_{7})=0000101010110={\boldsymbol {342))

S kertoo C - luvuille esimerkiksi käänteisfunktion .

s_{i}\oplus g^{-1}(y_{i}),1\leqslant i\leqslant 8(

g^{-1}(y)=y^{d_{2}}{\pmod {n_{2}}}=y^{2261}{\pmod {2747}})

s_{2}=471=000111010111

g^{-1}(y_{2})=1988=011111000100

s_{2}\oplus g^{-1}(y_{2})=011000010011={\boldsymbol {1555))

Vaihe 6 B oppii S : ltä saadun 7. luvun salaisen bittikohtaisen lisäyksen , nimittäin:

{\displaystyle s_{7))

{\displaystyle x'_{7))

x'_{7}=2212=100010100100

342=000101010110

x'_{7}\oplus 342)=100111110010={\boldsymbol {2546))

Jos C haluaa ostaa salaisuuden , se laskee S : ltä saadun 2. luvun bittikohtaisen lisäyksen , nimittäin:

s_{2}

x_{2}

x_{2}=1988=11111000100

1555=11000010011

x_{2}\oplus 1555)=00111010111={\boldsymbol {471))

Kirjallisuus

G. Brassard, C. Crepeau ja J.-M. Robert. Kaikki tai ei mitään salaisuuksien paljastaminen // Springer Lecture Notes in Computer Science 263(1987). Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
A.Salomaa ja L.Santean. Salaisuuksien salainen myynti monien ostajien kanssa // EATCS Bulletin 42(1990)) . Arkistoitu alkuperäisestä 4. maaliskuuta 2016.