Feig - Fiat - Shamir protokoll

A Feig-Fiat-Shamir protokoll egy nulla tudású azonosítási protokoll , a korábbi Fiat-Shamir protokoll általánosítása , amelyet Uriel Feige , Amos Fiat [ ] és Adi Shamir fejlesztett ki 1986-ban . Ezt az egyszerűen kivitelezhető és kereskedelmileg jelentős konstrukciót a kidolgozása után egy évvel szabadalmaztatták a szerzők.

A protokoll lehetővé teszi, hogy az egyik fél (A bizonyító) bebizonyítsa egy másik félnek (B ellenőrző), hogy titkos információi vannak anélkül, hogy ezekből egyetlen bitet is felfedne.

A protokoll biztonsága azon a nehézségen alapszik, hogy a négyzetgyök modulo egy kellően nagy n összetett számból nyerhető ki, amelynek faktorizációja ismeretlen.

A protokoll fő verziója néhány fejlesztést tartalmaz a résztvevők közötti interakciók bonyolultságának csökkentése vagy az identitások sémába való beágyazása érdekében.

Ezenkívül a Feig-Fiat-Shamir azonosítási séma könnyen átalakítható aláírási sémává.

Történelem

1986-ban a Wyman Institute izraeli tudósai, Uriel Feige, Amos Fiat és Adi Shamir kifejlesztettek egy gyakorlati tudás nélküli azonosítási sémát, amely még alacsony fogyasztású processzorral rendelkező eszközökön is megvalósítható, mint például intelligens kártyák, személyi számítógépek, személyazonosító okmányok . 1] . Kereskedelmi okokból a szerzők 1986. július 9-én kérték az Egyesült Államok szabadalmát . Az Egyesült Államok Szabadalmi és Védjegyhivatalának hat hónapon belül kellett döntenie a titoktartási rendszer felszámolásáról szóló határozatról [2] [3] .

A szabadalmi hivatal néhány nappal egy bizonyos időszak lejárta előtt megtiltotta a jegyzőkönyvvel kapcsolatos információk nyilvánosságra hozatalát vagy közzétételét, ezt nemzetbiztonsági veszélyként értelmezve. Sőt, a szerzőknek értesíteniük kellett minden amerikai állampolgárt, aki ismeri a Feig-Fiat-Shamir rendszert, hogy nyilvánosságra hozataluk súlyos szankciókat vonhat maga után - két év börtönt vagy tízezer dolláros bírságot. Emellett be kellett jelenteni minden olyan külföldi államot, amelyhez a tanulmányról információt közöltek [2] [3] .

Ekkorra Feige, Fiat és Shamir már számos előadást tartott Izrael, Európa és az Egyesült Államok egyetemein, és jelentkezett az Association for Computing Machinery konferenciára , amelyet 1987 májusában New Yorkban tartottak . 2] [3] .

Bár a protokoll kidolgozói abban reménykedtek, hogy a Weizmann Intézet, ahol a vizsgálatot végezték, fellebbez a végzés ellen, ennek ellenére levelet küldtek a konferencia bizottságának, amelyben ismertették a helyzetet. Ezt követően számos szervezet, például a Bell Labs és a The New York Times gyorsan csatlakozott a probléma megoldásához. A legnagyobb hozzájárulást a Nemzetbiztonsági Ügynökség (NSA) tette, amely kezdetben nem tudott a kiadott végzésről. Miután erről értesítették az NSA-t, két napon belül a rendelést törölték [2] [3] .

Shamir május 26-án felszólalt az Association for Computing Machinery konferenciáján [4] , majd 5 nappal később a szerzők szabadalmat kaptak a kifejlesztett protokollra [5] .

Azonosítási séma

A körök során bizonyítja B -nek a titok ismeretét anélkül, hogy a titok egyetlen darabját is felfedné [1] . $s$ $t$

Rendszerbeállítások kiválasztása

A T megbízható központ nagy számot tesz közzé , ahol és olyan prímszámok, amelyeket titokban tartanak. Az egész számok és a biztonsági paraméterek [6] is ki vannak választva . $n=pq$ $p$ $q$ $k$ $t$

Titkok generálása a résztvevők számára

Minden résztvevő véletlenszerű egész számokat és véletlenszerű biteket választ . $k$ $s_1, s_2, ..., s_k, 1 \leqslant s_i \leqslant n-1$ $k$ $b_1, b_2, ..., b_k$

Aztán kiszámolja . $v_i = (-1)^{b_i}\cdot (s_i^2)^{-1} \mod n, 1 \leqslant i \leqslant k$

A résztvevő a nyilvános kulcsaként működő értékek segítségével azonosítja magát mások előtt, míg a titkos kulcsot csak a résztvevő ismeri [6] . $(v_1, v_2, ..., v_k; n)$ $s = (s_1, s_2, ..., s_k)$

Protokoll akciók egy körön belül

A véletlenszerű egész számot választ $r, 1 \leqslant r \leqslant n-1$ kiszámítja: és elküldi B félnek . $x = r^2 \mod n$ $x$
B egy véletlen bites vektort küld A-nak, ahol vagy . $k$ $(e_1, e_2, ..., e_k)$ $e_i = 0$ $e_i = 1$
A kiszámítja és elküldi B -nek : . $y = r\cdot \prod^{k}_{i=1}s_i^{e_i} \mod n$
B kiértékeli: és ellenőrzi, hogy és [7] [6] . $z = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$ $z=\pm x\mod n$ $z \neq 0$

Biztonság

1. lemma: Ha A és B követi a protokollt, akkor B mindig elfogadja az A bizonyítást : Bizonyítás: definíció szerint

$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 "Hogyan bizonyítsd magad: gyakorlati megoldások az azonosítási és aláírási problémákra"

Feltételezve, hogy a faktoring számításilag lehetetlen feladat, a sikeres protokolltámadás valószínűsége . A támadó megpróbálhat becsületes felhasználót kiadni úgy, hogy kitalálja a helyes értékeit , felkészül az első lépésre, és megadja a harmadik lépésben. Akkor B gondoskodik róla . De az értékek helyes megválasztásának valószínűsége egy körben van, és ezért a teljes protokollban [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}$

Így például a biztonsági szint eléréséhez elegendő a és a . Ez azt jelenti, hogy egy tisztességtelen felhasználó által az ellenőrző megtévesztésére tett millió kísérletből csak egy lehet sikeres. $2^{-20}$ $k = 5$ $t=4$

A protokoll bizonyítja, hogy A -nak van privát kulcsa anélkül, hogy felfedné, hogy mikor és [1] . $k = O(\log \log n)$ $t = O(\log n)$

Példa

Hagyja , hogy T megbízható központ válasszon prímszámokat , és tegye közzé . Rendszerbiztonsági beállítások: , . $p=683$ $q = 811$ $n=pq=553913$ $k = 3$ $t=1$
Az A résztvevő számára véletlenszerű számok kerülnek kiválasztásra: , , és 3 bit: , , . $s_1 = 187$ $s_2 = 37411$ $s_3 = 5204$ $b_1 = 1$ $b_2 = 1$ $b_3 = 0$ az értékek kiszámítása: , , . $v_1 = 307124$ $v_2 = 115268$ $v_3 = 403211$ Nyilvános kulcs A : , privát kulcs: . $(307124, 115268, 403211; 553913)$ $(187, 37411, 5204)$
(a) A kiválaszt egy véletlenszámot , egy véletlen bitet , kiszámítja: és elküldi B -nek . $r=1337$ $b = 1$ $x=428083$

(b) B küld A-nak egy 3 bites vektort: .

(0,1,0)

y=r\cdot s_2\mod n=166337

(d) B kiszámítja: és elfogadja A bizonyítását mivel és .

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

z=\pm x\mod n

z \neq 0

Azonosítási séma fejlesztései és módosításai

Megtagadhatja a közös szám kiválasztását minden résztvevő számára , és megengedheti, hogy mindegyikük válassza ki a saját számát. Mindazonáltal egy T megbízható központ meglétére továbbra is szükség lesz ahhoz, hogy minden résztvevőt hozzá lehessen rendelni a moduljához [6] . $n$
Az A és B közötti interakció bonyolultságának csökkentése érdekében az A - ból B -be küldött első üzenetet lecserélheti egy hash értékre . Ennek megfelelően a protokoll utolsó iterációjában B - nek kell működnie a [6] helyett . $x$ $h(x)$ $h(z)$ $z$
A séma módosítható az egyes résztvevők személyazonossága alapján. Ehhez a T megbízható központ minden A felhasználóhoz hozzárendel egy egyedi azonosító karakterláncot a résztvevővel kapcsolatos információkkal (például név, cím, útlevélszám stb.). Ezután a központ kiszámítja azokat az értékeket , amelyek polinomiális időben nem különböztethetők meg egy véletlen függvénytől. Ezután a faktorizáció ismeretében a megbízható központ kiszámítja és kiadja az értékeit A. Az értékek és az A résztvevő nyilvános és privát kulcsaivá válnak, és a további műveleteket a fent leírt séma szerint hajtják végre [7] [6] [3] . $én_{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}$
A leírt protokoll párhuzamosan is végrehajtható. Ebben az esetben az A-ból B-be és vissza küldött üzeneteknek tartalmazniuk kell egyidejűleg minden körre vonatkozó adatokat . Ennek a megközelítésnek az az előnye, hogy lehetővé teszi a végrehajtás bonyolultságának csökkentését az előállított iterációk számának csökkentésével. Egy ilyen séma biztonságos, de technikai okok miatt elveszti tudás nélküli tulajdonságát. A helyzet az, hogy a párhuzamos végrehajtás lehetővé teszi a tisztességtelen B ellenőrző számára, hogy ne véletlenszerűen, hanem az A -tól első lépésben neki küldött teljes halmaz függvényeként határozzon . Ha B ezt egy egyirányú hash függvény segítségével teszi meg, akkor csak akkor tud olyan információt szerezni, amelyet egyébként ki tudna számítani, ha ismeri A titkát . Úgy véljük azonban, hogy ez az információ nem "hasznos" (ennek ismeretében B nem fogja tudni kiadni A -t egy másik résztvevőnek), ami lehetővé teszi számunkra, hogy a sémát továbbra is megbízhatónak tekintsük [1] [8] . $t$ $e_{it}$ $x_t$

Aláírás Feig - Fiat - Shamira

B fél nagyon fontos szerepet játszik az interaktív identitássémában - véletlenszerű értékeket generál , amelyek megakadályozzák, hogy A résztvevő csaljon . $e_{i}$

Ahhoz, hogy az azonosítási sémát aláírási sémává alakítsuk, elegendő ezt a B műveletet megváltoztatni , hogy egy titkos hash függvényt használjunk a [7] [6] [3] kiszámításához . $h$ $e_{i}$

Üzenet aláírása

Hagyja , hogy A aláírjon egy üzenetet . $m$

A kiválaszt egy véletlenszerű egész számot , és kiszámítja: . $r, 1 \leqslant r \leqslant n-1$ $x = r^2 \mod n$
A kiszámítja: . $e_i = h(x||m), 1 \leqslant i \leqslant k$
A kiszámítja: . $y = r\cdot \prod^{k}_{i=1}s_i^{e_i} \mod n$
A küld B -nek egy üzenetet , aláírást és . $m$ $(e_1, e_2, ..., e_k)$ $y$

Aláírás ellenőrzése

Hagyja , hogy B ellenőrizze az aláírást az üzenet alatt . $m$

B kiszámítja: . $x' = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$
B a kiszámításához használja : . $x'$ $e'_i$ $e'_i = h(x'||m), 1 \leqslant i \leqslant k$
Ha a számított értékek megegyeznek az A - tól kapott aláírással , akkor B elfogadja az aláírást . $(e'_1, e'_2, ..., e'_k)$ $(e_1, e_2, ..., e_k)$ $m$

Jegyzetek

↑ 1 2 3 4 5 Feige, Uriel; Fiat, Amos; Shamir, Adi. Zero-knowledge identitásigazolások (angol) (elérhetetlen link) (1987). Letöltve: 2015. november 10. Az eredetiből archiválva : 2015. november 17..
↑ 1 2 3 4 Susan Landau. Zero Knowledge and the Department of Defense (angol) (1988). Letöltve: 2015. november 10. Az eredetiből archiválva : 2016. január 16..
↑ 1 2 3 4 5 6 Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, C-forráskódok (2002). Letöltve: 2015. november 10. Az eredetiből archiválva : 2015. november 20.. (határozatlan)
↑ Alfred V. Aho. STOC'87 19. éves ACM konferencia a számítástechnika elméletéről . ACM New York, NY, USA (1987).
↑ Az azonosításra és aláírásra szolgáló módszer, készülék és cikk ( 1987. május 31.). Letöltve: 2015. november 11. Az eredetiből archiválva : 2015. november 21..
↑ 1 2 3 4 5 6 7 A. Menezes, P. van Oorschot és S. Vanstone. Handbook of Applied Cryptography (angol) (1996). Letöltve: 2015. november 10. Az eredetiből archiválva : 2015. december 8..
↑ 1 2 3 Amos Fiat, Adi Shamir. Hogyan bizonyítsd magad: Gyakorlati megoldások azonosítási és aláírási problémákra (angol) (hivatkozás nem elérhető) (1986). Letöltve: 2015. november 10. Az eredetiből archiválva : 2016. március 3.
↑ Gilles Brassard, Claude Crepeau, Moti Yung. Az NP-ben minden tökéletes nulla tudásban vitatható korlátozott számú körben (angolul) (1989). Hozzáférés időpontja: 2015. november 13. Az eredetiből archiválva : 2015. november 17.

Irodalom

Fiat A. , Shamir A. Hogyan bizonyítsd be magad: Az azonosítási és aláírási problémák gyakorlati megoldásai // Advances in Cryptology - CRYPTO '86 :6th Annual International Cryptology Conference, Santa Barbara, California, USA, 1986, Proceedings / A. M. Odlyzko - Berlin , Heidelberg , New York, NY , London [stb.] : Springer Berlin Heidelberg , 1987. - P. 186-194. — 490 p. - ( Számítástechnikai előadások jegyzetei ; 263. kötet) - ISBN 978-3-540-18047-0 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-47721-7_12
Landau S. Zero Knowledge and the Department of Defense // Megjegyzések Amer . Math. szoc. / F. Morgan - AMS , 1988. - Vol. 35, Iss. 1. - P. 5-12. — ISSN 0002-9920 ; 1088-9477
Feige U. , Fiat A. , Shamir A. Zero-Knowledge Proofs of Identity (angol) // Journal of Cryptology / I. Damgård - Springer Science + Business Media , International Association for Cryptologic Research , 1988. - Vol. 1, Iss. 2. - P. 77-94. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF02351717
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (angol) - CRC Press , 1996. - 816 p. — ( Diszkrét matematika és alkalmazásai ) — ISBN 978-0-8493-8523-0
Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .