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

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

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

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

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

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

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

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

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

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

Diffie–Hellman key exchange

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

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

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

\leftarrow 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 ամբողջ թվերը սեսիայի ավարտիվ հետո հեռացվում են, որպեսզի ապահովվի լիարժեք գաղտնիություն: Իր հիմնական իմաստով այս ալգորիթմը չի ապահովում կողմերի հեղինակայնությունը, որի հետևայքով կարող է որոշ թերությունների հանգեցնել: Հաղորդակցվող կողմերի միջև գտնվող անձը կաևող է և' Ալիսի, և' Բոբի հետ բանալիներ փոխանակել և մոտենալ գաղտնի բանալու հայտնաբերմանը:

Կաղապար:Crypto navbox