ლექცია 22 Number theory, RSA encryption

1)გაარჩიეთ RSA ალგორითი 303 გვერდზე და ახსენით რა
განაპირობებს საიდუმლო გასაღების საიდუმლოებას?
RSA ალგორითმი შედგება 4 ეტაპისგან:

1. ვაგენერირებთ ორ დიდ მარტივ რიცხვს p და q.
2. შემდეგ ამ ორ რიცხვს ვამრავლებთ და ვარქმევთ n-ს; n=pq;
3. ვარჩევთ ისეთ მთელ რიცხვს e-ს რომელიც ურთიერთმარტივია φ(n)-თან, შესაბამისად gcd(e,φ(n))=1; ეილერის ფუნქციის თანახმად φ(n)=φ(pq)=φ(p)*φ(q), რადგანაც p და q მარტივი რიცხვებია, შესაბამისად φ(p)=(p-1), იგივეა q-სთვისაც და შესაბამისად φ(n)=(p-1)(q-1) - აქ გავეცით პასუხი მეორე კითხვას; შესაბამისად gcd(e,(p-1)(q-1))=1; შემდეგ ჩვენ ვარქმევთ e - სა და n - ის წყვილს public key-ს, რომლის მფლობელიც შეიძლება იყოს ნებისმიერი ადამიანი.
4. ახლა ვაგენერირებთ ისეთ მთელ რიცხვ d - ს, რომ de = 1 mod(φ(n)); მთელი catch ისაა, რომ de შეიძლება წარმოვადგინოთ, როგორც φ(n)*t+1 სადაც t რაღაც მთელი რიცხვია.

დაშიფრვა:

                ჩვენ ვიღებთ ჩვენ მესიჯს m - ს. m* ჩვენი დაშიფრული მესიჯია და გამოითვლება შემდეგნაირად:

      m*=m^e mod(n);

გაშიფრვა:

რაც შეეხება გაშიფრვას, 

m*^d=m mod(n);

3)გაარჩიეთ RSA ალგორითი 303 გვერდზე და დაასაბუთეთ, რომ 

დეკოდირებული მესიჯი იქნება ზუსტად თავდაპირველი m 

მესიჯი. 

დამტკიცება:ყველაფერს ვწერთ mod(n) - ისთვის;

m*=m^e -> m*^d=m^de -> m^de=m^(φ(n)t+1)-> m^de=m^φ(n)t * m
დავხედოთ ეილერის ფუნქციას.

a^φ(n) = 1 mod (n).

ეს ტოლობა მართებულია ნებისმიერი n - ისთვის. ასევე ცნობილია ის ფაქტიც, რომ ეილერის ფუნქციის
აქედან გამომდინარე (m^φ(n))^t = 1^t mod(n) = 1 mod(n) -> m^de=1*m mod(n)
----------------------------------------------------------------------------------------------------------
განაპირობებს საიდუმლო გასაღების საიდუმლოებას?
გასაღების საიდუმლოობას განაპირობებს ის ფაქტი, რომ ეილერის ფუქნციის გამოთვლას დიდი n ებისათვის ექსპონენციალური დრო სჭირდება (ძალიან დიდი ხანი ანუ).

2)გაარჩიეთ RSA ალგორითი 303 გვერდზე და ახსენით საიდან
მოვიდა გამოსახულება (p-1)(q-1).
φ(n)=φ(p)*φ(q)=(p-1)(q-1)

რაღაცას ჩავამატებ :) ამის წაკითხვა თუ გეზარებათ, ის მაინც იცოდეთ, რომ RSA-ს მთელი მუღამი ისაა, რომ მესიჯს ერთი გასაღებით "ვკეტავთ" და მეორეთი "ვხსნით" - ამბროლა სულ ამას იმეორებდა.