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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

Նկարագրությունը[խմբագրել]

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

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

Բանալու գեներացումը[խմբագրել]

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

Գաղտնագրում[խմբագրել]

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

Գաղտնազերծում[խմբագրել]

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

Մաթեմատիկական մեթոդ[խմբագրել]

Բանալու գեներացում[խմբագրել]

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

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

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

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

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

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

Հիմա հաշվենք հաջորդականությունը

β = (β1, β2, ..., βn)

որտեղ

βi = rwi 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 = rwi 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}.

Բոլոր wi արժեքների գումարը ավելի փոյքր է, քան q-ն, ուստի \sum_{i = 1}^n \alpha_i w_i նույնպես [0,q-1] միջակայքում է: Այսպիսով ստացողը պետք է լուծի ենթաբազմության գումարի խնդիրը

c' = \sum_{i = 1}^n \alpha_i w_i.

Այս խնդիրը հեշտ է քանի որ w-ն գերաճող հաջորդականություն է: Վերցնում ենք w-ի ամենամեծ տարրը, նշանակենք wk. Եթե wk > c' , ապա αk = 0, եթե wkc' , ապա αk = 1. Հետո c' -ից հանում ենք wk×α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» հաղորդագրությունը:

Աղբյուրներ[խմբագրել]

  1. 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
  2. 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

Կաղապար:Crypto navbox