ANDOS (kryptografi)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. juli 2019; checks kræver 2 redigeringer .

ANDOS ( All or Nothing Disclosure Of Secrets ) er en kryptografisk protokol til "hemmeligt salg af hemmeligheder" . Lad sælgeren af S -hemmeligheder have en liste med spørgsmål og sæt svarene på ethvert af dem til salg. Antag, at køber B ønsker at købe en hemmelighed, men ikke ønsker at afsløre hvilken. Protokollen garanterer, at B får den hemmelighed, den har brug for, og intet andet, mens S ikke ved præcis, hvilken hemmelighed B har fået .

Algoritme

Lad de hemmeligheder, som S besidder , hver af dem indeholder en smule. For hver S udgiver en beskrivelse af hemmeligheden. Antag, at købere B og C ønsker at købe hemmeligheder og hhv. Tanken er, at køberne har individuelle envejsfunktioner, og hver af dem opererer på de tal, den anden modtager. ${\displaystyle s_{1},...,s_{k))$ $n$ $s_{j}$ $s_{j}$ ${\displaystyle s_{j'))$

Trin 1. S giver B og C individuelle envejsfunktioner f og g , men holder deres inverse for sig selv. Trin 2. B fortæller C (henholdsvis C - B ) tilfældige -bit-tal (henholdsvis ).

k

n

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

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

For , som kortlægger -bittal til -bittal og -bittal , sig, at indekset er det faste bitindeks (FBI) svarende til parret, hvis -th bit i er lig med -th bit i . Det er klart, at der er en IFB, der svarer til parret , hvis det er en IFB, der svarer til parret . Hvis det opfører sig ret tilfældigt, når der skiftes bits i (som gode kryptografiske funktioner), så kan man for random groft estimere, at ca. indeksene er IFB'er svarende til $f$ $n$ $n$ $n$ $x$ $i,1\leqslant i\leqslant n$ $(x,f)$ $jeg$ $x$ $jeg$ $f(x)$ $jeg$ $(x,f)$ $(f(x),f^{-1})$ $f$ $x$ $x$ ${\frac {n}{2))$ $(x,f).$

Trin 3. B fortæller C (hhv. C - B ) det sæt af IFB - indekser, der henholdsvis svarer til sættet af IFB - indekser svarende til

_{B}

(x'_{j},f)(

_{C}

(x_{j'},g)).

Trin 4. B (henholdsvis C ) fortæller S - tal (hhv . hvor er resultatet opnået ved at erstatte hver bit i , hvis indeks ikke er IFB , med sin modsætning (henholdsvis opnået fra på en lignende måde).

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

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

y_{i}

x_{i}

_{C}

{\displaystyle y'_{i))

{\displaystyle x'_{i))

Trin 5. S fortæller B (henholdsvis C ) tal

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

hhv . _

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

i=1,...,k

Trin 6. B (hhv. C ) kan beregne (hhv. ), da de er kendte hhv.

s_{j}

{\displaystyle s'_{j))

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

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

B og C lærte de hemmeligheder, de havde brug for. S lærte ikke noget om deres valg. Desuden lærte hverken B eller C mere end én af hinandens hemmeligheder eller valg. Et samarbejde mellem B og C resulterer i, at de kan lære alle hemmelighederne. Samarbejde mellem S og en af køberne kan afsløre, hvilken hemmelighed den anden køber ønsker.

Så hovedproblemet er samordning. Men hvis der er mindst tre købere, så er en ærlig køber nok til at gøre det umuligt at snyde resten, takket være brugen af kryptografiske funktioner, da hver bit af sekvensen sendt til købere fra S er meget afhængig af bitsene leveret af den ærlige køber.

I det tilfælde, hvor der er et antal købere , fungerer protokollen på nøjagtig samme måde, men hver køber modtager en funktion fra sælgeren sammen med sæt tal fra andre købere. $t\geqslant 3$ $t-1$

Eksempler

Lad os tage RSA som grundlag for envejsfunktioner . $f$ $g$

Lad os vælge . Overvej, at S har følgende 8 12-bit hemmeligheder at sælge:

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.

Trin 1. S giver B og C individuelle envejsfunktioner f og g baseret på primtal (henholdsvis ), modulo (henholdsvis ). De åbne og lukkede eksponenter er ens (henholdsvis ).

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

Trin 2 B fortæller C otte 12-bit tal :

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 fortæller B otte 12-bit tal :

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.

Trin 3 Lad B ønske at købe hemmeligheden . Han beregner

{\displaystyle s_{7))

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

Sammenligning af den binære repræsentation og

{\displaystyle x'_{7))

f(x'_{7}),

2212=0100010100100

5928=1011100101000

B fortæller C et sæt IFB'er for de tilsvarende

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

(x'_{7},f).

Lad C gerne købe en hemmelighed . Efter beregninger fortæller C B et sæt IFB'er af de tilsvarende

s_{2}

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

(x_{2},g).

Trin 4 B fortæller S tallet , hvor er resultatet opnået ved at erstatte hver bit i , hvis indeks ikke tilhører , med det modsatte, for eksempel:

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

y_{i}

x_{i}

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

y_{2}=0110011111100=1660.

C fortæller S tallene , hvor er resultatet opnået ved at erstatte hver bit i , hvis indeks ikke tilhører , med det modsatte, for eksempel:

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

{\displaystyle y'_{i))

{\displaystyle x'_{i))

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

y'_{7}=1011100101000=5928.

Trin 5 S fortæller B -tallene den inverse funktion , for eksempel:

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 fortæller C -tal en omvendt funktion , for eksempel.

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

Trin 6 B lærer den hemmelige bitvise tilføjelse af det 7. tal modtaget fra S , nemlig:

{\displaystyle s_{7))

{\displaystyle x'_{7))

x'_{7}=2212=100010100100

342=000101010110

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

Hvis C ønsker at købe hemmeligheden , så beregner den den bitvise tilføjelse af det 2. tal modtaget fra S , nemlig:

s_{2}

x_{2}

x_{2}=1988=11111000100

1555=11000010011

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

Litteratur

G. Brassard, C. Crepeau og J.-M. Robert. Alt-eller-intet afsløring af hemmeligheder // Springer Lecture Notes in Computer Science 263(1987). Arkiveret fra originalen den 4. marts 2016.
A.Salomaa og L.Santean. Hemmeligt salg af hemmeligheder med mange købere // EATCS Bulletin 42(1990)) . Arkiveret fra originalen den 4. marts 2016.