Data Encryption Standard (DES) е стандарт за криптиране на данни, изобретен в САЩ през 80-те години на ХХ век. Сред шифрите той се смята за „пенсиониран“, като остава работен кон на криптография. DES не е подходящ за високоскоростно инженерство и големи обеми данни поради ограничения от 56 бита на ключ и 64 бита на данни. Въпреки това, той все още се използва.

Какво представляват блоковите шифри?

DES - алгоритъм за шифроване на блокове. През последните 20-30 години бяха създадени много блокови шифри, но за да се създаде добър шифър, който е безопасен, задачата е доста сложна. Важно е шифърът да има характеристики, които ще му позволят да функционира в много области и индустрии. Блочните шифри се състоят от няколко повторения на алтернативното използване на някакъв шифър. Всяка итерация се нарича кръг. Както показва практиката, дори някои от примитивните алгоритми с последователна употреба могат да създадат надеждни шифри. DES алгоритъмът е пример, който остава стабилен и неуязвим в продължение на 20 години.


Този подход при разработването на шифри значително улеснява и опростява анализа на сигурността. Например тестова атака на блоков шифър започва с минимален брой кръгове и продължава методично с увеличаване на броя на кръговете.

Използване на DES

Въпреки че DES е остаряла и не отговаря на настоящите изисквания, тя може да се използва например като 3DES, когато шифърът се прилага три пъти подред. Този подход премахва ограничението за размера на ключа, но криптираният блок данни остава непроменен. В собствената сиDES времето беше достатъчно бързо и криптографско. В момента това не е така и 3DES е три пъти по-бавен. Въпреки това DES все още се използва в редица системи, но използването му в нови проекти е забранено.


Официалният алгоритъм DES е стандарт в САЩ до 1998 г. През 1997 г. започва да се създава нов стандарт, наречен AES (Advanced Encryption System), и въпреки че криптоанализата показва, че опитът да се разчупи DES води до набор от системи на нелинейни уравнения, аналитичните методи не могат да помогнат за решаването на проблем - неговата слабост е малък набор от възможни ключове. , Броят им е равен на 2 56 и всички варианти могат да бъдат преодолени с помощта на съвременни технологии за сравнително кратко време.

Един кръг в алгоритъма

За яснота на представянето и описанието на алгоритъма DES, използвайки чертеж (линейна изчислителна схема) 4.1 показва структурата на един кръг. Всеки правоъгълник в линейна диаграма представлява някакъв вид изчисление, а лявата стрелка показва къде ще бъдат предадени резултатите от блока. Знакът плюс в кръга е маркиран от операцията "изключване или", наречена XOR програмиране. Операцията все още носи името "добавяне на битове" или "добавяне без прехвърляне". Мрежата може да намери алгоритъма DES на C и да я изучи за по-добро разбиране. DES приема 64-битов текстов блок. Той преминава през първоначално пренареждане по определен принцип. При анализа на алгоритъма стана ясно, че смисълът в тази пермутация е малък, тъй като не дава никакъв криптографски ефект. текстовУредът е разделен на 2 равни части: дясна (R) и лява (L). След това кодираните части се променят и обединяват, а в края на кръглия 64-битов блок се криптират.

Общ алгоритъм

DES алгоритъмът включва 16 кръга, които се извършват съгласно описаната по-горе схема. Всички кръгове са номерирани чрез i, където i = (1; 16). Всеки i-ти кръг от пара (Li-1 Ri-1) получава нова двойка (Li, Ri), използвайки ключа Ki. Основните трансформации се извършват в рамките на функцията F.

Алгоритъм за F функция

Както може да се види от фигура 4.1 R преминава през операцията "Разширяване". Този блок дублира серия от битове от R и ги допълва с тях, получавайки 48-битова стойност. Полученият резултат преминава през побитово добавяне с 48-битовия Ke ключ. Резултатът от тази операция се предава на блок S. Блок S съдържа 8 малки матрици за подмяна, които се подбират по специален начин. Всяка матрица получава на входа на 6 бита информация и издава 4-битова стойност. Като резултат блокът S получава 48-битови данни на входа и на изхода резултатът е 32-битова стойност. Тази 32-битова стойност преминава през друга операция на пермутация, след което се сумира от операцията xor на L. Накрая правата и лявата част променят местата и кръгът завършва. Както вече споменахме, 16 такива алгоритми изпълняват такива кръгове. Тук няма да претоварваме статията с примери, които заемат много място. Работата на алгоритъма за криптиране DES и примерите могат да се видят онлайн.

Код на Fiesteel

Алгоритъмът DES се основава на шифъра Fiesteel.Неговата идея е много сложна. Във всеки кръг, част L се състои от стойността на F (R, Ki) и L се заменя с позиция R. Ключовата характеристика на алгоритъма Feistle е, че дешифрирането и кодирането се състоят от едни и същи стъпки: части L и R променят местата, а след това операцията по добавяне L и F (R, Ki). Това прави процедурите за криптиране и декриптиране прости и лесни за разбиране.
В кодовете на Фейстел най-често се въвежда една интересна промяна - премахването на пермутацията на L и R в последната итерация. Това прави алгоритмите за криптиране и декриптиране напълно симетрични. Разликата е само в използването на ключовете Ke. Този принцип се оказа много лесен за използване на ниво програма, тъй като криптирането и декриптирането се извършват с една функция. Например кратко представяне на алгоритъма за криптиране DES за C.

Ключове за кодиране

Шестнадесет 48-битови ключа се използват за криптиране на DES данните. Един ключ на кръг. Всеки ключ се създава чрез семплиране на 48 бита от 56-битовия главен ключ. Създаването на ключове или други кръгове се определя от механизма, описан подробно в документацията DES. Накратко, алгоритъмът за проба и ключ е следният. Прилепът се добавя към главния ключ на позиция 81624 324048 5664. Това се прави по такъв начин, че всеки байт съдържа нечетен брой единици. Спазването на правилата помага за идентифициране на грешки при превключване на ключовете. След това, използвайки специалните електронни таблици, завършеният ключ подлежи на пермутации и смени, с изключение на добавените битове. Така и такасе получава необходимия ключ.

DES Компоненти

Всеки компонент на DES алгоритъма решава определен проблем:

Алгоритъмът на Fiestel опростява криптирането и декриптирането, като същевременно гарантира, че двете страни на текста са смесени.

Добавянето на текстови части с ключове един до друг взаимодейства с отворени данни с ключ и ги кодира.

S-блока и таблиците за съвпадение правят алгоритъма нелинеен, увеличавайки неговата устойчивост на различни атаки.

Разширяването, S-блокът и пермутациите осигуряват дифузия на алгоритъма - лавинен ефект. С други думи, ако входните данни на F ще се променят най-малко 1 бит, тогава ще предизвика промяна в множеството от битове наведнъж. Ако лавинен ефект не се наблюдава в шифъра, промените в отворените данни ще доведат до еквивалентни промени в криптираната форма, които могат да бъдат проследени и използвани за хакване. В криптографията има критерий за лавинен ефект. Алгоритъмът го удовлетворява, ако най-малко половината от криптираните данни се променят при смяна на 1 бит от отворени данни. Алгоритъмът DES го удовлетворява, започвайки с 4 кръга. Резюме - при смяна на 1 бит от отворени данни в DES шифъра ще бъдат променени 29 бита.

Проблеми със сигурността в DES

Очевидният проблем на DES е изборът на ключове за шифроване с общ ключ. Какво ще стане, ако изберете нула като ключ (всички битове на ключовете са 0)? Това ще доведе до вземане на проби от всички ключове за криптиране във всеки кръг, които са еднакви, и всички ключове ще са нула. Не само това, 16 криптирани ще отидат с един ключ, поради факта, че алгоритмите за криптиране и декриптиране на DESсе различават само по реда на използването на ключовете, те ще бъдат напълно идентични. Цялото значение на криптирането ще бъде загубено.

DES има 4 ключа, които се наричат ​​слаби, което води до описания ефект. DES има 12 полу-слаби и 48 псевдо-слаби ключа, които водят до ограничаване на вариациите на генерираните ключове в кръговете. С други думи, има вероятност 16 различни ключа да се използват по време на криптиране в 16 кръга и 8 4 или дори 2. По-малко очевиден недостатък на DES е свойството на взаимно допълване. Това означава, че ако шифровате с отворен текст и добавки за ключове, резултатът ще бъде стойност, която е допълнение към шифрирания текст. Това безсмислено свойство може да доведе до успешни атаки на проекти, които използват DES за осигуряване на сигурност.

Проблемът с ключа за криптиране

е от основно значение за DES и се счита за основната причина, поради която този алгоритъм трябва да бъде изоставен. Тъй като размерът на DES ключа е 56 бита, ще трябва да прегледате 2 56 опции за сканиране на всички ключове. Това ли е толкова? Ако направите 10 милиона ключови проверки в секунда, тогава ще ви трябват около 2000 години за проверка. Изглежда, че алгоритъмът е доста стабилен. Така беше и през миналия век, когато създаването на компютър с подобна сила беше почти невъзможна задача както от техническа, така и от финансова гледна точка. Ако създадете компютър с милион чипа, търсенето на всички много ключове DES ще отнеме 20 часа. Първият такъв компютър за декодиране на алгоритъма DES се появи през 1998 г., койтосе справи със задачите за 56 часа. Съвременните технологии на мрежите и паралелните процеси позволяват да се намали още повече това време.

Криптоанализ и DES

Възможно е без преувеличение да се каже, че DES е причината за появата на приложна наука, наречена "криптографски анализ". От началото на появата на DES са правени опити за разрушаването му, научна работа по нейното изследване. Всичко това доведе до появата на такива области на математиката, като:

линейна криптоанализа - изследване и откриване на връзката между отворен код и криптирана;

диференциален криптоанализ - изучаване и анализиране на зависимости между няколко отворени текстове и техните криптирани версии;

криптоанализ на свързани ключове - изследване на връзката между криптирани текстове, получени на първичния ключ и ключовете, свързани с основната по някакъв начин.

DES поддържа 20 години глобален криптоанализ и атаки, но остава силен шифър. Но кой търси - той винаги ще намери

Бихамас и Шамир, израелски учени, през 1991 г. показаха с диференциален криптоанализ, че атаката може да бъде извършена на DES, в която ключът е бил изчислен, при условие че нападателят има 2 47 специално подбрани двойки. отворени и криптирани текстове.

Японският учен Mitsui Matsui през 1993 г. показа, че ключът може да бъде изчислен чрез линейна криптоанализа. За да направите това, трябва само да знаете 2 47 двойки отворен текст и съответната криптирана версия.

Освен това тези хакерски техники бяха леко преработени, подобрени и опростени, както и редица новиначини за счупване. Но те остават твърде сложни, на фона на техния опит, пълен преглед на всички ключови опции изглежда най-подходящата атака срещу DES.