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

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

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

Ընտրվում են երկու խոշոր պարզ թվեր՝ $p$ և $q$ ու հաշվարկվում է դրանց արտադրյալը՝ $n = p q$ ։ Ստեղծվում են $s_{1}, \dots, s_{k}$ գաղտնի թվերը, որոնցից յուրաքանչյուրի ամենամեծ ընդհանուր բաժանելին $n$ ֊ի հետ 1 է՝ $g c d (s_{i}, n) = 1$ և $s_{i} \in {1, n - 1}$ ։ Հաշվարկվում է $v_{i} \equiv s_{i}^{2} (\mod 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} (\mod n)$ ։ Ալիսը Վիկտորին է ուղարկում $x$ ֊ը։
Վիկտորը ընտրում է $a_{1}, \dots, a_{k}$ թվերը, որտեղ $a_{i}$ հավասար է 0 կամ 1։ Վիկտորը այս թվերը ուղարկում է Ալիսին։
Ալիսը հաշվարկում է $y \equiv r s_{1}^{a_{1}} s_{2}^{a_{2}} \dots s_{k}^{a_{k}} (\mod n)$ ։ Ալիսը այս թիվը ուղարկում է Վիկտորին։
Վիկտորը ստուգում է այս արտահայտությունը՝ $y^{2} \equiv \pm x v_{1}^{a_{1}} v_{2}^{a_{2}} \dots v_{k}^{a_{k}} (\mod 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}} \dots v_{k}^{- a_{k}} (\mod n)$ և Վիկտորին է ուղարկում $x$ ֊ը։ Երբ Վիկտորը ուղարկում է $a_{i}$ , Եվան պարզապես հետ է ուղարկում իր $y$ ֊ը։

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

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

Աղբյուրներ

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

Բովանդակություն

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

Ընթացակարգ

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

Աղբյուրներ

Նավարկման ցանկ

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

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

Ընթացակարգ

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

Աղբյուրներ

Նավարկման ցանկ

Որոնում