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

Մերկլ-Հելլման պարկային կրիպտոհամակարգը ամենավաղ հանրային բանալիով կրիպտոհամակարգերից է՝ ստեղծված Ռալֆ Մերկլի և Մարտին Հելլմանի կողմից 1978 թվականինMerkle, Ralph and Martin Hellman, "Hiding information and signatures in trapdoor knapsacks," Information Theory, IEEE Transactions on, vol.24, no.5, pp. 525-530, Sep 1978
URL: http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=1055927։ Չնայած իր էլեգանտ գաղափարներին և RSA-ից բավականին պարզ լինելուն, այն կոտրվել էShamir, Adi, "A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem," Information Theory, IEEE Transactions on, vol.30, no.5, pp. 699-704, Sep 1984
URL: http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=4568386։

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

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

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

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

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

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

w = (w1, w2, ..., wn)

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

 ,

և այնպիսի պատահական ամբողջ 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-րդ բիտն է և {0, 1}, հաշվենք

Կրիպտոգրամը ստացվում է c-ն։

Գաղտնազերծում
Որպեսզի գաղտնազերծի c գաղտնագիրը՝ ստացողը պետք է գտնի հաղորդագրության α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 գաղտնագիրը ստացողը հաշվում է

Հետևաբար

Քանի որ rs mod q = 1 և βi = rwi mod q, հետևում է

Այստեղից

Բոլոր wi արժեքների գումարը ավելի փոյքր է, քան q-ն, ուստի  նույնպես [0,q-1] միջակայքում է։
Այսպիսով ստացողը պետք է լուծի ենթաբազմության գումարի խնդիրը

Այս խնդիրը հեշտ է քանի որ w-ն գերաճող հաջորդականություն է։
Վերցնում ենք w-ի ամենամեծ տարրը, նշանակենք wk. Եթե wk > c' , ապա αk = 0, եթե wk≤c' , ապա αk = 1. Հետո c' -ից հանում ենք  wk×αk, և կրկնում ենք քայլերը մինչև α-ն հաշվելը։

Օրինակ
Նախ և առաջ ստեղծվում է գերաճող w հաջորդականություն
 w = {2, 7, 11, 21, 42, 89, 180, 354}
Սա մասնավոր բանալու հիմքն է։ Այստեղից հաշվարկենք գումարը։

Հետո ընտրենք q թիվ, որը մեծ է գումարից։
 q = 881
Նաև ընտրենք r թիվ, որը  միջակայքում է և պարզ է 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 </code>-ով (տես :en:Modular inverse)
 1129 * 442 mod 881 = 372
Այժմ Բոբն ընտրում է w-ի 372-ից մեծ կամ հավասար ամենամեծ տարրը և հանում 372-ից։ Հետո ընտրում է հաջորդ ամենամած տարրը, որը մեծ է կամ հավասար արդյունքից մինչև արդյունքը ստացվի :
 372 - 354 = 18
 18 - 11 = 7
 7 - 7 = 0
Մեր մասնավոր բանալուց ընտրված տարրերը համապատասխանում են հաղորդագրության 1 բիտերին։
 01100001
Երկուականից փոոխակերպելով կստացվի վերջնական գաղտնազերծված «a» հաղորդագրությունը։

 Աղբյուրներ 

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