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

Դիֆֆի-Հելլմանի բանալին բանալիներ փոխանակելու յուրահատուկ մեթոդ է: Այն բանալիների փոխանակման ամենավաղ գործնական օրինակներից մեկն է, որն իրականացվում է գաղտնագրության դաշտում: Դիֆֆի-Հելլմանի բանալու փոխանակման մեթոդը ենթադրում է երկու կողմ, որոնք նախապես պայմանավորված տեղեկություններ չունեն միմյանց մասին` անապահով հաղորդակցության կանալով ընդհանուր գաղտնիք սահմանելու համար: Այդ բանալին հետագայում կարող է օգտագործվել հետագա հաղորդագրությունները ծածկագրելու համար` օգտագործելով սիմետրիկ բանալիով շիֆր: Սխեման առաջին անգամ 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 = g^a mod p
   • A = 5⁶ mod 23
   • A = 15,625 mod 23
   • A = 8
3. Բոբն ընտրում է գաղտնի ամբողջ թիվ b=15, հետո Ալիսին ուղարկում է B = g^b mod p
   • B = 5¹⁵ mod 23
   • B = 30,517,578,125 mod 23
   • B = 19
4. Ալիսը հաշվում է s = B ^a mod p
   • s = 19⁶ mod 23
   • s = 47,045,881 mod 23
   • s = 2
5. Բոբը հաշվում է s = A ^b mod p
   • s = 8¹⁵ mod 23
   • s = 35,184,372,088,832 mod 23
   • s = 2
6. Հիմա Ալիսը և Բոբն ունեն ընդհանուր գաղտնիք. s = 2: Սա այն պատճառով է, որ 6*15-ը նույնն է ինչ 15*6-ը: Այսպիսով, եթե ինչ-որ մեկն իմանար այս գաղտնի ամբողջ թվերը, կարող էր նույնպես հաշվել s as follows:
   • s = 5^6*15 mod 23
   • s = 5^15*6 mod 23
   • s = 5⁹⁰ 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

Ալիսը և Բոբը ստացան միևնույն արժեքը, որովհետև (g^a)^b-ը և (g^b)^a-ը mod p հավասար են: Նշենք, որ միայն a, b-ն և g^ab = g^ba mod p են մնացել գաղտնի: Մնացած բոլոր արժեքները` – p, g, g<sup>a</sup> mod p, և g<sup>b</sup> mod p – ուղարկվում են բացահայտ: Քանի որ Ալիսը և Բոբը հաշվել են ընդհանուր գաղտնիքը, նրանք դա կարող են օգտագործել որպես ծածկագրման բանալի, որը հայտնի է միայն իրենց: Իհարկե, a-ի, b-ի և p-ի ավելի մեծ արժեքներ անհրաժեշտ կլինեն այս արինակն ավելի ապահով դարձնելու համար, քանի որ հեշտ է փորձել g<sup>ab</sup> mod 23-ի բոլոր հնարավոր արժեքները (ամենաշատը կլինեն 22 հատ): Եթե p-ն ունենա ամենաքիչը 300 թվանշան, և a-ն ու b-ն լինեն ամենաքիչը 100 նիշանոց, ապա ներկայուս հայտնի նույնիսկ լավագույն ալգորիթմները չեն կարող գտնել a-ն` g, p, g^b mod p-ի և g^a mod p-ի հայտնի լինելու պարագայում: Սա հայտնի է որպես դիսկրետ լոգարիթմի խնդիր: Նշենք նաև որ g-ն ընդհանրապես կարիք չունի մեծ լինել, այն սովորաբար պրակտիկայում 5 է կամ 2:

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

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

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

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

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

Դիագրամ

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

• Նշանակենք s = ընդհանուր գաղտնի բանալի. s = 2
• Նշանակենք g = հայտնի հիմք. g = 5
• Նշանակենք p = հայտնի (պարզ) թիվ. p = 23
• Նշանակենք a = Ալիսի գաղտնի բանալի. a = 6
• Նշանակենք A = Ալիսի հայտնի բաալի. A = g^a mod p = 8
• Նշանակենք b = Բոբի գաղտնի բանալի. b = 15
• Նշանակենք B = Բոբի հայտնի բանալի. B = g^b 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-ն ճիշտ են ընտրված: g^ab-ն ստանալու համար կողմնակի անձը պետք է լուծի Դիֆֆի-Հելլմանի խնդիրը: Դա ներկայումս բավականին բարդ է: Դիսկրետ լոգարիթմային խնդիրն էֆեկտիվ լուծող ալգորիթմը կհեշտացնի հաշվարկել a-ն կամ b-ն և լուծել Դիֆֆի-Հելլմանի խնդիրը` այս և այլ հանրային բանալիով կրիպտոհամակարգերը դարձնելով անապահով:

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