DES ალგორითმი

DES

სრული სახელი	DES (Data Encryption Standard)
გამოშვების თარიღი	1975 (1977 როგორც სტანდარტი)
გამომცემელი	IBM
წინამორბედი	Lucifer
განშტოებები	Triple DES, G-DES, DES-X, LOKI89, ICE
ბლოკის ზომა	64 bits
გასაღების სიგრძე	56 bits
სტრუქტურა Feistel-ის ქსელი	Feistel-ის ქსელი
კრიპტოანალიზი	წრფივი კრიპტოანალიზი,
	დიფერენციალური კრიპტოანალიზი, Brut-force

DES (ინგლ. Data Encryption Standard) — მონაცემთა დაშიფრვის სიმეტრიული ალგორითმი, რომელშიც ერთი და იგივე გასაღები გამოიყენება როგორც მონაცემთა დასაშიფრად, აგრეთვე მის გასაშიფრად.

DES-ი მუშაობს მონაცემთა 64-ბიტიან ბლოკებზე, დაშიფრვისთვის იყენებს 56-ბიტიან გასაღებს, აქვს ფეისტელის ქსელის ტიპის 16-ციკლიანი სტრუქტურა.

ალგორითმი იყენებს წრფივ (E, P, IP, FP გადანაცვლებები) და არაწრფივ (S-box) კომბინირებულ გარდაქმნებს. DES-ისთვის რეკომენდებულია რამდენიმე რეჟიმი, მაგ., Electronic Code Book (ECB) და Cipher Block Chaining (CBC). აგრეთვე ცნობილია, როგორც მონაცემთა დაშიფრვის ალგორითმი DEA (ინგ. Data Encryption Algorithm). დღესდღეობით მისი გმოყენება აღარ არის რეკომენდებული, მისი შესრულების სინელისა და მოკლე გასაღების გამო, რის გამოც იგი მუდმივი თავდასხმის საშიშროების ქვეშ დგას. DES-მეთოდი ძირითადად გამოიყენებოდა Unix-პაროლების დასაშიფრად. მისი ყველაზე გავრცელებული ნაირსახეობა იყო Triple DES.

DES-ის პირველი სტანდარტი გამოქვეყნდა FIPS(Federal Information Processing Standard)-ის მიერ 1977 წლის 15 იანვარს, ცნობილია "FIPS PUB 46-3"-ის სახელით.

ისტორიული მასალა

ამერიკულმა NBS-მ (National Bureau of Standards), რომელიც დღეისათვის NIST-ის (National Institute of Standards and Technology) სახელით არის ცნობილი, მოითხოვა ისეთი დაშიფვრის შექმნა, რომელიც ვარგისი იქნებოდა დაწესებულებებში გამოსაყენებლად. 1973 წლის 15 მაისს, შეერთებული შტატების უშიშროების ეროვნულ სააგენტოსთან (NSA, National Security Agency) კონსულტაციის შემდეგ, NBS-ნა გამოაცხადა კონკურსი დაშიფრვის მეთოდებზე, რომელშიც ვერც ერთმა კონკურსანტმა ვერ დააკმაყოფილა წამოყენებული საკმაოდ მკაცრი მოთხოვნები.1974 წლის 27 აგვისტოს ჩატარდა მეორე კონკურსი. ამჯერად, IBM-ის მიერ წარმოდგენილმა დაშიფრვის მეთოდი, სახელად Lucifer, ჩათვლეს მისაღებად. ეს იყო უფრო ადრეულ პერიოდში ჰორსტ ფეისტელის მიერ შემუშავებული დაშიფრვის მეთოდზე (ფეისტელის ქსელი, Feistel scheme, Feistel cipher) დაფუძნებული ალგორითმი. 1975 წლის 17 მარტს შემოთავაზებული იყო ალგორითმი DES, Lucifer-ის მოდიფიკაცია, რომელიც მიღებულ იქნა ფედერალურ ბიუროში. მომდევნო წელს გაიმართა 2 ღია სიმპოზიუმი, რომლებზეც განიხილებოდა DES-სტანდარტი. ამ სიმპოზიუმებზე მკაცრად გააკრიტიკეს NSA-ს მიერ ალგორითმში შეტანილი ცვლილებები: გასაღების პირვანდელი სიგრძის შემცირება, S-ბლოკების შექმნა. გავრცელდა ჭორები, იმის თაობაზე რომ NSA-მ განზრახ გაამარტივა და შეასუსტა ალგორითმი, რათა საშუალება ჰქონოდა მარტივად ეწარმოებინა კონტროლი დაშიფრულ მონაცემებზე. როგორც შემდგომში გაირკვა, DES-ის შემუშავების პროცესში, NSA-მ დაარწმუნა IBM-ი, რომ გასაღების შემცირებული სიგრძე აუცილებელსა დ საკმარისზე მეტია ნებისმიერი კომერციული application-ისთვის, გავლენა იქონია S-გადანაცვლებათა შემუშავებაზე და რომ DES-ის საბოლოო დასრულებული ვარიანტი, მათი აზრით, იყო დაშიფრვის საუკეთესო ალგორითმი, რომელშიც აღმოფხვრილი იყო სტატისტიკური ეა მათემატიკური ხარვეზები. აგრეთვე დადგინდა, რომ არასოდეს, NSA უშუალოდ არ ჩარეულა ალგორითმის შემუშავებში.

ეჭვების ნაწილი S-გადანაცვლებათა ფარული სისუსტის შესახებ გაქარწყლდა 1990-ში, ელი ბიჰამას (Eli Biham) და ადი შამირის (Adi Shmir) მიერ დიფერენციალურ კრიპტოანალიზზე (ძირითადი მეთოდი სიმეტრიული გასაღების მქონე ბლოკური ალგორითმების გასატეხად) ჩატარებული დამოუკიდებელი გამოკვლევების შედეგების გამოქვეყნების შემდეგ. DES-ალგორითმის S-ბლოკები აღმოჩნდა გაცილებით უფრო მდგრადი თავდასხმის წინააღმდეგ, ვიდრე ისინი შემთხვევითი წესით რომ აერჩიათ. ეს კი ნიშნავს იმას, რომ კრიპტოანალიზის ეს ტექნიკა NSA-სთვის ჯერ კიდევ XXს-ის 70-იან წლებში იყო ცნობილი.

სტრუქტურა და გამოყენება

DES-ის ალგორითმი მონაცემთა 64-ბიტიან ბლოკებს გარდაქმნის 64-ბიტიან განსხვავებულ ბლოკად. დასაშიფრად გამოიყენება 56-ბიტიანი სიმეტრიული გასაღები, წარმოდგენილი 64 ბიტში (ყოველი ბაიტის თითო ბიტი საკონტროლოა). დაშიფრვა ბლოკურ-იტერაციულია, რომელსაც ფეისტელის ქსელის სტრუქტურა აქვს.

DES-ში გამოიყოფა 3 ძირითადი ეტაპი:

ბლოკის საწყისი და საბოლოო პერმუტაცია. ბიტურ გადანაცვლებათა 16 იტერაციიანი ციკლი, რის შესრულების შემდეგ გენერირდება საბოლოო შედეგი.

გამოყენების მაგალითი

თითოეულ იტერაციაზე, ალგორითმში წარმოდგენილი f - ციკლური ფუნქცია ამუშავებს ბლოკის 32-ბიტს (ნახევარ ბლოკს), და პარამეტრად იყენებს 48-ბიტიან ქვეგასაღებს (J). თავდაპირველად ხდება ე.წ. გაფართოება, შემავალი 32 ბიტი გარდაიქმნება 48-ბიტში (ზიგიერთი ბიტი მეორდება).

გაფართოების სქემა მოცემულია ქვემოთ(რიცხვები შეესაბაება შემავალ 32-ბიტიან ბლოკში ბიტების რიგით ნომრებს):

   ${\begin{matrix}32&1&2&3&4&5\\4&5&6&7&8&9\\8&9&10&11&12&13\\12&13&14&15&16&17\\16&17&18&19&20&21\\20&21&22&23&24&25\\24&25&26&27&28&29\\28&29&30&31&32&1\end{matrix}}$

შემდეგ მიღებულ 48-ბიტიან ბლოკსა და მიმდინარე ქვეგასაღებზე სრულდება ოპერაცია XOR-ი.

მიღებული 48-ბიტიანი ბლოკი გარდაიკმნება 32-იანად S-ბლოკის საშუალებით. შემდეგ სქემის მიხედვით სრულდება კიდევ ერთი გდანაცვლება(რიცხვები წარმოადგენენ ბიტების რიგით ნომრებს):

   ${\begin{matrix}16&7&20&21\\29&12&28&17\\1&15&23&26\\5&18&31&10\\2&8&24&14\\32&27&3&9\\19&13&30&6\\22&11&4&25\end{matrix}}$

შიფრაცია იწყება შემავალ მონაცემთა 64-თანრიგა ბლოკის ბიტების გადანაცლებით (IP - Initial Permutation) : 58-ე ბიტი ხდება პირველი, 50-ე მეორე და ა.შ.

 ${\begin{matrix}58&50&42&34&26&18&10&2\\60&52&44&36&28&20&12&4\\62&54&46&38&30&22&14&6\\64&56&48&40&32&24&16&8\\57&49&41&33&25&17&9&1\\59&51&43&35&27&19&11&3\\61&53&45&37&29&21&13&5\\63&55&47&39&31&23&15&7\end{matrix}}$

მიღებული ბლოკი იყოფა ორ 32-ბიტიან L₀ და R₀ ნაწილად. შემდგომ, 16-ჯერ სრულდება შემდეგი 4 პროცედურა:
- გსაღების გარდაქმნა i ციკლის მთვლელის მნიშვნელობის გათვალისწინებით (ბიტების გადანაცვლება 8 ბიტის ამოგდებით, შედეგად ვიღებთ 48-თანრიგა გასაღებს).
- დავუშვათ, A=L_i, და J წარმოადგენს ქვეგასაღებს (გარდაქმნილ, 48-ბიტზე დაყვანილ გასაღებს). f(A,J) ფუნქციით გენერირდება ციკლური ფუნქციის 32-ბიტიანი გამოსავალი მნიშვნელობა.
- სრულდება ოპერაცია XOR (Ri, f(A,J)). შედეგი აღინიშნება R_i+1.
- სრულდება ოპერაცია L_i+1=R_i.
ციკლის 16 იტერაციის დატრიალების შემდეგ სრულდება კიდევ ერთი ბიტური გადანაცვლება(საწყისის ინვერსიული). 64 ბიტის გადანაცვლება ხდება შემდეგნაირად (40-ე ხდება პირველ ბიტად ჯდება მე-40, მეორე ბიტად - მე-8 და ა.შ.).

 ${\begin{matrix}40&8&48&16&56&24&64&32\\39&7&47&15&55&23&63&31\\38&6&46&14&54&22&62&30\\37&5&45&13&53&21&61&29\\36&4&44&12&52&20&60&28\\35&3&43&11&51&19&59&27\\34&2&42&10&50&18&58&26\\33&1&41&9&49&17&57&25\end{matrix}}$

S-box წარმოადგენს ცხრილს, რომელიც შემდგარს 4 სტრიქონისა და 16 სვეტისაგან. პირველი S₁ S-ბლოკი წარმოდგენილია ქვემოთ:

 ${\begin{array}{c|cccccccccccccccc}{\mbox{No.}}&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline 0&14&4&13&1&2&15&11&8&3&10&6&12&5&9&0&7\\1&0&15&7&4&14&2&13&1&10&6&12&11&9&5&3&8\\2&4&1&14&8&13&6&2&11&15&12&9&7&3&10&5&0\\3&15&12&8&2&4&9&1&7&5&11&3&14&10&0&6&13\end{array}}$

შემავალი 48-ბიტიანი ბლოკი იყოფა 8 ჯგუფად, თითო 6-ბიტიანად. ჯგუფში პირველი დ ბოლო ბიტი გამოიყენება სტრიქონის მისამართის აღსანიშნავად, შუა 4 ბიტი - სვეტის აღსანიშნავად. შედეგად ყოველი 6 ბიტი გარდაიქმნება 4 ბიტად, ანუ მთელი 48-ბიტიანი კოდი 32-ტანრიგად (ამისათვის საჭიროა 8 S-ბლოკი).

არსებობს DES-სტანდარტი აპარატული რეალიზაცია, რომელიც უზრუნველჰყოფს მაღალ მწარმოებლურობას.

თავდასხმა

მიუხედავად იმისა, რომ ამ ალგორთმზე გაცილებით მეტი კრიპტოანალიზია ჩატარებული, ვიდრე სხვებზე, მისი გატეხვის საუკეთესო გზად უხეში ძალის მეთოდი რჩება. მცირედი კრიპტოგრაფიული სისუსტეები და სამი თეორიული შეტევის შესაძლებლობა, რეალიზაციისათვის მოითხოვს ძალიან დიდი რაოდენობის მასალას ცნობილი და არჩეული ღია ტექსტით შეტევისათვის, რაც პრაქტიკულად შეუძლებლად მიიჩნევა.

შეტევა უხეში ძალით

მთავარი სტატია: უხეში ძალის მეთოდი.

ნებისმიერი შიფრისათვის არსებობს შეტევის მეთოდი - ყველა შესაძლო გასაღების გადარჩევა. შესაძლო გასაღებების სიმრავლეს განსაზღვრავს მისი სიგრძე. DES-ისთვის იგი წარმოადგენს 2⁵⁶ სიმბოლოს. ალგორითმის პროექტირების პროცესში წამოიჭრა საკითხი გასაღების სიმოკლის გამო, რაც საფრთხეს წარმოადგენდა მომავალი კრიპტოანალიზის კუთხით. მაგრამ კონსულტაციების შედეგად, რომელშიც მონაწილეობას NSA-ც იღებდა, საბოლოოდ გადაწყდა, რომ გასაღების ზომა თავდაპირველი 128 ბიტიდან 56 ბიტამდე შემცირებულიყო.

DES-ის უხეში ძალით გასატეხად რამდენიმე მანქანა იქნა დაპროექტებული. 1977 წელს უიტფილდ დიფიმ და მარტინ ჰელმანმა დააპროექტეს 20 მილიონ დოლარად ღირებული მანქანა, რომელსაც შეეძლო შიფრაციის გასაღების პოვნა ერთ დღეში. 1997 წელს ვინერმა წარმოადგინა მანქანის პროექტი, რომელსაც შეეძლო იგივეს გაკეთება 7 საათში. თუმცა არც ერთი ეს მანქანა არ ყოფილა პრაქტიკულად რეალიზებული. 1997 წელს RSA Security-ის მიერ გამოცხდებულ იქნა კონკურსი ალგორითმის გასატეხად, 100 ათასდოლარიანი პრიზით, რომელიც მოიგო DESCHALL Project-ის ჯგუფმა, რომელთაც ინტერნეტში განაწილებული გამოთვლების ქსელი გამოიყენეს. 1998 წელს გატეხვა მოახდინეს 250 ათას დოლარად ღირებული სპეციალურად აგებული მანქანით (EFF DES cracker), რომელმაც შიფრაციის გასაღების პოვნა 2 დღეში შეძლო.

2006 წელს გერმანიის ორმა საუნივერსიტეტო ჯგუფმა წარმოადგინა მანქანა, სახელად COPACOBANA, რომლის რირებულა 10,000 დოლარს აღწევს და შედგება ფართოდ ხელმისაწვდომი კომპონენტებისგან. COPACOBANA იყენებს XILINX Spartan3-1000-ის ტიპის 120 ცალ პროგრამირებადი ვენტილების მასივს (პვმ), რომლებიც პარალელურ რეჟიმში მუშაობენ. დღესდღეობით DES-ის გატეხვის სისწრაფის რეკორდი ეკუთვნის ფირმა SciEngines-ის აპარატს RIVYERA, რომელიც Spartan-3 5000-ის 128 პბმ-ს იყენებს.

გაუმჯობესებული შეტევა

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

დიფერენციალური კრიპტოანალიზი აღმოჩენილ იქნა 1980 წელს ელი ბიჰემისა და ადი შამირის მიერ. ეს მეთოდი ცნობილი იყო IBM-ისა და NSA-სთვის, თუმცა ფაქტი საიდუმლოდ რჩებოდა. DES-ის 16-ივე ციკლის გასატეხად, დიფერენციალურ კრიპტოანალიზს ესაჭიროება 2⁴⁷ არჩეული ღია ტექსტი. DES თავიდანვე პროექტირებულ იქნა ამ მეთოდის მიმართ მედეგობის გათვალისწინებით.
წრფივი კრიპტოანალიზი შეიმუშავა მიცურუ მაცუიმ 1993 წელს და მოითხოვს 2⁴³ ცნობილ ღია ტექსტს. თუმცა ამ ტიპის ანალიზის წარმატებული შედეგები ცნობილი არ არის. მრავალჯერადი წრფივი კრიპტოანალიზით შესაძლებელია კრიპტოანალიზის სირთულე კიდევ 4-ჯერ შემცირდეს (2⁴¹)
წინა ორი მეთოდისგან განსხვავებით, რომლებიც შიფრაციის ალგორითმთა ფართო წრეს ეხება, დეივისის შეტევა კონკრეტულად DES-ის წინააღმდეგაა მიმართული. ყველაზე ძლიერი ვერსია ანალიზისათვის ითხოვს 2⁵⁰ ცნობილ ღია ტექსტს, აქვს 2⁵⁰ გამოთვლითი სირთულე და 51% წარმატების ალბათობა.

სხვა სისუსტეები

არსებობს DES-ის 4 გასაღები (ე.წ. სუსტი გასაღები), რომელთათვისაც სრულდება პირობა

E_{K}(E_{K}(P))=P

ანუ

E_{K}=D_{K}

ასევე არსებობს 6 ე.წ. ნახევრად სუსტი გასაღები, რომელთათვისაც

E_{K_{1}}(E_{K_{2}}(P))=P

ანუ

E_{K_{2}}=D_{K_{1}}.

ამ შემთხვევაში ერთი გასაღებით დაშიფრული ინფორმაციის მეორე გასაღებით ხელახლა შიფრაციას მივყავართ საწყის ღია ტექსტზე.

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

დამტკიცებულია, რომ DES-ის მაქსიმალური დაცვა 64 ბიტს შეადგენს, თუნდაც ციკლებში გამოყენებული ქვეგასაღებები ძირითადი გასაღებისგან დამოუკიდებლად იყოს არჩეული (როდესაც საერთო გასაღების სიგრძე 768 ბიტი იქნებოდა).

სტატუსი

თავდაპირველად IBM (International Business Machines Corporation)-ის მიერ შემუშავებული ალგორითმი იყენებდა 112-ბიტიან გსაღებს.

შემდგომ NSA-ს გავლენით გასაღების სიგრძე შემცირდა და დავიდა 56-ბიტამდე. დღემდე, Triple DES რჩება ძალზედ გავრცელებული და რაც შეეხება "მარტივ" DES-ალგორითმებს,ის გამოიყენება მხოლოდ მოძველებულ application-ებში.

2001 წელს DES სტნდარტი შეიცვალა AES(Advanced Encryption Standard)-ით.