RSA ალგორითმი

ვიკიპედიიდან

ალგორითმი Rivest Shamir Adleman ანუ RSA არის კრიპტოგრაფიის ასიმეტრიული ალგორითმი (public სიტყვა-გასაღები), მნიშვენელოვან გამოყენებას ჰპოვებს ელექტრონულ კომერციაში, განსაკუთრებით საიდუმლო მონაცემების გაცვლა-გამოცვლისათვის ინტერნეტში. ეს ალგორითმი შეიქმნა რონ რივესტის, ადი შამირის და ლენ ადლემანის მიერ 1977 წელს, საიდანაც მოდის მისი სახელწოდება.

სექციების სია

1 ძირითადი ფუნქციონირება
2 უფრო დაწვრილებით ფუნქციონირების შესახებ
3 სიტყვა-გასაღებების შექმნა
4 ტექსტის დაშიფვრა
5 ტექსტის გაშიფვრა
6 დაპროგრამება-დანერგვა
7 უსაფრთხოება
8 პროგრამები
9 თავდასხმები
- 9.1 Wiener-ის თავდასხმა
- 9.2 Hastad-ის თავდასხმა
10 ქრონომეტრიული თავდასხმა
11 თავდასხმა არჩევითი შიფრაციით
12 იხილეთ აგრეთვე
13 ლიტერატურა
14 რესურსები ინტერნეტში

[რედაქტირება] ძირითადი ფუნქციონირება

ეს ალგორითმი იყენებს ორი ტიპის სიტყვა-გასაღებს: public, ტექსტის დასაშიფრად და private დაშიფრული ტექსტის გასაშიფრად. public სიტყვა-გასაღები ხელმისაწვდომია ყველასთვის ვინც შიფრავს ინფორმაციას, private კი ხელმისაწვდომია მხოლოდ მისთვის ვინც შექმნა ორივე სიტყვა-გასაღები. მაგალითად: ვთქვათ, ორ ადამიანს სურს საიდუმლო მონაცემების გაცვლა. ერთ-ერთი მათგანი, ჯემალი ქმნის ორივე სიტყვა-გასაღებს, შემდეგ public-ს უგზავნის სხვებს ბაკურს,ბეგლარას.... რომელთაც შეუძლიათ დაშიფრონ ტექსტი მოცემული public სიტყვა-გასაღებით,შემდეგ უგზავნიან ჯემალს რომელსაც შეუძლია გაშიფროს თავისი private სიტყვა-გასაღებით.

[რედაქტირება] უფრო დაწვრილებით ფუნქციონირების შესახებ

ამ ალგორითმის ავტორები იყენებენ Z/Zn რგოლს და ფერმატის თეორემას, რაც საშუალებას იძლევა მივიღოთ სპეციალური ფუნქციები(function trap) ანუ, ფუნქციები რომელთაც ერთადერთი მნიშვნელობები აქვთ "breach secret"-ზე. ეს მეთოდი გავრცელებულია და ფართო გამოყენებას ჰპოვებს(მაგ. ფრანგული საბანკო კარტა, კომერციული ვებ-გვერდები...). RSA აკეთებს გამოთვლას Z/Zn ჯგუფებში. მისი ალგორითმი მათემატიკურ პრინციპს ემყარება.

[რედაქტირება] სიტყვა-გასაღებების შექმნა

ვიღებთ ორ განსხვავებულ პირველ მარტივ რიცხვს $p$ და $q$ ;
შემდეგ $n$ -ს, $(n = p q)$ ;
გამოვთვლით Euler-ის ინდიკატორს $n$ : $\varphi(n) = (p-1)(q-1)$
ვიღებთ $e$ -ს, ისეთ პირველ მთელ რიცხვს, რომელსაც $\varphi(n)$ იყენებს როგორც დაშიფვრის ხარისხს.
რადგანაც $e$ მარტივია, ბეზუს თეორიიდან გამოდის რომ, იგი არის ინვერსიული mod $\varphi(n)$ არსებობს ისეთი მთელი $d$ რომლისთვისაც $ed \equiv1\pmod{\varphi(n)}$ . $d$ არის გაშიფვრის მაჩვენებელი.

$(n, e)$ წყვილი არის public სიტყვა-გასაღები, ხოლო $(n, d)$ -private სიტყვა-გასაღები.

[რედაქტირება] ტექსტის დაშიფვრა

ვთქვათ M არის მთელი რიცხვი (M<n) და წარმოადგენს ტექსტს. დაშიფრული ტექსტი იქნება:

$C \equiv M^e \pmod{n}$

[რედაქტირება] ტექსტის გაშიფვრა

C-ს გასაშიფრად ვიყენებთ d-ს (e mod $\varphi(n)$ -ის ინვერსიას) და გამოვთვლოთ $C^d \pmod{n}\,$ გვექნება:

$C^d \pmod{n} \equiv (M^e)^d \pmod{n} \equiv M^{ed} \pmod{n}\,$

რადგანაც $ed \equiv 1 \pmod{\varphi(n)}$ მოდულით გაყოფის განმარტებით გვექნება:

$ed = 1 + k \varphi(n) = 1 + k(p-1)(q-1)$ , სადაც $k \in \mathbb N$ .

ნებისმიერი მთელი M-თვის:

$M^{1+k(p-1)(q-1) }\equiv M \pmod p\,$

და

$M^{1+k(p-1)(q-1) }\equiv M \pmod q\,$ .

მართლაც, თუ M-ის და p-ის გამყოფები ურთიერთგანსხვავებულნი არიან, მაშინ ფერმატის თეორემის მიხედვით d, $M^{p-1} \equiv 1 \pmod p\,$ მაშასადამე $M^{k(p-1)(q-1)} \equiv 1 \pmod p\,$ puis $M^{1+k(p-1)(q-1)} \equiv M \pmod p\,$
si M n'est pas premier avec p, comme p est un nombre premier, cela signifie que M est multiple de p donc $M^{1+k(p-1)(q-1)} \equiv 0 \equiv M \pmod p\,$

თუ არა და, რადგანაც p არის მარტივი რიცხვი, გამოდის რომ M არის p-ს ჯერადი და $M^{1+k(p-1)(q-1)} \equiv 0 \equiv M \pmod p\,$

$M^{1+k(p-1)(q-1)} - M \,$ არის p-ს და q-ს ჯერადი, გაუსის ლემის მიხედვით მტკიცდება რომ, $M^{1+k(p-1)(q-1)} - M \,$ არის pq-ს ჯერადი ანუ n-ის, და გვექნება

$C^d \equiv M^{ed} \equiv M^{1+k(p-1)(q-1)} \equiv M \pmod n\,$

დგინდება, რომ ტექსტის დასაშიფრად საჭიროა ვიცოდეთ e და n. გასაშიფრად პირიქით - d და n.

იმისათვის, რომ გამოვთვალოთ e და n, d-ის საშუალებით, დაგვჭირდება e mod (p - 1)(q - 1 ) , აგრეთვე გვჭირდება ვიცოდეთ p და q-ს მნიშვნელობები.

[რედაქტირება] დაპროგრამება-დანერგვა

როცა RSA მეთოდის გამოყენებასთან გვაქვს საქმე, თავს იჩენს შემდეგი პრობლემები:

დიდი მარტივი რიცხვის არჩევა.
$M = c^e \mod{n}$ -ის გამოთვლა

დიდი მარტივი რიცხვის არჩევის მეთოდი არის შემდეგი: ვიღებთ ბიტების შემთხვევით მიმდევრობას (მაგ.:2048), შემდეგ ვამოწმებთ primality test(ალგორითმი რომელიც ამოწმებს მარტივია თუ არა რიცხვი)-ით. ამას მოსდევს კიდევ ერთი პრობლემა: მეთოდი, რომელიც აქ შეგვეძლო გამოგვეყენებინა, მაგალითად, ერასტოთენეს პირზმა, არის ძალიან ნელი. ამიტომ გამოიყენება სხვადასხვა primality probabilistic ტესტი(მაგ.: ფერმატის primality).

ეს ტესტი არ გვაძლევს უეჭველ პასუხს რომ რიცხვი მარტივია, მაგრამ დაზუსტებით გვეუბნება, რომ დიდია ალბათობა რომ იგი მარტივი იყოს. ასევე შეიძლება გამოვიყენოთ primality deterministic-ის ტესტი (polynomial-ის შემთხვევაში, რომელიც იძლევა აგრეთვე იმის საშუალებას, რომ დავაზუსტოდ მარტივია თუ არა რიცხვი (მაგ.: AKS-ის ალგორითმი).ეს უკანასკნელი ნაკლებად სწრაფია, თუმცა დანამდვილებით ამტკიცებს რიცხვის მარტივობას.

$M = c^e \mod{n}$ შეიძლება საკმაოდ გრძელი გამოდგეს, თუ მას ცუდად ავიღებთ. გასაგებია ისიც რომ ჯერ $c e$ -ს გამოთვლა და შემდეგ მისი მოდულით გაყოფა $n$ -ზე ცუდი იდეაა, რადგანაც ბევრ დროს მოითხოვს. ძირითადად, მაინც მამოიყენება მოდულლური ექსპონენცია.

აგრეთვე შესაძლებელია private სიტყვა-გასაღების განსხვავებული სახით შენახვა, რომელიც იძლევა უფრო სწრაფად გაშიფვრის საშუალებას ჩინური ნაშთის თეორემის დახმარებით.

[რედაქტირება] უსაფრთხოება

[რედაქტირება] პროგრამები

[რედაქტირება] თავდასხმები

[რედაქტირება] Wiener-ის თავდასხმა

Wiener-ის თავდასხმა(1989) მოქმედებს მაშინ როცა $d$ ნაკლებია $N^{\frac{1}{4}}$ . ხოლო $d$ -ს პოვნა შესაძლებელია $\frac{e}{N}$ უწყვეტი ფუნქციის გაშლით.

[რედაქტირება] Hastad-ის თავდასხმა

Hastad-ის თავდასხმა, ერთერთი პირველი თავდასხმა(აღმოჩენილი 1985 წ.), მოქმედებს როცა public e საკმაოდ პატარაა.როდესაც ხდება გაგზავნილი ტექსტური შეტყობინების დაჭერა, ჩინური ნაშთის თეორემის საშუალებით შესაძლებელია მისი თავდაპირველი სახის აღდგენა.

[რედაქტირება] ქრონომეტრიული თავდასხმა

[რედაქტირება] თავდასხმა არჩევითი შიფრაციით

[რედაქტირება] იხილეთ აგრეთვე

[რედაქტირება] ლიტერატურა

კრიფტოგრაფია, თეორია და პრაქტიკა, დუგლას სტინსონი, მეორე გამოცემა, Vuibert 2003
გამოყენებითი კრიპტოგრაფია, ბრიუს შნეიერი, მეორე გამოცემა, Vuibert, იანვარი 2001, ISBN 2-7117-8676-5.
კრიპტოგრაფია, პრინციპი, პიერ ბართელემი, რობერტ როლანდი, პასკალ ვერონი, ჰერმეს ლავუაზიე, 2005, ISBN 2-7462-1150-5

[რედაქტირება] რესურსები ინტერნეტში

რობერტ როლანდის ლექციები (ლუნინის მათემატიკის ინსტიტუტი) RSA-ს ფაილების შესახებ.