დაშიფრვა საჯარო გასაღებით და RSA (Public Key Encryption and RSA)
===

კურსის პირველ ნახევარში გავლილ ყველა კონსრტუქციაში უსაფრთხო კომუნიკაციის ორი მხარე იყენებდა საიდუმლო გასაღებს. დაშვება გვქონდა, რომ გასაღები წინასწარ ჰქონდათ გაცვლილი. გასაღების გაცვლა ხშირად რთულია ან შეუძლებელია. მაგალითად, Google-ის საძიებო სისტემის მომხმარებლებს უნდათ, რომ მათი გაგზავნილი მოთხოვნები (search query) და სერვერის გამოგზავნილი პასუხი (search results) იყოს დაშიფრული. Google-ს არ აქვს საშუალება, რომ ყველა მომხარებელთან პირადად გაცვალოს გასაღები. ამის მაგივრად, Google-ს აქვს **საჯარო გასაღები (public key)**, რომლის გამოყენებაც შეუძლია ნებისმიერ მომხმარებელს საკუთარი შეტყობინების დასაშიფრად. ამ გასაღებით დაშიფრული შეტყობინებების გახსნა შეუძლია მხოლოდ Google-ს, რომელსაც აქვს შესაბამისი **საიდუმლო გასაღები (secret key)**.

ფორმალურად, საჯარო გასაღებით დაშიფრვისთვის საჭიროა სამი ალგორითმი: $Gen()$, რომელიც აბრუნებს საჯარო და საიდუმლო გასაღების წყვილ $(pk,sk)$-ს, დაშიფრვის ალგორითმი $E(pk, \cdot)$ და განშიფრვის ალგორითმი $D(sk, \cdot)$ შემდეგი თვისებით: ნებისმიერი შეტყობინება $m$-ისთვის, სრულდება $D(sk, E(pk, m)) = m$ (ანუ განშიფრვა სწორად მუშაობს). მაგალითად, სერვერს შეუძლია, დააგენერიროს გასაღებების წყვილი და გაასაჯაროვოს მიღებული $pk$. შემდეგ მომხმარებელშ შეუძლია, დაშიფროს საკუთარი შეტყოფინება $m$ ალგორითმი $E$-სა და $pk$-ს გამოყენებით, და გაუგზავნოს სერვერს $c = E(pk, m)$. სერვერს შეუძლია შეტყობინების განშიფრვა $D$-სა და $sk$-ს გამოყენებით. მეთვალთვალე, რომელიც მათ შორის კომუნიკაციას აკვირდება, ხედავს საჯარო გასაღებ $pk$-სა და დაშიფრულ შეტყობინება $c$-ს. დაცული ალგორითმის გამოყენების შემთხვევაში, მას პრაქტიკულად არ აქვს შანსი, რომ მიიღოს რაიმე ინფორმაცია დაშიფრული შეტყობინების შესახებ.

საჯარო გასაღებით დაშიფრვისთვის ხშირად გამოიყენება RSA ფუნქცია. ავირჩიოთ მოდული $N = pq$, სადაც $p$ და $q$ დიდი მარტივი რიცხვებია (დაახლოებით, 1024-ბიტიანი). გავიხსენოთ, რომ $\mathbb{Z}_N = \{0,1,\dots,N-1\}$, $\mathbb{Z}^\times_N = \{ a \in \mathbb{Z}_N : \gcd(a,N) = 1 \}$, ხოლო $|\mathbb{Z}^\times_N| = \varphi(N) = \varphi(pq) = (p-1)(q-1)$. ოილერის თეორემით, $x^{\phi(N)} = 1 \mod N$ ყველა $x$-ისთვის სიმრავლიდან $\mathbb{Z}^\times_N$. RSA-ის გენერაციის ალგორითმი პოულობს ისეთ $e$-სა და $d$-ს რომ $ed = 1 \mod \varphi(n)$. საჯარო გასაღები არის $(N, e)$, ხოლო საიდუმლო გასაღები არის $(N, d)$. დაშიფრვა $(N, e)$-თი მუშაობს ასე: $RSA(x) =x^e$. ამ ფუნქციის შესაბრუნებლად, საიდუმლო გასაღების მცოდნეს შეუძლია, $RSA(x)$ აიყვანოს ხარისხში $d$ და მიიღოს $RSA(x)^d = x^{ed} = x$, სადაც ბოლო ნაბიჯი იყენებს ოილერის თეორემასა და იმ ფაქტს, რომ $ed = k\varphi(N) + 1$ რაღაც რიცხვი $k$-სთვის. RSA-ის დაშვებაა, რომ $N$, $e$ და $x^e \bmod N$-iს ცოდნით, რთულია გამოთვალო $x$. თავად ეს დაშვება ეფუძნება რწმენას, რომ $N = pq$-ს ფაქტორიზაცია რთული ამოცანაა. <span style="color:orange">აჩვენეთ, რომ $p$-სა და $q$-ს ცოდნის შემთხვევაში, შეგვიძლია გამოვთვალოთ $e$-ს შებრუნებული $d$.</span>