Protokol Feig - Fiat - Shamir

Protokol Feig-Fiat-Shamir je identifikační protokol s nulovými znalostmi , zobecnění dřívějšího protokolu Fiat-Shamir , který vyvinuli Uriel Feige , Amos Fiat [ ] a Adi Shamir . ) v roce 1986. Toto jednoduché implementovatelné a komerčně významné schéma bylo autory patentováno rok po jeho vývoji.

Protokol umožňuje jedné straně (prověřovatel A) prokázat druhé straně (ověřovateli B), že má tajné informace, aniž by prozradil jediný kousek této informace.

Zabezpečení protokolu je založeno na obtížnosti extrahování modulu druhé odmocniny dostatečně velkého složeného čísla n, jehož faktorizace není známa.

Hlavní verze protokolu obsahuje některá vylepšení, která snižují složitost interakcí mezi účastníky nebo začleňují identity do schématu.

Identifikační schéma Feig-Fiat-Shamir lze navíc snadno převést na schéma podpisu.

Historie

V roce 1986 izraelští vědci z Wyman Institute Uriel Feige, Amos Fiat a Adi Shamir vyvinuli praktické identifikační schéma s nulovými znalostmi, které by bylo možné implementovat i na zařízeních s procesory s nízkou spotřebou, jako jsou čipové karty, osobní počítače, osobní identifikační doklady [ 1] . Z komerčních důvodů autoři požádali o americký patent 9. července 1986 . Americký úřad pro patenty a ochranné známky musel do šesti měsíců rozhodnout o rozhodnutí o vydání příkazu k odstranění režimu utajení [2] [3] .

Jen několik dní před uplynutím určité lhůty vydal patentový úřad příkaz zakazující jakékoli zveřejnění nebo zveřejnění informací o protokolu a vysvětlil to jako ohrožení národní bezpečnosti. Autoři navíc museli upozornit všechny občany USA, kteří znají schéma Feig-Fiat-Shamir, že jejich prozrazení by mohlo vést k vážným sankcím – dvěma letům vězení nebo pokutě deset tisíc dolarů. Dále bylo nutné hlásit všechny cizí státy, kterým byly informace o studii sděleny [2] [3] .

V té době již Feige, Fiat a Shamir přednesli řadu prezentací na univerzitách v Izraeli, Evropě a Spojených státech a přihlásili se na konferenci Asociace pro výpočetní stroje , která se měla konat v New Yorku v květnu 1987 [ 2] [3] .

Přestože tvůrci protokolu doufali, že Weizmannův institut, kde byla studie provedena, se proti příkazu odvolá, přesto zaslali konferenčnímu výboru dopis s vysvětlením situace. Poté se do řešení problému rychle zapojilo mnoho organizací, jako jsou Bell Labs a The New York Times . Největší příspěvek poskytla Národní bezpečnostní agentura (NSA), která původně o vydaném rozkazu nevěděla. Poté, co byl o tom NBÚ informován, byla objednávka do dvou dnů zrušena [2] [3] .

Shamir vystoupil na konferenci Association for Computing Machinery 26. května [4] a o 5 dní později autoři obdrželi patent na vyvinutý protokol [5] .

Identifikační schéma

A dokazuje B v průběhu kol svou znalost tajemství, aniž by prozradil jediný kousek tajemství samotného [1] . $s$ $t$

Výběr možností systému

Důvěryhodné centrum T zveřejňuje velké množství , kde a jsou prvočísla, která jsou držena v tajnosti. Vybírají se také celá čísla a - bezpečnostní parametry [6] . $n=pq$ $p$ $q$ $k$ $t$

Generování tajemství pro účastníky

Každý účastník si vybere náhodná celá čísla a náhodné bity . $k$ $s_1, s_2, ..., s_k, 1 \leqslant s_i \leqslant n-1$ $k$ $b_1, b_2, ..., b_k$

Poté se počítá . $v_i = (-1)^{b_i}\cdot (s_i^2)^{-1} \mod n, 1 \leqslant i \leqslant k$

Účastník se identifikuje ostatním pomocí hodnot , které fungují jako jeho veřejný klíč, zatímco tajný klíč zná pouze účastník [6] . $(v_1, v_2, ..., v_k; n)$ $s = (s_1, s_2, ..., s_k)$

Akce protokolu v rámci jednoho kola

A vybere náhodné celé číslo $r, 1 \leqslant r \leqslant n-1$ vypočítá: a pošle straně B . $x = r^2 \mod n$ $X$
B pošle A náhodný bitový vektor kde nebo . $k$ $(e_1, e_2, ..., e_k)$ $e_i = 0$ $e_i = 1$
A vypočítá a pošle B : . $y = r\cdot \prod^{k}_{i=1}s_i^{e_i} \mod n$
B vyhodnotí: a zkontroluje to a [7] [6] . $z = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$ $z=\pm x\mod n$ $z \neq 0$

Zabezpečení

Lemma 1: Pokud A a B postupují podle protokolu, pak B vždy přijímá důkazy A : Důkaz: podle definice

$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 „Jak se prokázat: Praktická řešení problémů s identifikací a podpisem“

Za předpokladu, že faktoring je výpočetně nemožný úkol, je pravděpodobnost úspěšného útoku na protokol . Útočník se může pokusit vydávat za čestného uživatele tím, že uhodne správné hodnoty , připraví se na první krok a poskytne ve třetím kroku. Pak se B o to postará . Pravděpodobnost správného výběru hodnot je ale v jednom kole a tedy v celém protokolu [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}$

K dosažení úrovně zabezpečení tedy například stačí zvolit a . To znamená, že jen jeden z milionu pokusů nepoctivého uživatele oklamat ověřovatele může uspět. $2^{-20}$ $k = 5$ $t=4$

Protokol dokazuje, že A má svůj soukromý klíč, aniž by o něm prozradil jakoukoli znalost, kdy a [1] . $k = O(\log \log n)$ $t = O(\log n)$

Příklad

Nechte důvěryhodné centrum T vybrat prvočísla a publikovat . Nastavení zabezpečení systému: , . $p=683$ $q = 811$ $n=pq=553913$ $k = 3$ $t = 1$
Pro účastníka A jsou vybrána náhodná čísla: , , a 3 bity: , , . $s_1 = 187$ $s_2 = 37411$ $s_3 = 5204$ $b_1 = 1$ $b_2 = 1$ $b_3 = 0$ hodnoty se počítají: , , . $v_1 = 307124$ $v_2 = 115268$ $v_3 = 403211$ Veřejný klíč A : , soukromý klíč: . $(307124, 115268, 403211; 553913)$ $(187, 37411, 5204)$
(a) A vybere náhodné číslo , náhodný bit , vypočítá: a pošle ho B . $r=1337$ $b = 1$ $x=428083$

(b) B pošle A 3bitový vektor: .

(0,1,0)

y=r\cdot s_2\mod n=166337

(d) B vypočítá: a přijme důkaz A od a .

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

z=\pm x\mod n

z \neq 0

Vylepšení a úpravy identifikačního schématu

Můžete odmítnout výběr společného čísla pro všechny účastníky a umožnit každému z nich, aby si zvolil své vlastní. Existence důvěryhodného centra T však bude stále nezbytná, aby bylo možné přidružit každého účastníka k jeho modulu [6] . $n$
Chcete-li snížit složitost interakce mezi A a B , můžete první zprávu odeslanou z A do B nahradit hodnotou hash . Podle toho bude při poslední iteraci protokolu muset fungovat B namísto samotného [6] . $X$ $h(x)$ $Hz)$ $z$
Schéma lze upravit tak, aby bylo založeno na identitě každého účastníka. K tomu je každému uživateli A přiděleno důvěryhodným centrem T jedinečný identifikační řetězec s informacemi o účastníkovi (například jméno, adresa, číslo pasu atd.). Poté centrum vypočítá hodnoty , kde by měly být k nerozeznání od náhodné funkce v polynomiálním čase. Poté, se znalostí faktorizace , důvěryhodné centrum vypočítá a vydá jejich hodnoty A . Hodnoty a stávají se veřejným a soukromým klíčem účastníka A a další akce se provádějí podle schématu popsaného výše [7] [6] [3] . $IA}$ $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}$
Popsaný protokol lze provádět paralelně. V tomto případě musí zprávy odeslané z A do B a zpět obsahovat data pro všechna kola současně. Výhodou tohoto přístupu je, že vám umožňuje snížit složitost provádění snížením počtu vyrobených iterací. Takové schéma je bezpečné, ale z technických důvodů ztrácí svou vlastnost nulových znalostí. Faktem je, že paralelní provádění může umožnit nepoctivému ověřovateli B určovat nikoli náhodně, ale jako funkce celé množiny , kterou mu v prvním kroku poslal A. Pokud to B provede pomocí jednosměrné hašovací funkce , bude moci získat informace, které by jinak mohl vypočítat, pouze pokud by znal tajemství A. Má se však za to, že tato informace není „užitečná“ (když ji B zná, nebude se moci vydávat za A nějakému jinému účastníkovi), což nám umožňuje považovat schéma stále za spolehlivé [1] [8] . $t$ $e_{it}$ $x_t$

Podpis Feig - Fiat - Shamira

Strana B hraje velmi důležitou roli v interaktivním schématu identity – generuje náhodné hodnoty , které zabraňují účastníkovi A podvádět . $e_{i}$

Aby bylo možné převést identifikační schéma na schéma podpisu, stačí změnit tuto akci B na použití tajné hašovací funkce pro výpočet [7] [6] [3] . $h$ $e_{i}$

Podpis zprávy

Nechte A podepsat zprávu . $m$

A vybere náhodné celé číslo a vypočítá: . $r, 1 \leqslant r \leqslant n-1$ $x = r^2 \mod n$
A počítá: . $e_i = h(x||m), 1 \leqslant i \leqslant k$
A počítá: . $y = r\cdot \prod^{k}_{i=1}s_i^{e_i} \mod n$
A odešle B zprávu , podpis a . $m$ $(e_1, e_2, ..., e_k)$ $y$

Ověření podpisu

Nechť B chce zkontrolovat podpis pod zprávou . $m$

B vypočítá: . $x' = y^2\cdot \prod^{k}_{i=1} v_i^{e_i} \mod n$
B používá k výpočtu : . $X'$ $e'_i$ $e'_i = h(x'||m), 1 \leqslant i \leqslant k$
Pokud se vypočítané hodnoty shodují s podpisem přijatým od A , pak B podpis přijme . $(e'_1, e'_2, ..., e'_k)$ $(e_1, e_2, ..., e_k)$ $m$

Poznámky

↑ 1 2 3 4 5 Feige, Uriel; Fiat, Amos; Shamire, Adi. Doklady totožnosti s nulovými znalostmi (anglicky) (nepřístupný odkaz) (1987). Získáno 10. listopadu 2015. Archivováno z originálu 17. listopadu 2015.
↑ 1 2 3 4 Susan Landau. Nulové znalosti a ministerstvo obrany (anglicky) (1988). Staženo 10. listopadu 2015. Archivováno z originálu 16. ledna 2016.
↑ 1 2 3 4 5 6 Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojové kódy C (2002). Získáno 10. listopadu 2015. Archivováno z originálu 20. listopadu 2015. (neurčitý)
↑ Alfred V. Aho. STOC'87 19. výroční konference ACM o teorii výpočetní techniky . ACM New York, NY, USA (1987).
↑ Metoda, zařízení a předmět pro identifikaci a podpis ( 31. května 1987). Získáno 11. listopadu 2015. Archivováno z originálu 21. listopadu 2015.
↑ 1 2 3 4 5 6 7 A. Menezes, P. van Oorschot a S. Vanstone. Handbook of Applied Cryptography (anglicky) (1996). Získáno 10. listopadu 2015. Archivováno z originálu 8. prosince 2015.
↑ 1 2 3 Amos Fiat, Adi Shamir. Jak se prokázat: Praktická řešení problémů s identifikací a podpisem (anglicky) (odkaz není k dispozici) (1986). Získáno 10. listopadu 2015. Archivováno z originálu 3. března 2016.
↑ Gilles Brassard, Claude Crepeau, Moti Yung. Všechno v NP lze argumentovat v dokonalé nulové znalosti v omezeném počtu kol (anglicky) (1989). Datum přístupu: 13. listopadu 2015. Archivováno z originálu 17. listopadu 2015.

Literatura

Fiat A. , Shamir A. Jak se prokázat: Praktická řešení problémů s identifikací a podpisem // Pokroky v kryptologii - CRYPTO '86 :6. výroční mezinárodní kryptologická konference, Santa Barbara, Kalifornie, USA, 1986, sborník příspěvků / A. M. Odlyzko - Berlín , Heidelberg , New York, NY , Londýn [atd.] : Springer Berlin Heidelberg , 1987. - S. 186-194. — 490p. - ( 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. Nulové znalosti a ministerstvo obrany // Notices Amer . Matematika. soc. / F. Morgan - AMS , 1988. - Sv. 35, Iss. 1. - S. 5-12. — ISSN 0002-9920 ; 1088-9477
Feige U. , Fiat A. , Shamir A. Zero-Knowledge Proofs of Identity (anglicky) // 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 (anglicky) - CRC Press , 1996. - 816 s. — ( Diskrétní matematika a její aplikace ) — ISBN 978-0-8493-8523-0
Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .