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

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

Նկարագրությունը

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

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

Բանալու գեներացումը

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

Գաղտնագրում

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

Գաղտնազերծում

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

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

Բանալու գեներացում

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

w = (w₁, w₂, ..., w_n)

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

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

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

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

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

β = (β₁, β₂, ..., β_n)

որտեղ

β_i = rw_i mod q.

Հանրային բանալին β է, իսկ մասնավոր բանալին` (w, q, r).

Գաղտնագրում

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

α = (α₁, α₂, ..., α_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 = 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 ⁻¹ 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» հաղորդագրությունը: