ANDOS (criptografie)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 8 iulie 2019; verificările necesită 2 modificări .

ANDOS ( All or Nothing Disclosure Of Secrets ) este un protocol criptografic pentru „vânzarea secretă a secretelor” . Lăsați vânzătorul de secrete S să aibă o listă de întrebări și să pună la vânzare răspunsurile la oricare dintre ele. Să presupunem că cumpărătorul B dorește să cumpere un secret, dar nu dorește să dezvăluie care dintre ele. Protocolul garantează că B va obține secretul de care are nevoie și nimic altceva, în timp ce S nu va ști exact ce secret a primit B.

Algoritm

Lasă secretele deținute de S , fiecare dintre ele conține câte un pic. Pentru fiecare S publică o descriere a secretului. Să presupunem că cumpărătorii B și C doresc să cumpere secrete și , respectiv. Ideea este că cumpărătorii au funcții individuale unidirecționale și fiecare dintre aceștia operează pe numerele primite de celălalt. $s_{1},...,s_{k)$ $n$ $s_{j}$ $s_{j}$ ${\displaystyle s_{j'))$

Pasul 1. S oferă B și C funcții unidirecționale individuale f și g , dar păstrează inversele lor pentru sine. Pasul 2. B îi spune lui C (respectiv C - B ) numere aleatorii de biți (respectiv ).

k

n

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

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

Pentru , care mapează numerele -biți la numerele -biților și numărul -biților , spunem că indexul este Fixed Bit Index (FBI) corespunzător perechii dacă -al-lea bit în este egal cu --lea bit în . Este clar că există un IFB corespunzător perechii dacă este un IFB corespunzător perechii . Dacă se comportă destul de aleatoriu la schimbarea biților (cum ar fi funcțiile criptografice bune), atunci, pentru random , se poate estima aproximativ că aproximativ indicii sunt IFB-uri corespunzători lui $f$ $n$ $n$ $n$ $X$ $i,1\leqslant i\leqslant n$ $(x,f)$ $i$ $X$ $i$ $f(x)$ $i$ $(x,f)$ $(f(x),f^{-1})$ $f$ $X$ $X$ ${\frac {n}{2))$ $(x,f).$

Pasul 3. B îi spune lui C (respectiv C - B ) setul de indici IFB corespunzători respectiv setului de indici IFB corespunzători lui

_{B}

(x'_{j},f)(

_{C}

(x_{j'},g)).

Pasul 4. B (respectiv C ) spune S numere (respectiv , unde este rezultatul obținut prin înlocuirea fiecărui bit în , al cărui indice nu este IFB , cu opusul său (respectiv obținut dintr- un mod similar).

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

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

y_{i}

x_{i}

_{C}

y'_{i)

x'_{i)

Pasul 5. S spune numerelor B (respectiv C ).

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

respectiv , .

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

i=1,...,k

Pasul 6. B (respectiv C ) poate calcula (respectiv ) deoarece sunt cunoscute respectiv

s_{j}

s'_{j)

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

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

B și C au învățat secretele de care aveau nevoie. S nu a aflat nimic despre alegerea lor. De asemenea, nici B , nici C nu au aflat mai mult de unul dintre secretele sau alegerile celuilalt. O coluziune între B și C îi face ca aceștia să poată învăța toate secretele. Coluziunea dintre S și unul dintre cumpărători poate dezvălui ce secret dorește celălalt cumpărător.

Deci principala problemă este coluziunea. Cu toate acestea, dacă există cel puțin trei cumpărători, atunci un cumpărător onest este suficient pentru a face imposibilă înșelarea pe restul, datorită utilizării funcțiilor criptografice, deoarece fiecare bit din secvența trimis cumpărătorilor de la S este foarte dependent de biți. furnizate de cumpărătorul cinstit.

În cazul în care există un număr de cumpărători , protocolul funcționează exact în același mod, dar fiecare cumpărător primește o funcție de la vânzător împreună cu seturi de numere de la alți cumpărători. $t\geqslant 3$ $t-1$

Exemple

Să luăm RSA ca bază a funcțiilor unidirecționale . $f$ $g$

Să alegem . Luați în considerare că S are următoarele 8 secrete pe 12 biți de vândut:

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.

Pasul 1. S oferă B și C funcții unidirecționale individuale f și g bazate pe numere prime (respectiv ), modulo (respectiv ). Exponenții deschis și închis sunt egali (respectiv ).

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

Pasul 2 B îi spune lui C opt numere de 12 biți :

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 îi spune lui B opt numere de 12 biți :

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.

Pasul 3 Să dorească B să cumpere secretul . El calculează

s_{7)

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

Comparând reprezentarea binară și

x'_{7)

f(x'_{7}),

2212=0100010100100

5928=1011100101000

B îi spune lui C un set de IFB-uri ale corespunzătoare

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

(x'_{7},f).

Să C vrea să cumpere un secret . După calcule, C îi spune lui B un set de IFB -uri corespunzătoare

s_{2}

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

(x_{2},g).

Pasul 4 B îi spune lui S numărul , unde este rezultatul obținut prin înlocuirea fiecărui bit din , al cărui indice nu aparține lui , cu opusul, de exemplu:

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

y_{i}

x_{i}

\{0,1,2,6,9,10\)

y_{2}=0110011111100=1660.

C îi spune lui S numerele , unde este rezultatul obținut prin înlocuirea fiecărui bit din , al cărui indice nu aparține lui , cu opusul, de exemplu:

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

y'_{i)

x'_{i)

\{0,1,4,5,6\)

y'_{7}=1011100101000=5928.

Pasul 5 S le spune numerelor B funcția inversă , de exemplu:

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 le spune numerelor C o funcție inversă , de exemplu.

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)}

Pasul 6 B învață adăugarea secretă pe biți a celui de-al 7-lea număr primit de la S , și anume:

s_{7)

x'_{7)

x'_{7}=2212=100010100100

342=000101010110

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

Dacă C dorește să cumpere secretul , atunci calculează adăugarea pe biți a celui de-al 2-lea număr primit de la S , și anume:

s_{2}

x_{2}

x_{2}=1988=11111000100

1555=11000010011

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

Literatură

G. Brassard, C. Crepeau și J.-M. Robert. Dezvăluirea totul sau nimic a secretelor // Springer Lecture Notes in Computer Science 263 (1987). Arhivat din original pe 4 martie 2016.
A.Salomaa și L.Santean. Vânzarea secretă de secrete cu mulți cumpărători // Buletinul EATCS 42(1990)) . Arhivat din original pe 4 martie 2016.