ANDOS (kryptografi)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 juli 2019; kontroller kräver 2 redigeringar .

ANDOS ( All or Nothing Disclosure Of Secrets ) är ett kryptografiskt protokoll för "hemlig försäljning av hemligheter" . Låt säljaren av S hemligheter ha en lista med frågor och lägg ut svaren på någon av dem till försäljning. Antag att köpare B vill köpa en hemlighet, men inte vill avslöja vilken. Protokollet garanterar att B kommer att få hemligheten den behöver och inget annat, medan S inte vet exakt vilken hemlighet B fick .

Algoritm

Låt hemligheterna som S besitter , var och en av dem innehåller lite. För varje S publicerar en beskrivning av hemligheten. Antag att köpare B och C vill köpa hemligheter respektive . Tanken är att köparna har individuella envägsfunktioner och var och en av dem opererar på de nummer som den andra får. ${\displaystyle s_{1},...,s_{k))$ $n$ $s_{j}$ $s_{j}$ ${\displaystyle s_{j'))$

Steg 1. S ger B och C individuella envägsfunktioner f och g , men behåller sina inverser för sig själv. Steg 2. B berättar för C (respektive C - B ) slumpmässiga bitar (respektive ).

k

n

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

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

För , som mappar -bitnummer till -bittal och -bitnummer , säg att indexet är det fasta bitindexet (FBI) som motsvarar paret om den -th biten i är lika med -th biten i . Det är tydligt att det finns en IFB som motsvarar paret om det är en IFB som motsvarar paret . Om den beter sig ganska slumpmässigt när man byter bitar i (som bra kryptografiska funktioner) så kan man för random grovt uppskatta att ungefär indexen är IFBs motsvarande $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).$

Steg 3. B berättar för C (respektive C - B ) uppsättningen IFB- index som motsvarar respektive uppsättning IFB- index motsvarande

_{B}

(x'_{j},f)(

_{C}

(x_{j'},g)).

Steg 4. B (respektive C ) berättar S -tal (respektive , var är resultatet som erhålls genom att ersätta varje bit i , vars index inte är IFB , med dess motsats (respektive erhållen från på ett liknande sätt).

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

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

y_{i}

x_{i}

_{C}

{\displaystyle y'_{i))

{\displaystyle x'_{i))

Steg 5. S berättar B (respektive C ) nummer

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

respektive . _

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

i=1,...,k

Steg 6. B (respektive C ) kan beräkna (respektive ) eftersom de är kända resp.

s_{j}

{\displaystyle s'_{j))

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

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

B och C lärde sig hemligheterna de behövde. S fick inte veta något om deras val. Dessutom lärde sig varken B eller C mer än en av varandras hemligheter eller val. En maskopi mellan B och C resulterar i att de kan lära sig alla hemligheter. Samverkan mellan S och en av köparna kan avslöja vilken hemlighet den andra köparen vill ha.

Så huvudproblemet är maskopi. Men om det finns minst tre köpare, räcker det med en ärlig köpare för att göra det omöjligt att lura resten, tack vare användningen av kryptografiska funktioner, eftersom varje bit av sekvensen som skickas till köpare från S är starkt beroende av bitarna tillhandahålls av den ärliga köparen.

I de fall där det finns ett antal köpare fungerar protokollet på exakt samma sätt, men varje köpare får en funktion från säljaren tillsammans med uppsättningar av nummer från andra köpare. $t\geqslant 3$ $t-1$

Exempel

Låt oss ta RSA som grund för envägsfunktioner . $f$ $g$

Låt oss välja . Tänk på att S har följande 8 12-bitars hemligheter att sälja:

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.

Steg 1. S ger B och C individuella envägsfunktioner f och g baserat på primtal (respektive ), modul (respektive ). De öppna och slutna exponenterna är lika (respektive ).

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

Steg 2 B berättar för C åtta 12-bitars nummer :

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 berättar för B åtta 12-bitars nummer :

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.

Steg 3 Låt B vilja köpa hemligheten . Han räknar ut

{\displaystyle s_{7))

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

Jämföra den binära representationen och

{\displaystyle x'_{7))

f(x'_{7}),

2212=0100010100100

5928=1011100101000

B berättar för C en uppsättning IFB för motsvarande

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

(x'_{7},f).

Låt C vilja köpa en hemlighet . Efter beräkningar berättar C för B en uppsättning IFB:er av motsvarande

s_{2}

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

(x_{2},g).

Steg 4 B berättar för S talet , där är resultatet som erhålls genom att ersätta varje bit i , vars index inte tillhör , med motsatsen, till exempel:

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

y_{i}

x_{i}

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

y_{2}=0110011111100=1660.

C berättar för S siffrorna , där är resultatet som erhålls genom att ersätta varje bit i , vars index inte tillhör , med motsatsen, till exempel:

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

{\displaystyle y'_{i))

{\displaystyle x'_{i))

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

y'_{7}=1011100101000=5928.

Steg 5 S talar om för B -nummer den inversa funktionen , till exempel:

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 säger till C -tal en invers funktion , till exempel.

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

Steg 6 B lär sig den hemliga bitvisa additionen av det 7:e numret som tas emot från S , nämligen:

{\displaystyle s_{7))

{\displaystyle x'_{7))

x'_{7}=2212=100010100100

342=000101010110

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

Om C vill köpa hemligheten beräknar den det bitvisa tillägget av det andra numret som tas emot från S , nämligen:

s_{2}

x_{2}

x_{2}=1988=11111000100

1555=11000010011

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

Litteratur

G. Brassard, C. Crepeau och J.-M. Robert. Allt-eller-ingenting avslöjande av hemligheter // Springer Lecture Notes in Computer Science 263(1987). Arkiverad från originalet den 4 mars 2016.
A.Salomaa och L.Santean. Hemlig försäljning av hemligheter med många köpare // EATCS Bulletin 42(1990)) . Arkiverad från originalet den 4 mars 2016.