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

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

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

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

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

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

# Ալիսը և Բոբը պայմանավորվում են օգտագործել նախնական թիվ՝ *<span style="color:green">p</span>*=23 և հիմքը՝ *<span style="color:green">g</span>*=5.
# Ալիսն ընտրում է գաղտնի ամբողջ թիվ. ***<span style="color:red">a</span>***=**<span style="color:red">6</span>**, և Բոբին ուղարկում է A = *<span style="color:green">g</span><sup>*'a**</sup>'' mod ''<span style="color:green">p</span>''
#* <span style="color:green">A</span> = <span style="color:green">5</span><sup>**6**</sup> mod <span style="color:green">23</span>
#* <span style="color:green">A</span> = <span style="color:red">15,625</span> mod <span style="color:green">23</span>
#* <span style="color:green">A</span> = <span style="color:green">8</span>
# Բոբն ընտրում է գաղտնի ամբողջ թիվ ***<span style="color:red">b</span>***=**15**, հետո Ալիսին ուղարկում է <span style="color:green">B</span> = ''<span style="color:green">g</span><sup>**b**</sup>'' mod ''<span style="color:green">p</span>''
#* <span style="color:green">B</span> = <span style="color:green">5</span><sup>**15**</sup> mod <span style="color:green">23</span>
#* <span style="color:green">B</span> = <span style="color:red">30,517,578,125</span> mod <span style="color:green">23</span>
#* <span style="color:green">B</span> = <span style="color:green">19</span>
# Ալիսը հաշվում է **s** = ''<span style="color:green">B</span>'' ''<sup>**a**</sup>'' mod ''<span style="color:green">p</span>''
#* **s** = <span style="color:green">19</span><sup>**6**</sup> mod <span style="color:green">23</span>
#* **s** = <span style="color:red">47,045,881</span> mod <span style="color:green">23</span>
#* **s** = **2**
# Բոբը հաշվում է **s** = ''<span style="color:green">A</span>'' ''<sup>**b**</sup>'' mod ''<span style="color:green">p</span>''
#* **s** = <span style="color:green">8</span><sup>**15**</sup> mod <span style="color:green">23</span>
#* **s** = <span style="color:red">35,184,372,088,832</span> mod <span style="color:green">23</span>
#* **s** = **2**
# Հիմա Ալիսը և Բոբն ունեն ընդհանուր գաղտնիք. **s** = **2**։ Սա այն պատճառով է, որ <span style="color:red">6</span>*<span style="color:red">15</span>-ը նույնն է ինչ <span style="color:red">15</span>*<span style="color:red">6</span>-ը։ Այսպիսով, եթե ինչ-որ մեկն իմանար այս գաղտնի ամբողջ թվերը, կարող էր նույնպես հաշվել <span style="color:red">s</span> as follows։
#* **s** = <span style="color:green">5</span><sup>**6*15**</sup> mod <span style="color:green">23</span>
#* **s** = <span style="color:green">5</span><sup>**15*6**</sup> mod <span style="color:green">23</span>
#* **s** = <span style="color:green">5</span><sup>**90**</sup> mod <span style="color:green">23</span>
#* **s** = <span style="color:red">807,793,566,946,316,088,741,610,050,849,573,099,185,363,389,551,639,556,884,765,625</span> mod <span style="color:green">23</span>
#* **s** = **2*'

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

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

# Ալիսը և Բոբը վերցում են մի ինչ-որ վերջավոր *G* ցիկլիկ խումբ և այդ խմբի միջի ինչ-որ *g* տարր։ (Սա արվում է կանոնակարգից դեռ շատ առաջ, ենթադրվում է, որ *g*-ն հայտնի է բոլոր հարձակվողներին)։
# Ալիսն ընտրում է մի պատահական բնական *a* թիվ և Բոբին ուղարկում է *ga*։
# Բոբն ընտրում է մի պատահական բնական *b* թիվ և Ալիսին ուղարկում է *gb*։
# Ալիսը հաշվում է (*gb*)*a*։
# Բոբը հաշվում է (*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:*

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

* Նշանակենք <span style="color:red">s</span> = ընդհանուր գաղտնի բանալի. <span style="color:red">s</span> = <span style="color:red">2</span>
* Նշանակենք <span style="color:green">g</span> = հայտնի հիմք. <span style="color:green">g</span> = <span style="color:green">5</span>
* Նշանակենք <span style="color:green">p</span> = հայտնի (պարզ) թիվ. <span style="color:green">p</span> = <span style="color:green">23</span>
* Նշանակենք <span style="color:red">a</span> = Ալիսի գաղտնի բանալի. <span style="color:red">a</span> = <span style="color:red">6</span>
* Նշանակենք <span style="color:green">A</span> = Ալիսի հայտնի բաալի. <span style="color:green">A</span> = <span style="color:green">g</span><sup><span style="color:red">a</span></sup> mod <span style="color:green">p</span> = <span style="color:green">8</span>
* Նշանակենք <span style="color:red">b</span> = Բոբի գաղտնի բանալի. <span style="color:red">b</span> = <span style="color:red">15</span>
* Նշանակենք <span style="color:green">B</span> = Բոբի հայտնի բանալի. <span style="color:green">B</span> = <span style="color:green">g</span><sup><span style="color:red">b</span></sup> mod <span style="color:green">p</span> = <span style="color:green">19</span>



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

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

Եթե Ալիսը և Բոբը օգտագործեն պատահական թվերի գեներատորներ, որոնց ելքերը ոչ ամբողջությամբ պատահական մեծություններ են և կարող են որոշ չափով կանխատեսվել, ապա Եվայի գործը զգալիորեն կհեշտանա։ Գաղտնի *a* և *b* ամբողջ թվերը սեսիայի ավարտիվ հետո հեռացվում են, որպեսզի ապահովվի լիարժեք գաղտնիություն։ Իր հիմնական իմաստով այս ալգորիթմը չի ապահովում կողմերի հեղինակայնությունը, որի հետևայքով կարող է որոշ թերությունների հանգեցնել։ Հաղորդակցվող կողմերի միջև գտնվող անձը կաևող է և' Ալիսի, և' Բոբի հետ բանալիներ փոխանակել և մոտենալ գաղտնի բանալու հայտնաբերմանը։
* Dieter Gollmann (2006). *Computer Security Second Edition* West Sussex, England։ John Wiley & Sons, Ltd.
* [http://www.cesg.gov.uk/publications/Documents/secenc.pdf Non-Secret Encryption Using a Finite Field]  MJ Williamson, January 21, 1974.
* [http://www.fi.muni.cz/usr/matyas/lecture/paper3.pdf Thoughts on Cheaper Non-Secret Encryption] MJ Williamson, August 10, 1976.
* [http://cryptocellar.web.cern.ch/cryptocellar/cesg/ellis.pdf The History of Non-Secret Encryption]  [[:en:James H. Ellis|JH Ellis]] 1987 (28K PDF file) ([http://www.jya.com/ellisdoc.htm HTML version] )
* [http://cr.yp.to/bib/1988/diffie.pdf The First Ten Years of Public-Key Cryptography] Whitfield Diffie, Proceedings of the IEEE, vol. 76, no. 5, May 1988, pp։ 560–577 (1.9MB PDF file)
* [[:en:Alfred Menezes|Menezes, Alfred]]; [[:en:Paul van Oorschot|van Oorschot, Paul]]; [[:en:Scott Vanstone|Vanstone, Scott]] (1997). *Handbook of Applied Cryptography* Boca Raton, Florida։ CRC Press. ISBN 0-8493-8523-7. ([http://www.cacr.math.uwaterloo.ca/hac/ Available online])
* [[:en:Simon Singh|Singh, Simon]] (1999) *:en:The Code Book: the evolution of secrecy from Mary Queen of Scots to quantum cryptography'' New York։ Doubleday ISBN 0-385-49531-5
* An Overview of Public Key Cryptography Martin E. Hellman, IEEE Communications Magazine, May 2002, pp։42–49. (123kB PDF file)

Կատեգորիա:Գաղտնագրություն