Feig - Fiat - Shamir protokol

Feig-Fiat-Shamir- protokollen er en nul-viden identifikationsprotokol , en generalisering af den tidligere Fiat-Shamir- protokol , udviklet af Uriel Feige , Amos Fiat [ ] og Adi Shamir . ) i 1986. Denne enkle at implementere og kommercielt betydningsfulde ordning blev patenteret af forfatterne et år efter dens udvikling.

Protokollen giver en part (beviser A) mulighed for at bevise over for en anden part (verifikator B), at de har hemmelige oplysninger uden at afsløre en eneste bit af denne information.

Protokollens sikkerhed er baseret på vanskeligheden ved at udtrække kvadratroden modulo et tilstrækkeligt stort sammensat tal n, hvis faktorisering er ukendt.

Der er nogle forbedringer til hovedversionen af protokollen for at reducere kompleksiteten af interaktioner mellem deltagere eller for at indlejre identiteter i skemaet.

Derudover kan Feig-Fiat-Shamir-identifikationsskemaet nemt konverteres til et signaturskema.

Historie

I 1986 udviklede israelske forskere fra Wyman Institute Uriel Feige, Amos Fiat og Adi Shamir en praktisk nul-viden identifikationsordning, der kunne implementeres selv på enheder med laveffektprocessorer, såsom smart cards, personlige computere, personlige identifikationsdokumenter [ 1] . Af kommercielle årsager ansøgte forfatterne om et amerikansk patent den 9. juli 1986 . Den amerikanske patent- og varemærkemyndighed skulle inden for seks måneder tage stilling til beslutningen om at udstede en ordre om at fjerne hemmeligholdelsesordningen [2] [3] .

Blot få dage før udløbet af en vis periode udstedte Patentstyrelsen en ordre, der forbød enhver offentliggørelse eller offentliggørelse af oplysninger om protokollen, og forklarede dette som en trussel mod den nationale sikkerhed. Desuden skulle forfatterne underrette alle amerikanske borgere med kendskab til Feig-Fiat-Shamir-ordningen, at deres afsløring kunne føre til alvorlige sanktioner - to års fængsel eller en bøde på ti tusinde dollars. Det var også nødvendigt at rapportere om alle udenlandske stater, som oplysninger om undersøgelsen blev videregivet til [2] [3] .

På dette tidspunkt havde Feige, Fiat og Shamir allerede holdt adskillige præsentationer på universiteter i Israel, Europa og USA og havde ansøgt om konferencen Association for Computing Machinery , som skulle afholdes i New York i maj 1987 [ 2] [3] .

Selvom udviklerne af protokollen håbede, at Weizmann Instituttet, hvor undersøgelsen blev udført, ville appellere ordren, sendte de alligevel et brev til konferenceudvalget, hvor de forklarede situationen. Derefter gik mange organisationer, såsom Bell Labs og The New York Times , hurtigt med til at løse problemet. Det største bidrag blev ydet af National Security Agency (NSA), som i første omgang var uvidende om den udstedte ordre. Efter at NSA blev informeret om det, blev ordren annulleret inden for to dage [2] [3] .

Shamir talte ved en konference i Association for Computing Machinery den 26. maj [4] , og 5 dage senere modtog forfatterne et patent på den udviklede protokol [5] .

Identifikationsskema

A beviser sin viden om hemmeligheden til B i løbet af runder uden at afsløre en eneste smule af selve hemmeligheden [1] . $s$ $t$

Valg af systemindstillinger

Det betroede center T udgiver et stort antal , hvor og er primtal, der holdes hemmelige. Heltal og sikkerhedsparametre [6] er også valgt . $n=pq$ $s$ $q$ $k$ $t$

Generering af hemmeligheder for deltagere

Hver deltager vælger tilfældige heltal og tilfældige bits . $k$ $s_1, s_2, ..., s_k, 1 \leqslant s_i \leqslant n-1$ $k$ $b_1, b_2, ..., b_k$

Så regner den ud . $v_i = (-1)^{b_i}\cdot (s_i^2)^{-1} \mod n, 1 \leqslant i \leqslant k$

Deltageren identificerer sig selv over for andre ved hjælp af de værdier , der fungerer som hans offentlige nøgle, mens den hemmelige nøgle kun er kendt af deltageren [6] . $(v_1, v_2, ..., v_k; n)$ $s = (s_1, s_2, ..., s_k)$

Protokolhandlinger inden for en runde

A vælger et tilfældigt heltal $r, 1 \leqslant r \leqslant n-1$ beregner: og sender til part B . $x = r^2 \mod n$ $x$
B sender A en tilfældig -bitvektor hvor eller . $k$ $(e_1, e_2, ..., e_k)$ $e_i = 0$ $e_i = 1$
A beregner og sender B :. $y = r\cdot \prod^{k}_{i=1}s_i^{e_i} \mod n$
B vurderer: og kontrollerer at og [7] [6] . $z = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$ $z=\pm x\mod n$ $z \neq 0$

Sikkerhed

Lemma 1: Hvis A og B følger protokollen, så accepterer B altid bevis A : Bevis: pr. definition

$z = y^2 \cdot \prod^{k}_{i=1} v_i^{e_i} = r^2 \cdot \prod^{k}_{i=1} (s_i^{2e_i} v_i^ {e_i}) = \pm r^2 = \pm x \mod n$

- Amos Fiat, Adi Shamir "Sådan beviser du dig selv: Praktiske løsninger på identifikations- og signaturproblemer"

Hvis man antager, at factoring er en beregningsmæssig umulig opgave, er sandsynligheden for et vellykket protokolangreb . En angriber kan forsøge at efterligne en ærlig bruger ved at gætte de korrekte værdier af , forberede sig på det første trin og give i det tredje trin. Så sørger B for at . Men sandsynligheden for korrekt valg af værdier er i en runde og derfor i hele protokollen [1] . $n$ $2^{-kt}$ $e_{i}$ $x = \pm r^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$ $y=r$ $z = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} = r^2\cdot \prod^{k}_{i=1} v_i^{e_i} = \pm x$ $k$ $(e_1, e_2, ..., e_k)$ $2^{-k}$ $2^{-kt}$

For at opnå sikkerhedsniveauet er det således tilstrækkeligt at vælge og . Det betyder, at kun et ud af en million forsøg fra en uærlig bruger på at bedrage verifikatoren kan lykkes. $2^{-20}$ $k = 5$ $t=4$

Protokollen beviser, at A har sin private nøgle uden at afsløre nogen viden om den, hvornår og [1] . $k = O(\log \log n)$ $t = O(\log n)$

Eksempel

Lad betroet center T vælge primtal og og publicer . Systemsikkerhedsindstillinger: , . $p=683$ $q = 811$ $n=pq=553913$ $k = 3$ $t=1$
For deltager A vælges tilfældige tal: , , og 3 bits: , , . $s_1 = 187$ $s_2 = 37411$ $s_3 = 5204$ $b_1 = 1$ $b_2 = 1$ $b_3 = 0$ værdier beregnes: , , . $v_1 = 307124$ $v_2 = 115268$ $v_3 = 403211$ Offentlig nøgle A : , privat nøgle: . $(307124, 115268, 403211; 553913)$ $(187, 37411, 5204)$
(a) A vælger et tilfældigt tal , en tilfældig bit , beregner: og sender det til B. $r=1337$ $b = 1$ $x=428083$

(b) B sender A en 3-bit vektor: .

(0,1,0)

y=r\cdot s_2\mod n=166337

(d) B beregner: og accepterer beviset for A siden og .

z = y^2\cdot v_2 \mod n = 428083

z=\pm x\mod n

z \neq 0

Forbedringer og ændringer af identifikationsskemaet

Du kan nægte at vælge et fælles nummer for alle deltagere og give hver af dem mulighed for at vælge deres eget. Imidlertid vil eksistensen af et betroet center T stadig være nødvendig for at knytte hver deltager til sit modul [6] . $n$
For at reducere kompleksiteten af interaktionen mellem A og B , kan du erstatte den første besked, der sendes fra A til B , med en hashværdi . Følgelig vil B ved den sidste iteration af protokollen skulle operere i stedet for [6] sig selv . $x$ $h(x)$ $h(z)$ $z$
Skemaet kan ændres til at være baseret på hver enkelt deltagers identitet. For at gøre dette tildeles hver bruger A af det betroede center T en unik identifikationsstreng med oplysninger om deltageren (for eksempel navn, adresse, pasnummer osv.). Derefter beregner centret værdierne , hvor de ikke burde kunne skelnes fra en tilfældig funktion i polynomisk tid. Derefter, ved at kende faktoriseringen , beregner og udlæser det betroede center deres værdier A . Værdierne og bliver henholdsvis den offentlige og private nøgle for deltager A , og yderligere handlinger udføres i henhold til skemaet beskrevet ovenfor [7] [6] [3] . $I_{A}$ $v_i = f(I_A,i), 1 \leqslant i \leqslant k$ $f$ $n$ $s_i = \sqrt {v_i^{-1}} \mod n$ $v_{i}$ $s_{i}$
Den beskrevne protokol kan udføres parallelt. I dette tilfælde skal beskeder sendt fra A til B og tilbage indeholde data for alle runder på samme tid. Fordelen ved denne tilgang er, at den giver dig mulighed for at reducere kompleksiteten af eksekveringen ved at reducere antallet af producerede iterationer. En sådan ordning er sikker, men på grund af tekniske årsager mister den sin nul-viden egenskab. Faktum er, at parallel eksekvering kan tillade den uærlige verifikator B at bestemme ikke tilfældigt, men som funktioner af hele sættet sendt til ham fra A i det første trin. Hvis B gør dette ved hjælp af en envejs-hash-funktion , så vil den være i stand til at få information, som den ellers kun kunne beregne, hvis den kendte A 's hemmelighed . Det menes dog, at denne information ikke er "nyttig" (ved at vide det, vil B ikke være i stand til at efterligne A for en anden deltager), hvilket giver os mulighed for at betragte ordningen som stadig pålidelig [1] [8] . $t$ $e_{it}$ $x_t$

Signatur Feig - Fiat - Shamira

Part B spiller en meget vigtig rolle i det interaktive identitetsskema - det genererer tilfældige værdier , der forhindrer deltager A i at snyde . $e_{i}$

For at konvertere identifikationsskemaet til et signaturskema er det nok at ændre denne handling B til at bruge en hemmelig hashfunktion til at beregne [7] [6] [3] . $h$ $e_{i}$

Meddelelsessignatur

Lad A ønsker at underskrive en besked . $m$

A vælger et tilfældigt heltal og beregner: . $r, 1 \leqslant r \leqslant n-1$ $x = r^2 \mod n$
A beregner :. $e_i = h(x||m), 1 \leqslant i \leqslant k$
A beregner :. $y = r\cdot \prod^{k}_{i=1}s_i^{e_i} \mod n$
A sender B en besked , signatur og . $m$ $(e_1, e_2, ..., e_k)$ $y$

Signaturbekræftelse

Lad B ønsker at tjekke signaturen under beskeden . $m$

B beregner :. $x' = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$
B bruger til at beregne : . $x'$ $e'_i$ $e'_i = h(x'||m), 1 \leqslant i \leqslant k$
Hvis de beregnede værdier matcher signaturen modtaget fra A , så accepterer B signaturen . $(e'_1, e'_2, ..., e'_k)$ $(e_1, e_2, ..., e_k)$ $m$

Noter

↑ 1 2 3 4 5 Feige, Uriel; Fiat, Amos; Shamir, Adi. Nul-viden beviser for identitet (engelsk) (utilgængeligt link) (1987). Hentet 10. november 2015. Arkiveret fra originalen 17. november 2015.
↑ 1 2 3 4 Susan Landau. Zero Knowledge and Department of Defence (engelsk) (1988). Hentet 10. november 2015. Arkiveret fra originalen 16. januar 2016.
↑ 1 2 3 4 5 6 Schneier B. Anvendt kryptografi. Protokoller, Algoritmer, C-kildekoder (2002). Hentet 10. november 2015. Arkiveret fra originalen 20. november 2015. (ubestemt)
↑ Alfred V. Aho. STOC'87 19. årlige ACM-konference om databehandlingsteori . ACM New York, NY, USA (1987).
↑ Metode, apparatur og artikel til identifikation og underskrift ( 31. maj 1987). Hentet 11. november 2015. Arkiveret fra originalen 21. november 2015.
↑ 1 2 3 4 5 6 7 A. Menezes, P. van Oorschot og S. Vanstone. Handbook of Applied Cryptography (engelsk) (1996). Hentet 10. november 2015. Arkiveret fra originalen 8. december 2015.
↑ 1 2 3 Amos Fiat, Adi Shamir. Sådan beviser du dig selv: Praktiske løsninger på identifikations- og signaturproblemer (engelsk) (link ikke tilgængeligt) (1986). Hentet 10. november 2015. Arkiveret fra originalen 3. marts 2016.
↑ Gilles Brassard, Claude Crepeau, Moti Yung. Alt i NP kan argumenteres i perfekt nul-viden i et begrænset antal runder (engelsk) (1989). Dato for adgang: 13. november 2015. Arkiveret fra originalen 17. november 2015.

Litteratur

Fiat A. , Shamir A. Sådan beviser du dig selv: praktiske løsninger på identifikations- og signaturproblemer // Fremskridt inden for kryptologi - CRYPTO '86 :6. årlige internationale kryptologikonference, Santa Barbara, Californien, USA, 1986, Proceedings / A. M. Odlyzko - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 1987. - S. 186-194. - 490 sider. - ( Lecture Notes in Computer Science ; Vol. 263) - ISBN 978-3-540-18047-0 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-47721-7_12
Landau S. Zero Knowledge og Forsvarsministeriet // Meddelelser Amer . Matematik. soc. / F. Morgan - AMS , 1988. - Vol. 35, Iss. 1. - S. 5-12. — ISSN 0002-9920 ; 1088-9477
Feige U. , Fiat A. , Shamir A. Zero-Knowledge Proofs of Identity (engelsk) // Journal of Cryptology / I. Damgård - Springer Science + Business Media , International Association for Cryptologic Research , 1988. - Vol. 1, Iss. 2. - S. 77-94. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF02351717
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (engelsk) - CRC Press , 1996. - 816 s. — ( Diskret matematik og dens anvendelser ) — ISBN 978-0-8493-8523-0
Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .