RSA ალგორითმი

RSA ალგორითმი
ალგორითმი Rivest Shamir Adleman ანუ RSA — კრიპტოგრაფიის ასიმეტრიული ალგორითმი (public სიტყვა-გასაღები), მნიშვენელოვან გამოყენებას ჰპოვებს ელექტრონულ კომერციაში, განსაკუთრებით საიდუმლო მონაცემების გაცვლა-გამოცვლისათვის ინტერნეტში. ეს ალგორითმი შეიქმნა რონ რივესტის, ადი შამირის და ლენ ადლემანის მიერ 1977 წელს, საიდანაც მოდის მისი სახელწოდება.
ძირითადი ფუნქციონირება
ეს ალგორითმი იყენებს ორი ტიპის სიტყვა-გასაღებს: public, ტექსტის დასაშიფრად და private დაშიფრული
ტექსტის გასაშიფრად. public სიტყვა-გასაღები ხელმისაწვდომია ყველასთვის ვინც შიფრავს ინფორმაციას, private კი ხელმისაწვდომია მხოლოდ მისთვის ვინც შექმნა ორივე სიტყვა-გასაღები.
მაგალითად: ვთქვათ, ორ ადამიანს სურს საიდუმლო მონაცემების გაცვლა. ერთ-ერთი მათგანი, ჯემალი ქმნის ორივე სიტყვა-გასაღებს, შემდეგ public-ს უგზავნის სხვებს ბაკურს,ბეგლარას.... რომელთაც შეუძლიათ დაშიფრონ ტექსტი მოცემული public სიტყვა-გასაღებით,შემდეგ უგზავნიან ჯემალს რომელსაც შეუძლია გაშიფროს თავისი private სიტყვა-გასაღებით.
უფრო დაწვრილებით ფუნქციონირების შესახებ
ამ ალგორითმის ავტორები იყენებენ Z/Zn რგოლს და ფერმას მცირე თეორემას, რაც საშუალებას იძლევა მივიღოთ სპეციალური ფუნქციები(function trap) ანუ, ფუნქციები რომელთაც ერთადერთი მნიშვნელობები აქვთ breach secret-ზე. ეს მეთოდი გავრცელებულია და ფართო გამოყენებას ჰპოვებს(მაგ. ფრანგული საბანკო კარტა, კომერციული ვებ-გვერდები...). RSA აკეთებს გამოთვლას Z/Zn ჯგუფებში. მისი ალგორითმი მათემატიკურ პრინციპს ემყარება.
სიტყვა-გასაღებების შექმნა
ვიღებთ ორ განსხვავებულ პირველ მარტივ რიცხვს და ;
შემდეგ -ს, ;
გამოვთვლით ეილერის ინდიკატორს :
ვიღებთ -ს, ისეთ პირველ მთელ რიცხვს, რომელსაც იყენებს როგორც დაშიფვრის ხარისხს.
რადგანაც მარტივია, ბეზუს თეორიიდან გამოდის რომ, იგი არის ინვერსიული mod არსებობს ისეთი მთელი რომლისთვისაც . არის გაშიფვრის მაჩვენებელი.
წყვილი არის public სიტყვა-გასაღები, ხოლო -private სიტყვა-გასაღები.
ტექსტის დაშიფვრა
ვთქვათ M არის მთელი რიცხვი (M<n) და წარმოადგენს ტექსტს. დაშიფრული ტექსტი იქნება:
ტექსტის გაშიფვრა
C-ს გასაშიფრად ვიყენებთ d-ს (e mod -ის ინვერსიას) და გამოვთვლოთ
გვექნება:
რადგანაც მოდულით გაყოფის განმარტებით გვექნება:
, სადაც .
ნებისმიერი მთელი M-თვის:
და
.
მართლაც, თუ M-ის და p-ის გამყოფები ურთიერთგანსხვავებულნი არიან, მაშინ ფერმას თეორემის მიხედვით d, მაშასადამე puis
si M n'est pas premier avec p, comme p est un nombre premier, cela signifie que M est multiple de p donc
თუ არა და, რადგანაც p არის მარტივი რიცხვი, გამოდის რომ M არის p-ს ჯერადი და
არის p-ს და q-ს ჯერადი, გაუსის ლემის მიხედვით მტკიცდება რომ, არის pq-ს ჯერადი ანუ n-ის, და გვექნება
დგინდება, რომ ტექსტის დასაშიფრად საჭიროა ვიცოდეთ e და n. გასაშიფრად პირიქით - d და n.
იმისათვის, რომ გამოვთვალოთ e და n, d-ის საშუალებით, დაგვჭირდება e mod (p - 1)(q - 1 ) , აგრეთვე გვჭირდება ვიცოდეთ p და q-ს მნიშვნელობები.
დაპროგრამება-დანერგვა
როცა RSA მეთოდის გამოყენებასთან გვაქვს საქმე, თავს იჩენს შემდეგი პრობლემები:
დიდი მარტივი რიცხვის არჩევა.
-ის გამოთვლა
დიდი მარტივი რიცხვის არჩევის მეთოდი არის შემდეგი: ვიღებთ ბიტების შემთხვევით მიმდევრობას (მაგ.:2048), შემდეგ ვამოწმებთ primality test(ალგორითმი რომელიც ამოწმებს მარტივია თუ არა რიცხვი)-ით. ამას მოსდევს კიდევ ერთი პრობლემა: მეთოდი, რომელიც აქ შეგვეძლო გამოგვეყენებინა, მაგალითად, ერასტოთენეს პირზმა, არის ძალიან ნელი. ამიტომ გამოიყენება სხვადასხვა primality probabilistic ტესტი(მაგ.: ფერმას primality).
ეს ტესტი არ გვაძლევს უეჭველ პასუხს რომ რიცხვი მარტივია, მაგრამ დაზუსტებით გვეუბნება, რომ დიდია ალბათობა რომ იგი მარტივი იყოს. ასევე შეიძლება გამოვიყენოთ primality deterministic-ის ტესტი (polynomial-ის შემთხვევაში, რომელიც იძლევა აგრეთვე იმის საშუალებას, რომ დავაზუსტოდ მარტივია თუ არა რიცხვი (მაგ.: AKS-ის ალგორითმი).ეს უკანასკნელი ნაკლებად სწრაფია, თუმცა დანამდვილებით ამტკიცებს რიცხვის მარტივობას.
შეიძლება საკმაოდ გრძელი გამოდგეს, თუ მას ცუდად ავიღებთ. გასაგებია ისიც რომ ჯერ -ს გამოთვლა და შემდეგ მისი მოდულით გაყოფა -ზე ცუდი იდეაა, რადგანაც ბევრ დროს მოითხოვს. ძირითადად, მაინც მამოიყენება მოდულლური ექსპონენცია.
აგრეთვე შესაძლებელია private სიტყვა-გასაღების განსხვავებული სახით შენახვა, რომელიც იძლევა უფრო სწრაფად გაშიფვრის საშუალებას ჩინური ნაშთის თეორემის დახმარებით.
უსაფრთხოება
პროგრამები
თავდასხმები
Wiener-ის თავდასხმა
Wiener-ის თავდასხმა(1989) მოქმედებს მაშინ როდესაც ნაკლებია . ხოლო -ს პოვნა შესაძლებელია უწყვეტი ფუნქციის გაშლით.
Hastad-ის თავდასხმა
Hastad-ის თავდასხმა, ერთ-ერთი პირველი თავდასხმა(აღმოჩენილი 1985 წ.), მოქმედებს როდესაც public e საკმაოდ პატარაა.როდესაც ხდება გაგზავნილი ტექსტური შეტყობინების დაჭერა, ჩინური ნაშთის თეორემის საშუალებით შესაძლებელია მისი თავდაპირველი სახის აღდგენა.
ქრონომეტრიული თავდასხმა
თავდასხმა არჩევითი შიფრაციით
იხილეთ აგრეთვე
დაშიფვრა
სიმეტრიული დაშიფვრა
ასიმეტრიული დაშიფვრა
აუთენტიფიკაცია
ციფრული ხელწერა
DSA (Digital Signature Algorithm)
RSA-ს გამოძახება
ლიტერატურა
კრიფტოგრაფია, თეორია და პრაქტიკა, დუგლას სტინსონი, მეორე გამოცემა, Vuibert 2003
გამოყენებითი კრიპტოგრაფია, ბრიუს შნეიერი, მეორე გამოცემა, Vuibert, იანვარი 2001, ISBN 2-7117-8676-5.
კრიპტოგრაფია, პრინციპი, პიერ ბართელემი, რობერტ როლანდი, პასკალ ვერონი, ჰერმეს ლავუაზიე, 2005, ISBN 2-7462-1150-5
რესურსები ინტერნეტში
რობერტ როლანდის ლექციები (ლუნინის მათემატიკის ინსტიტუტი) RSA-ს ფაილების შესახებ.
კრიპტოგრაფია