Մերկլ-Հելմանի պարկային գաղտնահամակարգ

Մերկլ-Հելլման պարկային կրիպտոհամակարգը ամենավաղ հանրային բանալիով կրիպտոհամակարգերից է՝ ստեղծված Ռալֆ Մերկլի և Մարտին Հելլմանի կողմից 1978 թվականին։ Չնայած իր էլեգանտ գաղափարներին և RSA-ից բավականին պարզ լինելուն, այն կոտրվել է։


== Նկարագրությունը ==
Մերկլ-Հելլմանը ասիմետրիկ բանալիով կրիպտոհամակարգ է, ենթադրում է հաղորդակցություն երկու անհրաժեշտ բանալիներով՝ հանրային բանալի և մասնավոր բանալի։ Ավելին, ի տարբերություն RSA-ի, Միակողմանի հանրային բանալի է օգտագործվում գաղտնագրման, իսկ մասնավոր բանալին օգտագործվում է միայն գաղտնազերծման համար։ Այսպիսով, այն չի կիրառվում իսկությունը ստուգելու համար թվային ստորագրության կողմից։
Մերկլ-Հելլման համակարգը հիմնված է ենթաբազմության գումարի խնդրի վրա (պարկային կրիպտոհամակարգի մասնավոր դեպք)։ Խնդիրը հետևյալն է. տրված է թվերի A բազմություն և b թիվ, գտնել A ենթաբազմություն, որի գումարը b է։ Ընդհանուր առմամբ, այս խնդիրը հայտնի է որպես NP-ամբողջություն։ Ինչևէ, եթե թվերի բազմությունը (պարկ կոչվող) գերաճող է, այսինքն՝ բազմության յուրաքանչյուր տարրը ավելի մեծ է, քան նրանից առաջ եղած թվերի գումարը, խնդիրը «հեշտ» է և լուծվող պարզ ագահ ալգորիթմով։


=== Բանալու գեներացումը ===
Մերկլ-Հելլմանում բանալիները պարկեր են։ Հանրային բանալին «բարդ» պարկ է, իսկ մասնավորը՝ պարզ, կամ գերաճող, պարկ՝ համակցված երկու լրացուցիչ թվերով, բազմապատկիչ և modulus, որոնք օգտագործվում են գերաճող պարկը բարդ պարկի վերածելու համար։ Այս նույն թվերն օգտագործվում են բարդ պարկի ենթաբազմության գումարը վերափոխելու պարզ պարկի ենթաբազմության, որը լուծելի է։


=== Գաղտնագրում ===
Հաղորդագրությունը գաղտնագրելու համար բարդ պարկի ենթաբազմություն է ընտրվում՝ համեմատելով բանալու երկարությանը հավասար բիտերի բազմության (պարզ տեքստ) հետ, և պարզ տեքստում հանրային բանալու՝ 1-ի համապատասխանող յուրաքանչյուր անդամ ենթաբազմության բաղադրիչ դարձնելով՝ անտեսելով պարզ տեքստում 0 անդամին համապատասխանող անդամները։ Այս ենթաբազմության տարրերը համակցվում են, և արդյունքում ստացվում է ծածկագիրը։


=== Գաղտնազերծում ===
Գաղտնազերծումը հնարավոր է, քանի որ բազմապատկումը և մոդուլը օգտագործվել են պարզ գերաճող պարկը հանրային բանալի դարձնելու համար։ Հետո, պարզ ալգորիթմ օգտագործելով, պարզ պարկը կարող է լուծվել օգտագործելով O(n) թվաբանական գործողություններ, որն էլ կգաղտնազարծի հաղորդագրությունը։


== Մաթեմատիկական մեթոդ ==


=== Բանալու գեներացում ===
Գաղտնագրելու համար n-բիտանոց հաղորդագրությունները ընտրվում է գերաճող հաջորդականություն

w = (w1, w2, ..., wn)n ոչ զրոյական բնական թվերից. Վերցվում է այնպիսի պատահական q ամբողջ թիվ, որ

  
    
      
        q
        >
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          w
          
            i
          
        
      
    
    {\displaystyle q>\sum _{i=1}^{n}w_{i}}
  ,և այնպիսի պատահական ամբողջ r թիվ, որ gcd(r,q) = 1 (այսինքն՝ r-ը q-ն փոխադարձաբար պարզ են)։
q-ն ընտրվում է այնպես, որ հավաստիացնի գաղտնագրի եզակիությունը։ Եթե այն փոքր է, մեկից ավելի պարզ տեքստեր կարող են գաղտնագրվել նույն արդյունքով։ r-ը պետք է պարզ լինի q-ի նկատմամբ, այլապես այն չի ունենա հակադարձ mod q: r-ի հակադարձի առկայությունը անհրաժեշտ է դեկոդավորումը հնարավոր դարձնելու համար։
Հիմա հաշվենք հաջորդականությունը

β = (β1, β2, ..., βn)որտեղ

βi = rwi mod q.Հանրային բանալին β է, իսկ մասնավոր բանալին՝ (w, q, r).


=== Գաղտնագրում ===
Գաղտնագրելու համար n-բիտանոց հաղորդագրությունը՝

α = (α1, α2, ..., αn),որտեղ 
  
    
      
        
          α
          
            i
          
        
      
    
    {\displaystyle \alpha _{i}}
  -ը հաղորդագրության i-րդ բիտն է և 
  
    
      
        
          α
          
            i
          
        
        
          ∈
        
      
    
    {\displaystyle \alpha _{i}{\boldsymbol {\in }}}
  {0, 1}, հաշվենք

  
    
      
        c
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          α
          
            i
          
        
        
          β
          
            i
          
        
        .
      
    
    {\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.}
  Կրիպտոգրամը ստացվում է c-ն։


=== Գաղտնազերծում ===
Որպեսզի գաղտնազերծի c գաղտնագիրը՝ ստացողը պետք է գտնի հաղորդագրության αi բիտերը որոնք բավարարում են

  
    
      
        c
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          α
          
            i
          
        
        
          β
          
            i
          
        
        .
      
    
    {\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.}
  Դժվար խնդիր կստացվեր, եթե βi-երը պատահական արժեքներ լինեին։ Ինչևէ, βi-երի արժեքները ընտրվում են այնպես, որ գաղտնազերծելը վերածվեր պարզ խնդրի (w, q, r) մասնավոր բանալու հայտնի լինելու դեպքում։
Գաղտնազերծման բանալին s ամբողջ թիվ գտնելն է, որը r mod q-ի հակադարձն է։ Դա նշանակում է՝ s- բավարարում է s r mod q = 1 հավասարությանը, կամ համարժեքորեն գոյություն ունի k ամբողջ թիվ այնպես, որ sr = kq + 1: Քանի որ r-ը ընտրվել էր gcd(r,q)=1 պայմանով, ուստի հնարավոր է գտնել s և k` օգտագործելով Էվկլիդեսի ընդլայնված ալգորիթմը։ Հետո c գաղտնագիրը ստացողը հաշվում է

  
    
      
        
          c
          ′
        
        ≡
        c
        s
        
          
          (
          mod
          
          q
          )
        
        .
      
    
    {\displaystyle c'\equiv cs{\pmod {q}}.}
  Հետևաբար

  
    
      
        
          c
          ′
        
        ≡
        c
        s
        ≡
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          α
          
            i
          
        
        
          β
          
            i
          
        
        s
        
          
          (
          mod
          
          q
          )
        
        .
      
    
    {\displaystyle c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q}}.}
  Քանի որ rs mod q = 1 և βi = rwi mod q, հետևում է

  
    
      
        
          β
          
            i
          
        
        s
        ≡
        
          w
          
            i
          
        
        r
        s
        ≡
        
          w
          
            i
          
        
        
          
          (
          mod
          
          q
          )
        
        .
      
    
    {\displaystyle \beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q}}.}
  Այստեղից

  
    
      
        
          c
          ′
        
        ≡
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          α
          
            i
          
        
        
          w
          
            i
          
        
        
          
          (
          mod
          
          q
          )
        
        .
      
    
    {\displaystyle c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q}}.}
  Բոլոր wi արժեքների գումարը ավելի փոյքր է, քան q-ն, ուստի 
  
    
      
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          α
          
            i
          
        
        
          w
          
            i
          
        
      
    
    {\displaystyle \sum _{i=1}^{n}\alpha _{i}w_{i}}
   նույնպես [0,q-1] միջակայքում է։
Այսպիսով ստացողը պետք է լուծի ենթաբազմության գումարի խնդիրը

  
    
      
        
          c
          ′
        
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          α
          
            i
          
        
        
          w
          
            i
          
        
        .
      
    
    {\displaystyle c'=\sum _{i=1}^{n}\alpha _{i}w_{i}.}
  Այս խնդիրը հեշտ է քանի որ w-ն գերաճող հաջորդականություն է։
Վերցնում ենք w-ի ամենամեծ տարրը, նշանակենք wk. Եթե wk > c' , ապա αk = 0, եթե wk≤c' , ապա αk = 1. Հետո c' -ից հանում ենք  wk×αk, և կրկնում ենք քայլերը մինչև α-ն հաշվելը։


== Օրինակ ==
Նախ և առաջ ստեղծվում է գերաճող w հաջորդականություն

w = {2, 7, 11, 21, 42, 89, 180, 354}

Սա մասնավոր բանալու հիմքն է։ Այստեղից հաշվարկենք գումարը։

  
    
      
        ∑
        w
        =
        706
      
    
    {\displaystyle \sum w=706}
  Հետո ընտրենք q թիվ, որը մեծ է գումարից։

q = 881

Նաև ընտրենք r թիվ, որը 
  
    
      
        [
        1
        ,
        q
        )
      
    
    {\displaystyle [1,q)}
   միջակայքում է և պարզ է q-ի նկատմամբ։

r = 588

Մասնավոր բանալին բաղկացած է q-ից, w-ից և r-ից։
Հանրային բանալին հաշվարկելու համար գեներացնենք β բազմություն` w-ի յուրաքանչյուր տարրը բազմապատկելով r mod q -ով։

β = {295, 592, 301, 14, 28, 353, 120, 236}

քանի որ

2 * 588 mod 881 = 295
7 * 588 mod 881 = 592
11 * 588 mod 881 = 301
21 * 588 mod 881 = 14
42 * 588 mod 881 = 28
89 * 588 mod 881 = 353
180 * 588 mod 881 = 120
354 * 588 mod 881 = 236

β հաջորդականությունը կառուցում է հանրային բանալին։
Օրինակ Էլիսը որոշում է գաղտնագրել «a» տառը. Նախ և առաջ նա պետք է "a"-ն վերախի երկուական կոդի (այս դեպքում օգտագործելով en:ASCII կամ en:UTF-8)

01100001

Նա համապատասխանաբար բիտերը բազմապատկում է β-ի թվերի հետ։

a = 01100001
0 * 295
+ 1 * 592
+ 1 * 301
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
= 1129

Սա նա ուղարկում է ստացողին։
Գաղտնազերծելու համար Բոբը 1129 բազմապատկում է r −1 mod 
  
    
      
        q
      
    
    {\displaystyle q}
  -ով (տես en:Modular inverse)

1129 * 442 mod 881 = 372

Այժմ Բոբն ընտրում է w-ի 372-ից մեծ կամ հավասար ամենամեծ տարրը և հանում 372-ից։ Հետո ընտրում է հաջորդ ամենամած տարրը, որը մեծ է կամ հավասար արդյունքից մինչև արդյունքը ստացվի 
  
    
      
        0
      
    
    {\displaystyle 0}
  :

372 - 354 = 18
18 - 11 = 7
7 - 7 = 0

Մեր մասնավոր բանալուց ընտրված տարրերը համապատասխանում են հաղորդագրության 1 բիտերին։

01100001

Երկուականից փոոխակերպելով կստացվի վերջնական գաղտնազերծված «a» հաղորդագրությունը։


== Աղբյուրներ ==