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

Գաղտնագրման մեջ Ֆեյգ֊Ֆիատ֊Շամիրի նույնականացման արձանագրությունը զրո իմացությամբ զուգահեռ ապացուցման արձանագրություն է ստեղծված Ուրիել Ֆեյգի, Ամոս Ֆիատի
և Ադի Շամիրի կողմից 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 թվերից՝ քառակուսի արմատի հաշվարկման խնդրի դժվարության պատճառով, երբ մոդուլի ֆակտորիզացիան անհայտ է։

## Ընթացակարգ
# Ալիսը ընտրում է պատահական r\in\{1,n-1\} թիվը և պատահական s\in\{-1,1\} նշանը և հաշվարկում է x \equiv s\cdot r^2 \pmod{n}։ Ալիսը Վիկտորին է ուղարկում x֊ը։
# Վիկտորը ընտրում է a_1, \cdots, a_k թվերը, որտեղ a_i հավասար է 0 կամ 1։ Վիկտորը այս թվերը ուղարկում է Ալիսին։
# Ալիսը հաշվարկում է y \equiv rs_1^{a_1}s_2^{a_2} \cdots s_k^{a_k}\pmod{n}։ Ալիսը այս թիվը ուղարկում է Վիկտորին։
# Վիկտորը ստուգում է այս արտահայտությունը՝ y^2 \equiv \pm\, x v_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^{k t}֊ի մեջ։

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

## Աղբյուրներ
*
*

Կատեգորիա:Գաղտնագրություն