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

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

## Նկարագրությունը
Մերկլ-Հելլմանը ասիմետրիկ բանալիով կրիպտոհամակարգ է, ենթադրում է հաղորդակցություն երկու անհրաժեշտ բանալիներով՝ հանրային բանալի և մասնավոր բանալի։ Ավելին, ի տարբերություն RSA-ի, Միակողմանի հանրային բանալի է օգտագործվում գաղտնագրման, իսկ մասնավոր բանալին օգտագործվում է միայն գաղտնազերծման համար։ Այսպիսով, այն չի կիրառվում իսկությունը ստուգելու համար թվային ստորագրության կողմից։

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

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

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

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

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

:*w* = (*w*1, *w*2, ..., *w**n*)

*n* ոչ զրոյական բնական թվերից. Վերցվում է այնպիսի պատահական *q* ամբողջ թիվ, որ

: q>\sum_{i = 1}^n w_i,

և այնպիսի պատահական ամբողջ *r* թիվ, որ gcd(*r*,*q*) = 1 (այսինքն՝ *r*-ը *q*-ն փոխադարձաբար պարզ են)։

*q*-ն ընտրվում է այնպես, որ հավաստիացնի գաղտնագրի եզակիությունը։ Եթե այն փոքր է, մեկից ավելի պարզ տեքստեր կարող են գաղտնագրվել նույն արդյունքով։ *r*-ը պետք է պարզ լինի *q*-ի նկատմամբ, այլապես այն չի ունենա հակադարձ mod *q*: *r*-ի հակադարձի առկայությունը անհրաժեշտ է դեկոդավորումը հնարավոր դարձնելու համար։

Հիմա հաշվենք հաջորդականությունը
:β&nbsp;= (β1, β2, ..., β*n*)
որտեղ
:β*i*&nbsp;= *rw**i* mod *q*.
Հանրային բանալին β է, իսկ մասնավոր բանալին՝ (*w*, *q*, *r*).

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

:α = (α1, α2, ..., α*n*),

որտեղ \alpha_i-ը հաղորդագրության *i*-րդ բիտն է և \alpha_i \boldsymbol{\in}{0, 1}, հաշվենք

:c = \sum_{i = 1}^n \alpha_i \beta_i.
Կրիպտոգրամը ստացվում է *c*-ն։

### Գաղտնազերծում
Որպեսզի գաղտնազերծի *c* գաղտնագիրը՝ ստացողը պետք է գտնի հաղորդագրության α*i* բիտերը որոնք բավարարում են
: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'\equiv cs \pmod{q}.
Հետևաբար
: c' \equiv cs \equiv \sum_{i = 1}^n \alpha_i \beta_i s \pmod{q}.
Քանի որ *rs* mod q = 1 և β*i*&nbsp;= *rw**i* mod *q*, հետևում է
: \beta_i s\equiv w_i r s\equiv w_i\pmod{q}.
Այստեղից
: c' \equiv \sum_{i = 1}^n \alpha_i w_i\pmod{q}.
Բոլոր *w*i արժեքների գումարը ավելի փոյքր է, քան *q*-ն, ուստի \sum_{i = 1}^n \alpha_i w_i նույնպես [0,*q*-1] միջակայքում է։
Այսպիսով ստացողը պետք է լուծի ենթաբազմության գումարի խնդիրը
: c' = \sum_{i = 1}^n \alpha_i w_i.
Այս խնդիրը հեշտ է քանի որ *w*-ն գերաճող հաջորդականություն է։
Վերցնում ենք *w*-ի ամենամեծ տարրը, նշանակենք *w**k*. Եթե *w**k* > *c' *, ապա α*k* = 0, եթե *w**k*≤*c' *, ապա α*k* = 1. Հետո *c' *-ից հանում ենք  *w**k*×α*k*, և կրկնում ենք քայլերը մինչև α-ն հաշվելը։

## Օրինակ
Նախ և առաջ ստեղծվում է գերաճող *w* հաջորդականություն
 w = {2, 7, 11, 21, 42, 89, 180, 354}
Սա մասնավոր բանալու հիմքն է։ Այստեղից հաշվարկենք գումարը։
: \sum w = 706
Հետո ընտրենք *q* թիվ, որը մեծ է գումարից։
 `q = 881`
Նաև ընտրենք *r* թիվ, որը [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-ով (տես :en:Modular inverse)
 `1129 * 442 mod 881 = 372`
Այժմ Բոբն ընտրում է *w*-ի 372-ից մեծ կամ հավասար ամենամեծ տարրը և հանում 372-ից։ Հետո ընտրում է հաջորդ ամենամած տարրը, որը մեծ է կամ հավասար արդյունքից մինչև արդյունքը ստացվի 0:
 `372 - 354 = 18`
 `18 - 11 = 7`
 `7 - 7 = 0`
Մեր մասնավոր բանալուց ընտրված տարրերը համապատասխանում են հաղորդագրության 1 բիտերին։
 `01100001`
Երկուականից փոոխակերպելով կստացվի վերջնական գաղտնազերծված «a» հաղորդագրությունը։

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

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