Data Encryption Standard
DES (англ. Data Encryption Standard) — це симетричний алгоритм шифрування певних даних, стандарт шифрування прийнятий урядом США із 1976 до кінця 1990-х, з часом набув міжнародного застосування. Ще з часу свого розроблення алгоритм викликав неоднозначні відгуки. Оскільки DES містив засекречені елементи своєї структури, породжувались побоювання щодо можливості контролю з боку Національного Агентства Безпеки США (англ. National Security Agency). Алгоритм піддавався критиці за малу довжину ключа, що, врешті, після бурхливих обговорень та контролю академічної громадськості, не завадило йому стати загальноприйнятим стандартом. DES дав поштовх сучасним уявленням про блочні алгоритми шифрування та криптоаналіз.
Розробники | IBM |
---|---|
Уперше оприлюднений | 1975 р. |
Раундів | 16 |
Тип | Мережа Фейстеля |
Зараз DES вважається ненадійним в основному через малу довжину ключа (56 біт) та розмір блоку (64 біти). У 1999 ключ DES було публічно дешифровано за 22 години 15 хвилин. Вважається, що алгоритм достатньо надійний для застосування у модифікації 3-DES, хоча існують розроблені теоретичні атаки. DES поступово витісняється алгоритмом AES, що з 2002 року є стандартом США.
Щиро кажучи, існує різниця між стандартом DES (Data Encryption Standard) та алгоритмом DEA (Data Encryption Algorithm).
Історія DES
ред.Історія розробки DES сягає початку 1970-х і почалась за ініціативи Національного Бюро Стандартів США (англ. National Bureau of Standards) — тепер, Національний Інститут Стандартів і Технологій (англ. National Institute of Standards and Technology) — для забезпечення засекречених урядових даних. 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 DES cracker (Deep Crack) дешифрує ключ DES за 56 годин. |
січень | 1999 | Разом Deep Crack та 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-бітний блок даних, які переставляються згідно з таблицею:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
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 |
33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
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 |
16 раундів
ред.Далі 16 разів повторюються наступні операції:
Функція розширення блоку
ред.Функція Е розширює 32-бітовий вектор до 48-бітового вектора шляхом повторення деяких біт з згідно з таблицею:
_ | 1 | 2 | 3 | 4 | _ | _ | 5 | 6 | 7 | 8 | _ | _ | 9 | 10 | 11 | 12 | _ | _ | 13 | 14 | 15 | 16 | _ | _ | 17 | 18 | 19 | 20 | _ | _ | 21 | 22 | 23 | 24 | _ | _ | 25 | 26 | 27 | 28 | _ | _ | 29 | 30 | 31 | 32 | _ |
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 |
Перший рядок — номери вхідних біт, другий рядок — вихідні біти. Повторення номерів, означає повторення біт.
Додавання раундового ключа
ред.Блок 48 біт XOR'иться з раундовим ключем .
Таблиці підстановки
ред.S-блоки мають вигляд:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 | |
0 | 15 | 1 | 8 | 14 | 6 | 11 | 3 | 4 | 9 | 7 | 2 | 13 | 12 | 0 | 5 | 10 | |
1 | 3 | 13 | 4 | 7 | 15 | 2 | 8 | 14 | 12 | 0 | 1 | 10 | 6 | 9 | 11 | 5 | |
2 | 0 | 14 | 7 | 11 | 10 | 4 | 13 | 1 | 5 | 8 | 12 | 6 | 9 | 3 | 2 | 15 | |
3 | 13 | 8 | 10 | 1 | 3 | 15 | 4 | 2 | 11 | 6 | 7 | 12 | 0 | 5 | 14 | 9 | |
0 | 10 | 0 | 9 | 14 | 6 | 3 | 15 | 5 | 1 | 13 | 12 | 7 | 11 | 4 | 2 | 8 | |
1 | 13 | 7 | 0 | 9 | 3 | 4 | 6 | 10 | 2 | 8 | 5 | 14 | 12 | 11 | 15 | 1 | |
2 | 13 | 6 | 4 | 9 | 8 | 15 | 3 | 0 | 11 | 1 | 2 | 12 | 5 | 10 | 14 | 7 | |
3 | 1 | 10 | 13 | 0 | 6 | 9 | 8 | 7 | 4 | 15 | 14 | 3 | 11 | 5 | 2 | 12 | |
0 | 7 | 13 | 14 | 3 | 0 | 6 | 9 | 10 | 1 | 2 | 8 | 5 | 11 | 12 | 4 | 15 | |
1 | 13 | 8 | 11 | 5 | 6 | 15 | 0 | 3 | 4 | 7 | 2 | 12 | 1 | 10 | 14 | 9 | |
2 | 10 | 6 | 9 | 0 | 12 | 11 | 7 | 13 | 15 | 1 | 3 | 14 | 5 | 2 | 8 | 4 | |
3 | 3 | 15 | 0 | 6 | 10 | 1 | 13 | 8 | 9 | 4 | 5 | 11 | 12 | 7 | 2 | 14 | |
0 | 2 | 12 | 4 | 1 | 7 | 10 | 11 | 6 | 8 | 5 | 3 | 15 | 13 | 0 | 14 | 9 | |
1 | 14 | 11 | 2 | 12 | 4 | 7 | 13 | 1 | 5 | 0 | 15 | 10 | 3 | 9 | 8 | 6 | |
2 | 4 | 2 | 1 | 11 | 10 | 13 | 7 | 8 | 15 | 9 | 12 | 5 | 6 | 3 | 0 | 14 | |
3 | 11 | 8 | 12 | 7 | 1 | 14 | 2 | 13 | 6 | 15 | 0 | 9 | 10 | 4 | 5 | 3 | |
0 | 12 | 1 | 10 | 15 | 9 | 2 | 6 | 8 | 0 | 13 | 3 | 4 | 14 | 7 | 5 | 11 | |
1 | 10 | 15 | 4 | 2 | 7 | 12 | 9 | 5 | 6 | 1 | 13 | 14 | 0 | 11 | 3 | 8 | |
2 | 9 | 14 | 15 | 5 | 2 | 8 | 12 | 3 | 7 | 0 | 4 | 10 | 1 | 13 | 11 | 6 | |
3 | 4 | 3 | 2 | 12 | 9 | 5 | 15 | 10 | 11 | 14 | 1 | 7 | 6 | 0 | 8 | 13 | |
0 | 4 | 11 | 2 | 14 | 15 | 0 | 8 | 13 | 3 | 12 | 9 | 7 | 5 | 10 | 6 | 1 | |
1 | 13 | 0 | 11 | 7 | 4 | 9 | 1 | 10 | 14 | 3 | 5 | 12 | 2 | 15 | 8 | 6 | |
2 | 1 | 4 | 11 | 13 | 12 | 3 | 7 | 14 | 10 | 15 | 6 | 8 | 0 | 5 | 9 | 2 | |
3 | 6 | 11 | 13 | 8 | 1 | 4 | 10 | 7 | 9 | 5 | 0 | 15 | 14 | 2 | 3 | 12 | |
0 | 13 | 2 | 8 | 4 | 6 | 15 | 11 | 1 | 10 | 9 | 3 | 14 | 5 | 0 | 12 | 7 | |
1 | 1 | 15 | 13 | 8 | 10 | 3 | 7 | 4 | 12 | 5 | 6 | 11 | 0 | 14 | 9 | 2 | |
2 | 7 | 11 | 4 | 1 | 9 | 12 | 14 | 2 | 0 | 6 | 10 | 13 | 15 | 3 | 5 | 8 | |
3 | 2 | 1 | 14 | 7 | 4 | 10 | 8 | 13 | 15 | 12 | 9 | 0 | 3 | 5 | 6 | 11 |
«Розширені» біти використовуються для визначення номера 0-1-2-3 таблиці (ліва колонка).
Перестановка
ред.Далі виконується перестановка
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
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 |
За формулою отримуємо значення .
Кінцева перестановка
ред.Після 16-ти раундів застосовуюєть перестановка біт:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 |
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 |
Вхідний перший біт ставить на місце номер 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.
57 | 49 | 41 | 33 | 25 | 17 | 9 | 1 | 58 | 50 | 42 | 34 | 26 | 18 | 10 | 2 | 59 | 51 | 43 | 35 | 27 | 19 | 11 | 3 | 60 | 52 | 44 | 36 | |
63 | 55 | 47 | 39 | 31 | 23 | 15 | 7 | 62 | 54 | 46 | 38 | 30 | 22 | 14 | 6 | 61 | 53 | 45 | 37 | 29 | 21 | 13 | 5 | 28 | 20 | 12 | 4 |
Ця перестановка визначається двома блоками і по 28 біт кожен. Перші 3 біта є біти 57, 49, 41 розширеного ключа. А перші три біта є біти 63, 55, 47 розширеного ключа.
Для раундів i = 1,2,3 … отримують з одним або двома лівими циклічними зрушеннями згідно з таблицею:
i-й раунд | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Число зсувів | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
Ключ , i = 1, … 16 складається з 48 біт, вибраних з бітів вектора (56 біт) згідно з приведеною нижче таблицею. Перший і другий біти є біти 14, 17 вектора
i-й біт раундового ключа | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
номери біт 3 векторів | 14 | 17 | 11 | 24 | 1 | 5 | 3 | 28 | 15 | 6 | 21 | 10 | 23 | 19 | 12 | 4 | 26 | 8 | 16 | 7 | 27 | 20 | 13 | 2 | 41 | 52 | 31 | 37 | 47 | 55 | 30 | 40 | 51 | 45 | 33 | 48 | 44 | 49 | 39 | 56 | 34 | 53 | 46 | 42 | 50 | 36 | 29 | 32 |
Біти номер 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-бітових блоків х, для яких .
Слабкі ключі (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.
Посилання
ред.
Це незавершена стаття про програмування. Ви можете допомогти проєкту, виправивши або дописавши її. |