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

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


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


== Ընթացակարգ ==
Ալիսը ընտրում է պատահական 
  
    
      
        r
        ∈
        {
        1
        ,
        n
        −
        1
        }
      
    
    {\displaystyle r\in \{1,n-1\}}
   թիվը և պատահական 
  
    
      
        s
        ∈
        {
        −
        1
        ,
        1
        }
      
    
    {\displaystyle s\in \{-1,1\}}
   նշանը և հաշվարկում է 
  
    
      
        x
        ≡
        s
        ⋅
        
          r
          
            2
          
        
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle x\equiv s\cdot r^{2}{\pmod {n}}}
  ։ Ալիսը Վիկտորին է ուղարկում 
  
    
      
        x
      
    
    {\displaystyle x}
  ֊ը։
Վիկտորը ընտրում է 
  
    
      
        
          a
          
            1
          
        
        ,
        ⋯
        ,
        
          a
          
            k
          
        
      
    
    {\displaystyle a_{1},\cdots ,a_{k}}
   թվերը, որտեղ 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   հավասար է 0 կամ 1։ Վիկտորը այս թվերը ուղարկում է Ալիսին։
Ալիսը հաշվարկում է 
  
    
      
        y
        ≡
        r
        
          s
          
            1
          
          
            
              a
              
                1
              
            
          
        
        
          s
          
            2
          
          
            
              a
              
                2
              
            
          
        
        ⋯
        
          s
          
            k
          
          
            
              a
              
                k
              
            
          
        
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle y\equiv rs_{1}^{a_{1}}s_{2}^{a_{2}}\cdots s_{k}^{a_{k}}{\pmod {n}}}
  ։ Ալիսը այս թիվը ուղարկում է Վիկտորին։
Վիկտորը ստուգում է այս արտահայտությունը՝ 
  
    
      
        
          y
          
            2
          
        
        ≡
        ±
        
        x
        
          v
          
            1
          
          
            
              a
              
                1
              
            
          
        
        
          v
          
            2
          
          
            
              a
              
                2
              
            
          
        
        ⋯
        
          v
          
            k
          
          
            
              a
              
                k
              
            
          
        
        
          
          (
          mod
          
          n
          )
        
        .
      
    
    {\displaystyle y^{2}\equiv \pm \,xv_{1}^{a_{1}}v_{2}^{a_{2}}\cdots v_{k}^{a_{k}}{\pmod {n}}.}
  Այս գործողությունները կրկնվում են տարբեր 
  
    
      
        r
      
    
    {\displaystyle r}
   և 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   արժեքներով մինչև Վիկտորը համոզվում է որ Ալիսը իսկապես գիտի իր 
  
    
      
        
          v
          
            i
          
        
      
    
    {\displaystyle v_{i}}
   թվերի մոդուլային քառակուսի արմատները (
  
    
      
        
          s
          
            i
          
        
      
    
    {\displaystyle s_{i}}
  )։


== Անվտանգություն ==
Այս ընթացակարգում Ալիսը Վիկտորին որևէ օգտակար տեղեկատվություն չի տալիս։ Նա պարզապես ապացուցում է Վիկտորին, որ գիտի գաղտնի թվերը առանց բացահայտելու այդ թվերը։ Ցանկացած անձ, ով գաղտնալսում է նրանց միջև յուրաքանչյուր կապ, ամեն անգամ կիմանա նույն տեղեկատվությունը։
Գաղտնալսողը Ալիսի գաղտնի թվերի մասին ոչ մի օգտակար բան չի իմանա։
Այս արձանագրության հին տարբերակներում «Ֆիատ֊Շամիրի սխեման» (որի վրա հիմնված է Ֆեյգ֊Ֆիատ֊Շամիրի սխեման), արտահոսվում էր մի բիթ ինֆորմացիա։ 
  
    
      
        s
      
    
    {\displaystyle s}
   նշանի ներմուծմամբ նույնիսկ այդ բիթն էր թաքցվում, ինչի արդյունքում ստացվում էր զրո իմացությամբ արձանագրություն։
Ենթադրենք Եվան գաղտնալսմամբ ստացել է Վիկտորի 
  
    
      
        
          v
          
            i
          
        
      
    
    {\displaystyle v_{i}}
   թվերը, սակայն չգիտի թե որոնք են Ալիսի 
  
    
      
        
          s
          
            i
          
        
      
    
    {\displaystyle s_{i}}
   թվերը։
Եթե Եվան փորձի Վիկտորին համոզել որ ինքը Ալիսն է, նա պետք է ճիշտ կռահի թե Վիկտորի 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   թվերը։
Նա հետո ընտրում է պատահական 
  
    
      
        y
      
    
    {\displaystyle y}
   թիվ, հաշվարկում է 
  
    
      
        x
        ≡
        
          y
          
            2
          
        
        
          v
          
            1
          
          
            −
            
              a
              
                1
              
            
          
        
        
          v
          
            2
          
          
            −
            
              a
              
                2
              
            
          
        
        ⋯
        
          v
          
            k
          
          
            −
            
              a
              
                k
              
            
          
        
        
          
          (
          mod
          
          n
          )
        
      
    
    {\displaystyle x\equiv y^{2}v_{1}^{-a_{1}}v_{2}^{-a_{2}}\cdots v_{k}^{-a_{k}}{\pmod {n}}}
   և Վիկտորին է ուղարկում 
  
    
      
        x
      
    
    {\displaystyle x}
  ֊ը։ Երբ Վիկտորը ուղարկում է 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
  , Եվան պարզապես հետ է ուղարկում իր 
  
    
      
        y
      
    
    {\displaystyle y}
  ֊ը։
Վիկտոր գոհ է և եզրակացնում է, որ Եվան ունի գաղտնի թվերը։ Սակայն հավանականությունը այն բանի, որ Եվան ճիշտ կկռահի, թե որոնք են Վիկտորի 
  
    
      
        
          a
          
            i
          
        
      
    
    {\displaystyle a_{i}}
   թվերը, կլինի 1֊ը 
  
    
      
        
          2
          
            k
          
        
      
    
    {\displaystyle 2^{k}}
  ֊ի մեջ։ Այս ընթացակարգը կրկնելով 
  
    
      
        t
      
    
    {\displaystyle t}
   անգամ, հավանականությունը ընկնում է 1֊ը 
  
    
      
        
          2
          
            k
            t
          
        
      
    
    {\displaystyle 2^{kt}}
  ֊ի մեջ։

  
    
      
        k
        =
        5
      
    
    {\displaystyle k=5}
   և 
  
    
      
        t
        =
        4
      
    
    {\displaystyle 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-12-17-ին։ Վերցված է 2014-02-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