DES () — це симетричний алгоритм шифрування певних даних, стандарт шифрування прийнятий урядом США із 1976 до кінця 1990-х, з часом набув міжнародного застосування. Ще з часу свого розроблення алгоритм викликав неоднозначні відгуки. Оскільки DES містив засекречені елементи своєї структури, породжувались побоювання щодо можливості контролю з боку Національного Агентства Безпеки США (). Алгоритм піддавався критиці за малу довжину ключа, що, врешті, після бурхливих обговорень та контролю академічної громадськості, не завадило йому стати загальноприйнятим стандартом. DES дав поштовх сучасним уявленням про блочні алгоритми шифрування та криптоаналіз.
Зараз DES вважається ненадійним в основному через малу довжину ключа (56 біт) та розмір блоку (64 біти). У 1999 ключ DES було публічно дешифровано за 22 години 15 хвилин. Вважається, що алгоритм достатньо надійний для застосування у модифікації 3-DES, хоча існують розроблені теоретичні атаки. DES поступово витісняється алгоритмом AES, що з 2002 року є стандартом США.
Щиро кажучи, існує різниця між стандартом DES (Data Encryption Standard) та алгоритмом DEA (Data Encryption Algorithm).
Історія DES Історія розробки DES сягає початку 1970-х і почалась за ініціативи Національного Бюро Стандартів США () — тепер, Національний Інститут Стандартів і Технологій () — для забезпечення засекречених урядових даних. 15 травня 1973, після консультування із Національним Бюром Безпеки США, НБС оголосило конкурс на розробку алгоритму шифрування який би відповідав поставленим строгим архітектурним вимогам, однак, таких пропозицій не надійшло. Лише на другий конкурс 27 серпня 1974 IBM подала розробку яка задовільняла поставленим вимогам — алгоритм, розроблений в період 1973—1974, в основу якого був покладений шифр Хорста Фейстеля Люцифер.
Хронологія Дата Рік Подія 15 травня 1973 Національне Бюро Стандартів (НБС) США опублікувало перший запит на стандарт алгоритму шифрування. Ніхто не відреагував 27 серпня 1974 НБС опублікувало другий запит на алгоритм шифрування. IBM подала заявку 17 березня 1975 DES опубліковано у Federal Register для коментарів Серпень 1976 Перший робоча зустріч по DES Вересень 1976 Друга робоча група, обговорення математичного підґрунтя DES Листопад 1976 DES погоджено як стандарт 15 січня 1977 DES опубліковано як стандарт FIPS PUB 46 1983 DES знову підтверджується як стандарт 22 січня 1988 DES вдруге підтверджується як стандарт (FIPS 46-1) Липень 1990 Біхем і Шамір заново відкривають диференціальний криптоаналіз, і застосовують його до 15-раундової DES-подібної криптосистеми. 1992 Біхем і Шамір описують теоретичну атаку із меншою часовою складністю ніж повний перебір: диференціальний криптоаналіз. Однак, для її успішності необхідно 247 незашифрованих даних. 30 грудня 1993 DES втретє підтверджується як стандарт (FIPS 46-2) 1994 Вперше проведено експериментальний криптоаналіз DES використовуючи лінійний криптоаналіз (Matsui, 1994). червень 1997 Вперше публічно зломано зашифроване повідомлення DES. Проект DESCHALL липень 1998 EFF's (Deep Crack) дешифрує ключ DES за 56 годин. січень 1999 Разом та distributed.net дешифрують ключ DES за 22 години 15 хвилин. 25 жовтня 1999 DES вчетверте підтверджується як стандарт (FIPS 46-3), в якому зазначено, що надавати перевагу слід 3-DES. 26 листопада 2001 AES опубліковано як стандарт (FIPS 197) 26 травня 2002 AES вступає в силу
Опис алгоритму
DES є блочним шифром — дані шифруються блоками по 64 біти — 64 бітний блок явного тексту подається на вхід алгоритму, а 64-бітний блок шифрограми отримується в результаті роботи алгоритму. Крім того, як під час шифрування, так і під час дешифрування використовується один і той самий алгоритм (за винятком дещо іншого шляху утворення робочих ключів).
Ключ має довжину 56 біт (як правило, в джерельному вигляді ключ має довжину 64 біти, де кожний 8-й біт є бітом паритету, крім того, ці контрольні біти можуть бути винесені в останній байт ключа). Ключем може бути довільна 64-бітна комбінація, яка може бути змінена у будь-який момент часу. Частина цих комбінацій вважається слабкими ключами, оскільки може бути легко визначена. Безпечність алгоритму базується на безпечності ключа.
На найнижчому рівні алгоритм є ніщо інше, ніж поєднання двох базових технік шифрування: перемішування і підстановки. Цикл алгоритму, з яких і складається DES є комбінацією цих технік, коли як об'єкти перемішування виступають біти тексту, ключа і блоків підстановок.
Початкова перестановка На вході подаються 64-бітний блок даних, які переставляються згідно з таблицею: + Початкова перестановка IP1234567891011121314151617181920212223242526272829303132585042342618102605244362820124625446383022146645648403224168 +333435363738394041424344454647484950515253545556575859606162636457494133251791595143352719113615345372921135635547393123157
16 раундів Далі 16 разів повторюються наступні операції:
Функція розширення блоку Функція Е розширює 32-бітовий вектор до 48-бітового вектора шляхом повторення деяких біт з згідно з таблицею:
+ Функція розширення E_1234__5678__9101112__13141516__17181920__21222324__25262728__29303132_3212345456789891011121312131415161716171819202120212223242524252627282928293031321
Перший рядок — номери вхідних біт, другий рядок — вихідні біти. Повторення номерів, означає повторення біт.
Додавання раундового ключа Блок 48 біт XOR'иться з раундовим ключем .
Таблиці підстановки
S-блоки мають вигляд:
+ S-блок , i=1…8 012345678910111213141501441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613015181461134972131205101313471528141201106911520147111041315812693215313810131542116712051490100914631551131271142811370934610285141211151 21364981530111212510147311013069874151431152120713143069101285111241511381156150347212110149210690121171315131452843315061011389451112721402124171011685315130149114112124713150151039862421111013781591256301431181271142136150910453012110159268013341475111101542712956113140113829141552812370410113116343212951510111417608130411214150813312975106111301174911014351221586214111312371410156805923611138141079501514231201328461511110931450127111513810374125611014922711419121420610131535832114741081315129035611
«Розширені» біти використовуються для визначення номера 0-1-2-3 таблиці (ліва колонка).
Перестановка Далі виконується перестановка + Перестановка P12345678910111213141516171819202122232425262728293031321672021291228171152326518311028241432273919133062211425
XOR лівої і правої частин За формулою
отримуємо значення .
Кінцева перестановка Після 16-ти раундів застосовуюєть перестановка біт: + Перестановка 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636440848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725
Вхідний перший біт ставить на місце номер 40, другий біт на місце номер 8 і т. д.
В DES використовується 16 циклів, вихідними даними для кожного з них 64 є біти відкритого тексту (на вході першого раунду) чи 64 біти з результату роботи попереднього раунду (у всіх наступних), ключ і блоки підстановок.
Алгоритм використовує лише стандартні елементарні логічні операції (зсув, сума по модулю два(XOR)) на числах довжиною 64 біти, що значно полегшує програмування алгоритму і прискорює його роботу у інтегральних мікросхемах. Циклічний характер алгоритму в сумі з ідеальною здатністю до запрограмовування робить алгоритм швидким і легким до розуміння.
Розширення ключа (генерація раундових ключів ) Ключі отримують з початкового ключа k (64 біт = 8 байтів або 8 символів у ASCII) наступним чином. Вісім бітів, що знаходять в позиціях 8, 16, 24, 32, 40, 48, 56, 64 додаються в ключ k таким чином щоб кожен байт містив непарне число одиниць. Це використовується для виявлення помилок при обміні і зберіганні ключів. Потім роблять перестановку для розширеного ключа (крім доданих бітів номер 8, 16, 24, 32, 40, 48, 56, 64). Така перестановка визначена в таблиці 5.
+ Початкова перестановка біт ключа5749413325179158504234261810259514335271911360524436 6355473931231576254463830221466153453729211352820124
Ця перестановка визначається двома блоками і по 28 біт кожен. Перші 3 біта є біти 57, 49, 41 розширеного ключа. А перші три біта є біти 63, 55, 47 розширеного ключа.
Для раундів i = 1,2,3 … отримують з одним або двома лівими циклічними зрушеннями згідно з таблицею:
+ Циклічний зсувi-й раунд12345678910111213141516Число зсувів1122222212222221
Ключ , i = 1, … 16 складається з 48 біт, вибраних з бітів вектора (56 біт) згідно з приведеною нижче таблицею. Перший і другий біти є біти 14, 17 вектора
+i-й біт раундового ключа123456789101112131415161718192021222324252627282930313233343536373839404142434445464748номери біт 3 векторів 1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932 Біти номер 1-48 використовують для раундового XORу.
Приклад роботи алгоритму Для ключа 00 00 00 00 00 00 00 00 (НЕХ)
та тексту 00 00 00 00 00 00 00 00 (НЕХ)
Результати шифрування відкритого тексту ключем
8C A6 4D E9 C1 B1 23 A7 (НЕХ)
(test vector 8ca64de9c1b123a7)
Детальний приклад
Ключ FEDCBA9876543210 (НЕХ)
Відкритий текст 0123456789ABCDEF (НЕХ)
Результат ED39D950FA74BCC4 (НЕХ)
Слабкі ключі
Слабкими ключами називається ключі k такі, що , де x — 64-бітний блок.
Відомі 4 слабких ключа, вони наведені в таблиці 9. Для кожного слабкого ключа існує нерухомі точки, тобто, таких 64-бітових блоків х, для яких .
+ Таблиця 9. DES-Слабкі ключі Слабкі ключі (hexadecimal) 0101-0101-0101-0101 FEFE-FEFE-FEFE-FEFE 1F1F-1F1F-0E0E-0E0E E0E0-E0E0-F1F1-F1F1 позначає вектор, що складається з 28 нульових бітів.
Наприклад, для ключа
FE FE FE FE FE FE FE FE (НЕХ)
та тексту
01 23 45 67 89 AB CD EF (НЕХ)
Результати шифрування відкритого тексту ключем
6D CE 0D C9 00 65 56 A3 (НЕХ)
далі, для ключа
FE FE FE FE FE FE FE FE (НЕХ)
та тексту
6D CE 0D C9 00 65 56 A3 (НЕХ)
Результати шифрування відкритого тексту ключем
01 23 45 67 89 AB CD EF (НЕХ)
Захист та криптоаналіз Оскільки DES — порівняно старий криптоалгоритм, існує багато публікацій щодо його криптоаналізу. Дуже ґрунтовну оцінку безпеки DES дано Брюсом Шнаєром, який у своїй відомій книзі «Прикладна криптографія» розбирає та впорядковує велику кількість публікацій щодо криптоаналізу DES.
Тепер DES вважається нестійким, оскільки: Розмір ключа — 56 бітів — замалий, тому існує реальна загроза пошуку ключа лобовою атакою (послідовним перебором). DES нестійкий до лінійного криптоаналізу (тобто лінійна атака дозволяє знайти ключ DES швидше, ніж послідовний перебір).
В той же час, повний 16-раундовий DES стійкий до диференційного криптоаналізу.
Через високу розповсюдженість DES було запропоновано багато ідей щодо підвищення його безпеки, зокрема, замінити S-блоки DES новими, стійкими до лінійної атаки. Однак, широке практичне застосування жодна з видозмінених версій DES не набула. Винятком є потрійний DES, однак, це не видозміна алгоритму, а лише особливий режим шифрування звичайним DES.
Посилання Програмна реалізація DES