Ֆեյգ-Ֆիատ-Շամիրի նույնականացման արձանագրություն
Գաղտնագրման մեջ Ֆեյգ֊Ֆիատ֊Շամիրի նույնականացման արձանագրությունը զրո իմացությամբ զուգահեռ ապացուցման արձանագրություն է ստեղծված Ուրիել Ֆեյգի, Ամոս Ֆիատի և Ադի Շամիրի կողմից 1988 թ.։ Ինչպես բոլոր զրո իմացությամբ արձանագրությունները, Ֆեյգ֊Ֆիատ֊Շամիրի նույնականացման արձանագրությունը թույլ է տալիս մի կողմին՝ Ալիսին, ապացուցել մյուս կողմին՝ Վիկտորին, որ նա տիրապետում է ինչ֊որ գաղտնի ինֆորմացիայի, առանց բացահայտելու Վիկտորին, թե ինչ գաղտնի ինֆորմացիա է դա։ Ֆեյգ֊Ֆիատ֊Շամիրի նույնականացման արձանագրությունը օգտագործում է մոդուլային թվաբանություն և զուգահեռ ստուգման պրոցես, որը սահմանափակում է Ալիսի և Վիկտորի միջև հնարավոր հաղորդումների քանակը։
Նախապատրաստում
[խմբագրել | խմբագրել կոդը]Ընտրվում են երկու խոշոր պարզ թվեր՝ և ու հաշվարկվում է դրանց արտադրյալը՝ ։ Ստեղծվում են գաղտնի թվերը, որոնցից յուրաքանչյուրի ամենամեծ ընդհանուր բաժանելին ֊ի հետ 1 է՝ և ։ Հաշվարկվում է ։ Ալիսը և Վիկտորը ստանում են ֊ը, իսկ և պահվում են գաղտնի։ Հետո Ալիսին են ուղարկվում թվերը։ Սրանք նրա գաղտնի մուտքի թվերն են։
Վիկտորին են ուղարկվում թվերը։ Վիկտորը ի վիճակի չէ վերականգել Ալիսի թվերը իր թվերից՝ քառակուսի արմատի հաշվարկման խնդրի դժվարության պատճառով, երբ մոդուլի ֆակտորիզացիան անհայտ է։
Ընթացակարգ
[խմբագրել | խմբագրել կոդը]- Ալիսը ընտրում է պատահական թիվը և պատահական նշանը և հաշվարկում է ։ Ալիսը Վիկտորին է ուղարկում ֊ը։
- Վիկտորը ընտրում է թվերը, որտեղ հավասար է 0 կամ 1։ Վիկտորը այս թվերը ուղարկում է Ալիսին։
- Ալիսը հաշվարկում է ։ Ալիսը այս թիվը ուղարկում է Վիկտորին։
- Վիկտորը ստուգում է այս արտահայտությունը՝
Այս գործողությունները կրկնվում են տարբեր և արժեքներով մինչև Վիկտորը համոզվում է որ Ալիսը իսկապես գիտի իր թվերի մոդուլային քառակուսի արմատները ()։
Անվտանգություն
[խմբագրել | խմբագրել կոդը]Այս ընթացակարգում Ալիսը Վիկտորին որևէ օգտակար տեղեկատվություն չի տալիս։ Նա պարզապես ապացուցում է Վիկտորին, որ գիտի գաղտնի թվերը առանց բացահայտելու այդ թվերը։ Ցանկացած անձ, ով գաղտնալսում է նրանց միջև յուրաքանչյուր կապ, ամեն անգամ կիմանա նույն տեղեկատվությունը։
Գաղտնալսողը Ալիսի գաղտնի թվերի մասին ոչ մի օգտակար բան չի իմանա։
Այս արձանագրության հին տարբերակներում «Ֆիատ֊Շամիրի սխեման» (որի վրա հիմնված է Ֆեյգ֊Ֆիատ֊Շամիրի սխեման), արտահոսվում էր մի բիթ ինֆորմացիա։ նշանի ներմուծմամբ նույնիսկ այդ բիթն էր թաքցվում, ինչի արդյունքում ստացվում էր զրո իմացությամբ արձանագրություն։
Ենթադրենք Եվան գաղտնալսմամբ ստացել է Վիկտորի թվերը, սակայն չգիտի թե որոնք են Ալիսի թվերը։
Եթե Եվան փորձի Վիկտորին համոզել որ ինքը Ալիսն է, նա պետք է ճիշտ կռահի թե Վիկտորի թվերը։ Նա հետո ընտրում է պատահական թիվ, հաշվարկում է և Վիկտորին է ուղարկում ֊ը։ Երբ Վիկտորը ուղարկում է , Եվան պարզապես հետ է ուղարկում իր ֊ը։
Վիկտոր գոհ է և եզրակացնում է, որ Եվան ունի գաղտնի թվերը։ Սակայն հավանականությունը այն բանի, որ Եվան ճիշտ կկռահի, թե որոնք են Վիկտորի թվերը, կլինի 1֊ը ֊ի մեջ։ Այս ընթացակարգը կրկնելով անգամ, հավանականությունը ընկնում է 1֊ը ֊ի մեջ։
և դեպքում որպես Ալիս հանդես գալու հավանականությունը փոքր է քան 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.