ჯგუფები და დიფი-ჰელმანის პროტოკოლი (Groups & Diffie-Hellman Key Exchange) === ჯგუფთა თეორია შეისწავლის **სიმეტრიას**. ობიექტის სიმეტრიაში ვგულისმობთ იმას, რომ ის უცვლელი რჩება გარკვეული გარდაქმნის შემდეგ: მაგალითად, წრეწირი არ იცვლება ცენტრის გარშემო მოტრიალების შედეგად, საათის ისარი უბრუნდება თავის პოზიციას 12 საათის გავლის შემდეგ, ჯამი 1 + 2 + 3 არ იცვლება შესაკრებების გადანაცვლებით და ა.შ. მსგავსი სიმეტრია შეიძლება გააჩნდეს განსხვავებულ ობიექტებს, ჯგუფთა თეორია კი შეისწავლის სიმეტრიას აბსტრაქტულად, კონტექსტისგან დამოუკიდებლად. ფორმალურად, ჯგუფი $(G, \circ)$ განისაზღვრება როგორც ობიექტების სიმრავლე $G$ და ოპერაცია $\circ$, რომლებიც აკმაყოფილებენ *ჯგუფთა აქსიომებს*: 0) ჯგუფი $G$ *ჩაკეტილია* ოპერაცია $\circ$-ის მიმართ, ანუ თუ $a,b$ ჯგუფის ელემენტებია, მაშინ $a \circ b$ ასევე ჯგუფის ელემენტია. 1) ოპერაცია $\circ$ *ასოციურია*, ანუ $(a \circ b) \circ c = a \circ (b \circ c)$ სრულდება ნებისმიერი სამეული $a,b,c$-სთვის. 2) ჯგუფს გააჩნია *ნეიტრალური ელემენტი,* ანუ $e$ ისეთი რომ $a \circ e = e \circ a = a$ ნებისმიერი ელემენტი $a$-სთვის. 3) ჯგუფის ყველა ელემენტს გააჩნია *შებრულებული*, ანუ ნებისმიერი $a$-სთვის გვაქვს $a^{-1}$ ისეთი რომ $a \circ a^{-1} = a^{-1} \circ a = e$. **მაგალითი 1.** ავიღოთ მთელი რიცხვების სიმრავლე $\mathbb{Z}$ და ოპერაცია მიმატება $+$. შევამოწმოთ, რომ ოთხივე პირობა სრულდება: 0) ორი მთელი რიცხვის ჯამი ასევე მთელი რიცხვია, 1) მთელი რიცვხების მიმატება ასოციურია, 2) მიმატების მიმართ ნეიტრალური ელემენტი არის 0, 3) ნებისმიერი მთელი რიცხვი $a$-ს შებრუნებული არის $-a$. **კონტრმაგალითი 2.** ავიღოთ ნატურალური რიცხვების სიმრავლე $\mathbb{N} = \{0,1,2,...\}$ და ოპერაცია მიმატება $+$. <span style="color:orange">რომელი პირობა არ სრულდება $(\mathbb{N},+)$-ისთვის?</span> **კონტრმაგალითი 3.** ავიღოთ მთელი რიცხვების სიმრავლე $\mathbb{Z}$ და ოპერაცია გამრავლება $\times$. <span style="color:orange">რომელი პირობა არ სრულდება $(\mathbb{Z},\times)$-ისთვის?</span> ჩვენს კურსში ძირითადად განვიხილავთ სასრულ, კომუტატიურ ჯგუფებს, ანუ ჯგუფებს სადაც სრულდება $a \circ b = b \circ a$. **მაგალითი 4.** განვიხილოთ ტოლგვერდა ექვსკუთხედი და მოტრიალებები 0, 60, 120, 180, 240 და 300 გრადუსით საათის ისრის მიმართულებით: $\{R_{0}, R_{60}, R_{120}, R_{180}, R_{240}, R_{300}\}$. განვსაზღვროთ ოპერაცია $\circ$ როგორც კომპოზიცია, ანუ $R_{180} \circ R_{300}$ აღნიშნავს ჯერ 180 და შემდეგ 300 გრადუსით მოტრიალებას. დააკვირდით, რომ $R_{180} \circ R_{300} = R_{120}$. დავარქვათ ამ ჯგუფს $H_6$. <span style="color:orange">დარწმუნდით, რომ $H_6$ აკმაყოფილებს ჯგუფთა აქსიომებს.</span> ![](https://i.imgur.com/kjJMNcg.png) **მაგალითი 5.** ავიღოთ სიმრავლე $\mathbb{Z}_6 = \{0,1,2,3,4,5\}$ და განვსაზღვროთ ოპერაცია როგორც შეკრება მოდულით $6$, მაგალითად $3 + 5 = 2 \bmod 6$. დავარქვათ ამ ჯგუფს $\mathbb{Z}_6^+$. <span style="color:orange">დარწმუნდით, რომ $\mathbb{Z}_6^+$ აკმაყოფილებს ჯგუფთა აქსიომებს.</span> **მაგალითი 6.** ავიღოთ სიმრავლე $\mathbb{Z}_{18} = \{1,5,7,11,13,17\}$ და განვსაზღვროთ ოპერაცია როგორც გამრავლება მოდულით $18$, მაგალითად $17 \times 11 = 7 \bmod 18$. დავარქვათ ამ ჯგუფს $\mathbb{Z}_{18}^{\times}$. <span style="color:orange">დარწმუნდით, რომ $\mathbb{Z}_{18}^{\times}$ აკმაყოფილებს ჯგუფთა აქსიომებს.</span> მე-4, მე-5 და მე-6 მაგალითში აღწერილია ერთი და იგივე ჯგუფი - განსხვავებულია მხოლოდ ელემენტების სახელები. შედარებით მარტივია იმის დანახვა, რომ $H_6$ და $\mathbb{Z}_{6}^{+}$ ერთი და იგივე ჯგუფია - შევუსაბამოთ ერთმანეთს ელემენტები $R_{60i} \in H_6$ და $i \in \mathbb{Z}_{6}^{+}$. იმის სანახავად, რომ $\mathbb{Z}_{18}^{\times}$-იც იგივე ჯგუფია, დავაკვირდეთ, რომ $$ 1 = 5^0 \bmod 18 \\ 5 = 5^1 \bmod 18 \\ 7 = 5^2 \bmod 18 \\ 17 = 5^3 \bmod 18 \\ 13 = 5^4 \bmod 18 \\ 11 = 5^5 \bmod 18 $$ და შევუსაბამოთ $i \in \mathbb{Z}_{6}^{+}$ და $5^{i} \in \mathbb{Z}_{18}^{\times}$. ბოლო მაგალითიდან ჩანს, რომ $\mathbb{Z}_{18}^{\times}$-ის ყველა ელემენტი მიიღება $5$-იანის და ჯგუფის ოპერაციის გამოყენებით (ამ შემთხვევაში, გამრავლებით მოდულით $18$). იგივე ხდება სხვა განხილულ: ${H}_{6}$-ის ყველა ელემენტი მიიღება $R_{60}$-ითა და კომპოზიციით, $\mathbb{Z}_{6}^{+}$ კი მიიღება $1$-ითა და მიმატებით მოდულით $6$. ისეთ ელემენტს, რომელიც საკმარისია მთელი ჯგუფის მისაღებად ეწოდება *გენერატორი*, ხოლო ჯგუფებს, რომლებსაც აქვთ ერთი გენერატორი ეწოდებათ *ციკლური*. აღსანიშნავია, რომ ჯგუფს შეიძლება ჰქონდეს რამდენიმე გენერატორი. მაგალითად, $H_6$-ის გენერატორებია $R_{60}$ და $R_{300}$. ვიზუალურად, $R_{300}$ არის $60$ გრადუსით მოტრიალება საათის ისრის საწინააღმდეგო მიმართულებით, ამიტომაც ინტუიციურია, რომ მისი "ხარისხები" იგივე ელემენტებს მოგვცემენ, რაც $R_{60}$-ის "ხარისხები", ოღონდ შებრუნებული მიმდევრობით. <span style="color:orange">რა იქნება $\mathbb{Z}_{6}^{+}$-ისა და $\mathbb{Z}_{18}^{\times}$-ის გენერატორები? სულ რამდენი გენერატორი აქვს ამ ჯგუფს?</span> განხილულ ჯგუფს აბსტრაქტულად ეწოდება *6-ელემენტიანი ციკლური ჯგუფი*, იგივე $C_6 = \{g^0, g^1, \dots, g^5\}$ ოპერაციით $g^i \cdot g^j = g^{i + j \bmod 6}$. <span style="color:orange">რა იქნება ამ ჯგუფში $g^3$-ის შებრუნებული, და ზოგადად, როგორ ვიპოვოთ $g^i$-ს შებრუნებული?</span> $H_6$ | $\mathbb{Z}_{6}^{+}$ | $\mathbb{Z}_{18}^{\times}$ | :-------------------------:|:-------------------------:|:-----:| ![](https://i.imgur.com/vUtViep.jpg) | ![](https://i.imgur.com/oFh8nY4.jpg) | ![](https://i.imgur.com/awGqiow.jpg) ახლა ვნახოთ ჯგუფების კრიპტოგრაფიული გამოყენება. დავუშვათ, ელისსა და ბობს სსურთ საიდუმლო გასაღების გაცვლა საჯარო არხის გამოყენებით. ამ არხს აკვირდება ბოროტმოქმედი ივი, მაგრამ ის ვერ აგზავნის შეტყობინებებს, მხოლოდ პასიურად უყურებს კომუნიკაციას. ელისსა და ბობს შეუძლიათ გამოიყენონ **Diffie-Hellman-ის პროტოკოლი**: 1) შეთანხმდნენ დიდ ციკლურ ჯგუფ $C_N$-ზე და მის ერთ-ერთ გენერატორ $g$-ზე. (შეგიძლიათ წარმოიდგინოთ, რომ $N$ შედგება 256 ბიტისგან). 2) ელისი საკუთარ კომპიუტერში აგენერირებს შემთხვევითად ირჩევს რიცხვ $a$-ს სიმრავლიდან $\{0, \dots, N-1\}$, ითვლის $g^a$-ს და უგზავნის ბობს. (დააკვირდით, რომ $a$ ახლა მხოლოდ ელისმა იცის). 3) ბობი საკუთარ კომპიუტერში აგენერირებს შემთხვევითად ირჩევს რიცხვ $b$-ს სიმრავლიდან $\{0, \dots, N-1\}$, ითვლის $g^b$-ს და უგზავნის ელისს. 4) ელისი იღებს ბობის გამოგზავნილ $g^{b}$-ს, აჰყავს $a$-ურ ხარისხში და იღებს <span style="color:green">$g^{ab}$-ს</span>. 5) ბობი იღებს ელისის გამოგზავნილ $g^{a}$-ს, აჰყავს $b$-ურ ხარისხში და ასევე იღებს <span style="color:green">$g^{ab}$-ს</span>. ელემენტი <span style="color:green">$g^{ab}$</span> არის ელისის და ბობის საზიარო საიდუმლო გასაღები. ამ დროს ივი ხედავს $N, g, g^a, g^b$-ს და იცის პროტოკოლი, ამიტომაც მას სურს, გამოთვალოს $g^{ab}$. ამ ამოცანას ეწოდება Computational Diffie-Hellman Problem (CDH) და მიიჩნევა ერთ-ერთ რთულ ამოცანად, ანუ გვჯერა, რომ შეუძლებელია ამ ამოცანის სწრაფად (ანუ $\log(N)$-ის მიმართ პოლინომიურ დროში) ამოხსნა. CDH-ის სირთულე კი ეყრდნობა **დისკრეტული ლოგარითმის** გამოთვლის სირთულეს. დისკრეტული ლოგარითმის გამოთვლა გულისხმობს ნებისმიერი $N, g, h$-ისთვის, სადაც $g$ არის $C_N$-ის გენერატორი, ხოლო $h$ არის $C_N$-ის ერთ-ერთი ელემენტი, ისეთი ხარისხი $a$-ს პოვნას, რომ $g^a = h$. <span style="color:orange">როგორ შეგვიძლია გამოვიყენოთ დისკრეტული ლოგარითმი CDH-ის ამოსახსნელად?</span> შეიძლება გაგჩენოდათ კითხვა, რამდენად საჭირო იყო ამ პროტოკოლის განმარტებაში ჯგუფის გამოყენება, როცა შეგვეძლო მარტივი (მოდულარული) არითმეტიკით აღგვეწერა? აბსტრაქტული მიდგომის ერთ-ერთი ძალაა, რომ მკაფიოდ ჩანს, რა პირობებია რეალურად საჭირო პროტოკოლის მუშაობისთვის და რა არის მხოლოდ ზედაპირული დეტალები. აქ ჩანს, რომ Diffie-Hellman-ს სჭირდება ჯგუფი, რომლის ელემენტების აღწერაც შეგვიძლია კომპიუტერში, რომელშიც მუშაობს სწრაფი ახარისხება (ელისმა და ბობმა უნდა შეძლონ $g^a$-სა და $g^b$-ს სწრაფად გამოთვლა) და რთულია დისკრეტული ლოგარითმის ამოღება. მაგალითად, $\mathbb{Z}_{N}^{+}$ აკმაყოფილებს პირველ ორ პირობას, მაგრამ არა მესამეს. სამაგიეროდ, შეგვიძლია ვიპოვოთ ისეთი დიდი რიცხვი $M$, რომ $\mathbb{Z}_{M}^{\times}$ არის $N$-ელემენტიანი ციკლური ჯგუფი, რომელიც აკმაყოფილებს სამივე პირობას. ამაზე უკეთესი არჩევანია [ელიპტური წირების](https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman) გამოყენებით განსაზღვრული ჯგუფები, რომლებიც გამოიყენება, მაგალითად, [OpenSSL](https://wiki.openssl.org/index.php/Elliptic_Curve_Diffie_Hellman#:~:text=ECDH%20is%20used%20for%20the,QB%3DdBG.)-ში და მესენჯერ [სიგნალში](https://en.wikipedia.org/wiki/Signal_Protocol).