Դիֆֆի-Հելլմանի բանալու փոխանակում

Դիֆֆի-Հելլմանի բանալին բանալիներ փոխանակելու յուրահատուկ մեթոդ է։ Այն բանալիների փոխանակման ամենավաղ գործնական օրինակներից մեկն է, որն իրականացվում է գաղտնագրության դաշտում։ Դիֆֆի-Հելլմանի բանալու փոխանակման մեթոդը ենթադրում է երկու կողմ, որոնք նախապես պայմանավորված տեղեկություններ չունեն միմյանց մասին՝ անապահով հաղորդակցության կանալով ընդհանուր գաղտնիք սահմանելու համար։ Այդ բանալին հետագայում կարող է օգտագործվել հետագա հաղորդագրությունները ծածկագրելու համար՝ օգտագործելով սիմետրիկ բանալիով շիֆր։ Սխեման առաջին անգամ 1976 թվականին հրատարակել են Ուիթֆիլդ Դիֆֆին և Մարթին Հելլմանը, չնայած հետագայում պարզվեց, որ այն մի քանի տարի առաջ հորինվել է GCHQ-ի շրջանակներում, բրիտանացիների ազդանշանների հետախուզական գործակալությունում Մալքոլմ Ուիլյամսոնի կողմից։ 2002 թվականին Հելլմանն առաջարկեց հանրահաշիվն անվանել Դիֆֆիի-Հելմանի-Մերքլի բանալու փոխանակում՝ ի ճանաչումն Ռալֆ Մերքլի լումայի հանրային բանալիով գաղտնագրի գյուտի (Հելլման 2002)։

Կանոնակարգի պատմություն խմբագրել

Դիֆֆի-Հելլմանի բանալու համաձայնեցումը հնարվել է 1976 թվականին Ուիթֆիլդ Դիֆֆիի և Մարթին Հելլմանի միջև եղած աշխատակցման հետևանքով և առաջին գործնական մեթոդն էր հիմնելու ընդհանուր գաղտնիք չպաշտպանված հաղորդակցական կանալների համար։ Ռալֆ Մերքլի աշխատանքը հանրային բանալու բաշխման վրա մեծ ազդեցություն ուներ։ Ջոն Գիլլն առաջարկեց ընդհատ լոգարիթմի դիմման պրոբլեմը։ Այն մի քանի տարի առաջ Միացյալ Թագավորությունում հայտնագործել է Մալքոլմ Ուիլամսոնը GCHQ-ից, բայց GCHQ-ն նախընտրեց հրապարակավ չհայտնել դա մինչև 1997 թվականը, մինչ այդ այն չէր ազդում ակադեմիայի ուսումնասիրությունների վրա։ Հետո այս մեթոդին հաջորդեց RSA-ն՝ հանրային բանալու մեկ այլ իրագործում՝ օգտագործելով ասիմետրիկ ալգորիթմներ։

2002 թվականին Մարթին Հելլմանը գրել է.

«Համակարգը հայտնի է Դիֆֆի-Հելլմանի բանալու փոխանակում անվամբ։ Երբ այդ համակարգն առաջին անգամ թերթում իմ և Դիֆֆի կողմից տպագրվեց, այն հանրային բանալու բաժանման համակարգ էր, մի հասկացություն` զարգացրած Մերքլի կողմից և, հետևաբար, պետք է անվանվեր Դիֆֆիի-Հելլմանի-Մերքլի բանալու փոխանակում, եթե անհրաժեշտ է անունները դրա հետ մեկտեղ կապակցել։ Կարծում եմ, այս փոքրիկ քարոզը կօգնի ճանաչելու Մերքլի լուման բանալու գաղտնագրի գյուտի մեջ»։

U.S. Patent 4,200,770-ը այժմ Դիֆֆիին, Հելլմանին և Մերքլին ճանաչում է որպես ալգորիթմի գյուտարարների։

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

Ալգորիթմը սահմանում է ընդհանուր գաղտնիք, որը կարող է օգտագործվել գաղտնի հաղորդակցություններում, որոնց միջոցով տվյալներ են փոխանակում հանրային ցանցում։ Ներկայացնենք բացատրություն, որը պարունակում է կոդավորման մաթեմատիկան։

Ահա և կանոնակարգի մի օրինակ։ Ստորև բերված ընդգծված թվերը գաղտնի են, մյուսները՝ ոչ.

Alice
Bob
Secret Public Calculates Sends
Calculates
Public
Secret
a
p, g
p, g 

b
a
p, g, A
ga mod p = A A 
p, g
b
a
p, g, A

  B
gb mod p = B
p, g, A, B
b
a, s p, g, A, B
Ba mod p = s

Ab mod p = s
p, g, A, B
b, s
  1. Ալիսը և Բոբը պայմանավորվում են օգտագործել նախնական թիվ՝ p=23 և հիմքը՝ g=5.
  2. Ալիսն ընտրում է գաղտնի ամբողջ թիվ. a=6, և Բոբին ուղարկում է A = ga mod p
    • A = 56 mod 23
    • A = 15,625 mod 23
    • A = 8
  3. Բոբն ընտրում է գաղտնի ամբողջ թիվ b=15, հետո Ալիսին ուղարկում է B = gb mod p
    • B = 515 mod 23
    • B = 30,517,578,125 mod 23
    • B = 19
  4. Ալիսը հաշվում է s = B a mod p
    • s = 196 mod 23
    • s = 47,045,881 mod 23
    • s = 2
  5. Բոբը հաշվում է s = A b mod p
    • s = 815 mod 23
    • s = 35,184,372,088,832 mod 23
    • s = 2
  6. Հիմա Ալիսը և Բոբն ունեն ընդհանուր գաղտնիք. s = 2։ Սա այն պատճառով է, որ 6*15-ը նույնն է ինչ 15*6-ը։ Այսպիսով, եթե ինչ-որ մեկն իմանար այս գաղտնի ամբողջ թվերը, կարող էր նույնպես հաշվել s as follows։
    • s = 56*15 mod 23
    • s = 515*6 mod 23
    • s = 590 mod 23
    • s = 807,793,566,946,316,088,741,610,050,849,573,099,185,363,389,551,639,556,884,765,625 mod 23
    • s = 2

Ալիսը և Բոբը ստացան միևնույն արժեքը, որովհետև (ga)b-ը և (gb)a-ը mod p հավասար են։ Նշենք, որ միայն a, b-ն և gab = gba mod p են մնացել գաղտնի։ Մնացած բոլոր արժեքները՝ – p, g, ga mod p, և gb mod p – ուղարկվում են բացահայտ։ Քանի որ Ալիսը և Բոբը հաշվել են ընդհանուր գաղտնիքը, նրանք դա կարող են օգտագործել որպես ծածկագրման բանալի, որը հայտնի է միայն իրենց։ Իհարկե, a-ի, b-ի և p-ի ավելի մեծ արժեքներ անհրաժեշտ կլինեն այս արինակն ավելի ապահով դարձնելու համար, քանի որ հեշտ է փորձել gab mod 23-ի բոլոր հնարավոր արժեքները (ամենաշատը կլինեն 22 հատ)։ Եթե p-ն ունենա ամենաքիչը 300 թվանշան, և a-ն ու b-ն լինեն ամենաքիչը 100 նիշանոց, ապա ներկայուս հայտնի նույնիսկ լավագույն ալգորիթմները չեն կարող գտնել a-ն՝ g, p, gb mod p-ի և ga mod p-ի հայտնի լինելու պարագայում։ Սա հայտնի է որպես դիսկրետ լոգարիթմի խնդիր։ Նշենք նաև որ g-ն ընդհանրապես կարիք չունի մեծ լինել, այն սովորաբար պրակտիկայում 5 է կամ 2։

Հիմա տանք կանոնակարգի ավելի ընդհանուր նկարագրությունը.

  1. Ալիսը և Բոբը վերցում են մի ինչ-որ վերջավոր G ցիկլիկ խումբ և այդ խմբի միջի ինչ-որ g տարր։ (Սա արվում է կանոնակարգից դեռ շատ առաջ, ենթադրվում է, որ g-ն հայտնի է բոլոր հարձակվողներին)։
  2. Ալիսն ընտրում է մի պատահական բնական a թիվ և Բոբին ուղարկում է ga։
  3. Բոբն ընտրում է մի պատահական բնական b թիվ և Ալիսին ուղարկում է gb։
  4. Ալիսը հաշվում է (gb)a։
  5. Բոբը հաշվում է (ga)b։

Այժմ թե' Ալիսին, թե' Բոբին պատկանող gab խմբային տարրը կարող է ծառայել որպես ընդհանուր գաղտնի բանալի։ Հանրահաշվից մեզ հայտնի է, որ (gb)a-ը և (ga)b-ը իրար հավասար են։

m հաղորդագրությունը, որը ուղարկվել է որպես mgab, դեկոդավորելու համար Բոբը (կամ Ալիսը) պետք է սկզբից հաշվի (gab)-1, ինչպես հետևյալն է. Բոբը գիտի |G|, b, և ga թվերը։ G-ի բոլոր x-երի համար Բոբը հաշվում է x|G| = 1։ Հետո Բոբը հաշվում է (ga)|G|-b = ga(|G|-b) = ga|G|-ab = ga|G|g-ab = (g|G|)ag-ab=1ag-ab=g-ab=(gab)-1:

երբ Ալիսը Բոբին է ուղարկում գաղտնագրված հաղորդագրությունը՝ mgab, Բոբը պատասխանում է (gab)-1 և վերականգնում mgab(gab)-1 = m(1) = m:

Դիագրամ խմբագրել

Ահա մի աղյուսակ, որը կօգնի պարզեցնել ով ինչ գիտի։ (Եվան կողմնակի անձ է և տեսնում է, թե ինչ է փոխանակվել Ալիսի և Բոբի միջև, բայց նա չի վերափոխում նրանց հաղորդակցության պարունակությունը)։

  • Նշանակենք s = ընդհանուր գաղտնի բանալի. s = 2
  • Նշանակենք g = հայտնի հիմք. g = 5
  • Նշանակենք p = հայտնի (պարզ) թիվ. p = 23
  • Նշանակենք a = Ալիսի գաղտնի բանալի. a = 6
  • Նշանակենք A = Ալիսի հայտնի բաալի. A = ga mod p = 8
  • Նշանակենք b = Բոբի գաղտնի բանալի. b = 15
  • Նշանակենք B = Բոբի հայտնի բանալի. B = gb mod p = 19
Alice
knows doesn't know
p = 23 b = ?
base g = 5
a = 6
A = 56 mod 23 = 8
B = 5b mod 23 = 19
s = 196 mod 23 = 2
s = 8b mod 23 = 2
s = 196 mod 23 = 8b mod 23
s = 2
Bob
knows doesn't know
p = 23 a = ?
base g = 5
b = 15
B = 515 mod 23 = 19
A = 5a mod 23 = 8
s = 815 mod 23 = 2
s = 19a mod 23 = 2
s = 815 mod 23 = 19a mod 23
s = 2
Eve
knows doesn't know
p = 23 a = ?
base g = 5 b = ?
s = ?
A = 5a mod 23 = 8
B = 5b mod 23 = 19
s = 19a mod 23
s = 8b mod 23
s = 19a mod 23 = 8b mod 23

Որպես կանոն Ալիսի համար պետք է որ դժվար լինի վերլուծել Բոբի մասնավոր բանալին կամ հակառակը։ Եթե Ալիսի համար դժվար չէ վերլուծել Բոբի մասնավոր բանալին, Եվան կարող է պարզապես փոխարինել իր սեփական մասնավոր/հայտնի բանալիների զույգը, Բոբի հայտնի բանալին օգտագործել իր մասնավոր բանալու մեջ, ստանալ կեղծ ընդհանուր գաղտնի բանալի և ստանալ Բոբի մասնավոր գաղտնի բանալին։

Անվտանգություն խմբագրել

Կանոնակարգն ապահով է համարվում այն դեպքում, եթե G-ն և g-ն ճիշտ են ընտրված։ gab-ն ստանալու համար կողմնակի անձը պետք է լուծի Դիֆֆի-Հելլմանի խնդիրը։ Դա ներկայումս բավականին բարդ է։ Դիսկրետ լոգարիթմային խնդիրն էֆեկտիվ լուծող ալգորիթմը կհեշտացնի հաշվարկել a-ն կամ b-ն և լուծել Դիֆֆի-Հելլմանի խնդիրը՝ այս և այլ հանրային բանալիով կրիպտոհամակարգերը դարձնելով անապահով։

Եթե Ալիսը և Բոբը օգտագործեն պատահական թվերի գեներատորներ, որոնց ելքերը ոչ ամբողջությամբ պատահական մեծություններ են և կարող են որոշ չափով կանխատեսվել, ապա Եվայի գործը զգալիորեն կհեշտանա։ Գաղտնի a և b ամբողջ թվերը սեսիայի ավարտիվ հետո հեռացվում են, որպեսզի ապահովվի լիարժեք գաղտնիություն։ Իր հիմնական իմաստով այս ալգորիթմը չի ապահովում կողմերի հեղինակայնությունը, որի հետևայքով կարող է որոշ թերությունների հանգեցնել։ Հաղորդակցվող կողմերի միջև գտնվող անձը կաևող է և' Ալիսի, և' Բոբի հետ բանալիներ փոխանակել և մոտենալ գաղտնի բանալու հայտնաբերմանը։