Ֆեյգ-Ֆիատ-Շամիրի նույնականացման արձանագրություն

Գաղտնագրման մեջ Ֆեյգ֊Ֆիատ֊Շամիրի նույնականացման արձանագրությունը զրո իմացությամբ զուգահեռ ապացուցման արձանագրություն է ստեղծված Ուրիել Ֆեյգի, Ամոս Ֆիատի և Ադի Շամիրի կողմից 1988 թ.։ Ինչպես բոլոր զրո իմացությամբ արձանագրությունները, Ֆեյգ֊Ֆիատ֊Շամիրի նույնականացման արձանագրությունը թույլ է տալիս մի կողմին՝ Ալիսին, ապացուցել մյուս կողմին՝ Վիկտորին, որ նա տիրապետում է ինչ֊որ գաղտնի ինֆորմացիայի, առանց բացահայտելու Վիկտորին, թե ինչ գաղտնի ինֆորմացիա է դա։ Ֆեյգ֊Ֆիատ֊Շամիրի նույնականացման արձանագրությունը օգտագործում է մոդուլային թվաբանություն և զուգահեռ ստուգման պրոցես, որը սահմանափակում է Ալիսի և Վիկտորի միջև հնարավոր հաղորդումների քանակը։

Նախապատրաստում

Ընտրվում են երկու խոշոր պարզ թվեր՝ $p$ և $q$ ու հաշվարկվում է դրանց արտադրյալը՝ $n=pq$։ Ստեղծվում են $s_{1},\cdots ,s_{k}$ գաղտնի թվերը, որոնցից յուրաքանչյուրի ամենամեծ ընդհանուր բաժանելին $n$֊ի հետ 1 է՝ $gcd(s_{i},n)=1$ և $s_{i}\in \{1,n-1\}$։ Հաշվարկվում է $v_{i}\equiv s_{i}^{2}{\pmod {n}}$։ Ալիսը և Վիկտորը ստանում են $n$֊ը, իսկ $p$ և $q$ պահվում են գաղտնի։ Հետո Ալիսին են ուղարկվում $s_{i}$ թվերը։ Սրանք նրա գաղտնի մուտքի թվերն են։

Վիկտորին են ուղարկվում $v_{i}$ թվերը։ Վիկտորը ի վիճակի չէ վերականգել Ալիսի $s_{i}$ թվերը իր $v_{i}$ թվերից՝ քառակուսի արմատի հաշվարկման խնդրի դժվարության պատճառով, երբ մոդուլի ֆակտորիզացիան անհայտ է։

Ընթացակարգ

1. Ալիսը ընտրում է պատահական $r\in \{1,n-1\}$ թիվը և պատահական $s\in \{-1,1\}$ նշանը և հաշվարկում է $x\equiv s\cdot r^{2}{\pmod {n}}$։ Ալիսը Վիկտորին է ուղարկում $x$֊ը։
2. Վիկտորը ընտրում է $a_{1},\cdots ,a_{k}$ թվերը, որտեղ $a_{i}$ հավասար է 0 կամ 1։ Վիկտորը այս թվերը ուղարկում է Ալիսին։
3. Ալիսը հաշվարկում է $y\equiv rs_{1}^{a_{1}}s_{2}^{a_{2}}\cdots s_{k}^{a_{k}}{\pmod {n}}$։ Ալիսը այս թիվը ուղարկում է Վիկտորին։
4. Վիկտորը ստուգում է այս արտահայտությունը՝ $y^{2}\equiv \pm \,xv_{1}^{a_{1}}v_{2}^{a_{2}}\cdots v_{k}^{a_{k}}{\pmod {n}}.$

Այս գործողությունները կրկնվում են տարբեր $r$ և $a_{i}$ արժեքներով մինչև Վիկտորը համոզվում է որ Ալիսը իսկապես գիտի իր $v_{i}$ թվերի մոդուլային քառակուսի արմատները ($s_{i}$)։

Անվտանգություն

Այս ընթացակարգում Ալիսը Վիկտորին որևէ օգտակար տեղեկատվություն չի տալիս։ Նա պարզապես ապացուցում է Վիկտորին, որ գիտի գաղտնի թվերը առանց բացահայտելու այդ թվերը։ Ցանկացած անձ, ով գաղտնալսում է նրանց միջև յուրաքանչյուր կապ, ամեն անգամ կիմանա նույն տեղեկատվությունը։

Գաղտնալսողը Ալիսի գաղտնի թվերի մասին ոչ մի օգտակար բան չի իմանա։

Այս արձանագրության հին տարբերակներում «Ֆիատ֊Շամիրի սխեման» (որի վրա հիմնված է Ֆեյգ֊Ֆիատ֊Շամիրի սխեման), արտահոսվում էր մի բիթ ինֆորմացիա։ $s$ նշանի ներմուծմամբ նույնիսկ այդ բիթն էր թաքցվում, ինչի արդյունքում ստացվում էր զրո իմացությամբ արձանագրություն։

Ենթադրենք Եվան գաղտնալսմամբ ստացել է Վիկտորի $v_{i}$ թվերը, սակայն չգիտի թե որոնք են Ալիսի $s_{i}$ թվերը։

Եթե Եվան փորձի Վիկտորին համոզել որ ինքը Ալիսն է, նա պետք է ճիշտ կռահի թե Վիկտորի $a_{i}$ թվերը։ Նա հետո ընտրում է պատահական $y$ թիվ, հաշվարկում է $x\equiv y^{2}v_{1}^{-a_{1}}v_{2}^{-a_{2}}\cdots v_{k}^{-a_{k}}{\pmod {n}}$ և Վիկտորին է ուղարկում $x$֊ը։ Երբ Վիկտորը ուղարկում է $a_{i}$, Եվան պարզապես հետ է ուղարկում իր $y$֊ը։

Վիկտոր գոհ է և եզրակացնում է, որ Եվան ունի գաղտնի թվերը։ Սակայն հավանականությունը այն բանի, որ Եվան ճիշտ կկռահի, թե որոնք են Վիկտորի $a_{i}$ թվերը, կլինի 1֊ը $2^{k}$֊ի մեջ։ Այս ընթացակարգը կրկնելով $t$ անգամ, հավանականությունը ընկնում է 1֊ը $2^{kt}$֊ի մեջ։

$k=5$ և $t=4$ դեպքում որպես Ալիս հանդես գալու հավանականությունը փոքր է քան 1֊ը միլիոնում։

Աղբյուրներ

• Feige, Uriel; Fiat, Amos; Shamir, Adi (1988). «Zero-knowledge proofs of identity». Journal of Cryptology. 1 (2): 77–94. doi:10.1007/BF02351717. Արխիվացված է օրիգինալից 2012 թ․ դեկտեմբերի 17-ին. Վերցված է 2014 թ․ փետրվարի 10-ին.
• Trappe, Wade; Washington, Lawrence C. (2003). Introduction to Cryptography with Coding Theory. Upper Saddle River: Prentice-Hall. էջեր 231–233. ISBN 0-13-061814-4.