Data Encryption Standard

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Алгоритм блочного шифрування
Data Encription Standard Flow Diagram.svg
Назва: DES (Data Encryption Standard), DEA (Data Encryption Algorithm)
Розробник: IBM
Створений: 1975 р.
Опублікований: 1975 р.
Розмір ключа: 56 біт
Розмір блоку: 64 біт
Число раундів: 16
Тип: Мережа Фейстеля

DES (англ. Data Encryption Standard) — це симетричний алгоритм шифрування даних, стандарт шифрування прийнятий урядом США із 1976 до кінця 1990-х, з часом набув міжнародного застосування. Ще з часу свого розроблення алгоритм викликав неоднозначні відгуки. Оскільки DES містив засекречені елементи своєї структури, породжувались побоювання щодо можливості контролю з боку Національного Агенства Безпеки США (англ. National Security Agency). Алгоритм піддавався критиці за малу довжину ключа, що, врешті, після бурних обговорень та контролю академічної громадськості, не завадило йому стати загальноприйнятим стандартом. DES дав поштовх сучасним уявленням про блочні алгоритми шифрування та криптоаналіз.

Зараз DES вважається ненадійним в оCновному через малу довжину ключа (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-бітний блок даних, які переставляються згідно з таблицею:

Початкова перестановка IP
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-бітовий вектор R_{i-1} до 48-бітового вектора E(R_{i-1}) шляхом повторення деяких біт з R_{i-1} згідно з таблицею:

Функція розширення E
_ 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

Перший рядок - номери вхідних біт, другий рядок - вихідні біти. Повторення номерів, означає повторення біт.

Додавання раундового ключа k_i[ред.ред. код]

Блок 48 біт XOR'иться з раундовим ключем k_i.

Таблиці підстановки[ред.ред. код]

S-бокси мають вигляд:

S-бокси S_i, i=1…8
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 S_1
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 S_2
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 S_3
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 S_4
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 S_5
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 S_6
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 S_7
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 S_8
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 таблиці (ліва колонка).

Перестановка[ред.ред. код]

Далі виконується перестановка

Перестановка P
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

XOR лівої і правої частин[ред.ред. код]

За формулою R_i = L_{i-1}\oplus f(R_{i-1},k_i) отримуємо значення R_i.

Кінцева перестановка[ред.ред. код]

Після 16-ти раундів застосовуюєть перестановка біт:

Перестановка IP^{-1}
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_i)[ред.ред. код]

Ключі  k_i отримують з початкового ключа 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  C_0
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  D_0

Ця перестановка визначається двома блоками  C_0 і  D_0 по 28 біт кожен. Перші 3 біта  C_0 є біти 57, 49, 41 розширеного ключа. А перші три біта  D_0 є біти 63, 55, 47 розширеного ключа.

Для раундів  C_i, D_i i = 1,2,3 ... отримують з  C_ {i-1}, D_ {i-1} одним або двома лівими циклічними зрушеннями згідно з таблицею:

Циклічний зсув
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

Ключ  k_i , i = 1, ... 16 складається з 48 біт, вибраних з бітів вектора  C_i D_i (56 біт) згідно з приведеною нижче таблицею. Перший і другий біти  k_i є біти 14, 17 вектора  C_i D_i

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 векторів  C_i D_i 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 такі, що  DES_k (DES_k (x)) = x , де x - 64-бітний блок.

Відомі 4 слабких ключа, вони наведені в таблиці 9. Для кожного слабкого ключа існує  2 ^ {32} нерухомі точки, тобто, таких 64-бітових блоків х, для яких  DES_k (x) = x .

Таблиця 9. DES-Слабкі ключі
Слабкі ключі (hexadecimal)  C_0  D_0
0101-0101-0101-0101  [0] ^ {28}  [0] ^ {28}
FEFE-FEFE-FEFE-FEFE  [1] ^ {28}  [1] ^ {28}
1F1F-1F1F-0E0E-0E0E  [0] ^ {28}  [1] ^ {28}
E0E0-E0E0-F1F1-F1F1  [1] ^ {28}  [0] ^ {28}

 [0] ^ {28} позначає вектор, що складається з 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 вважається нестійким, оскільки:

  1. Розмір ключа — 56 бітів — замалий, тому існує реальна загроза пошуку ключа лобовою атакою (послідовним перебором).
  2. DES нестійкий до лінійного криптоаналізу (тобто лінійна атака дозволяє знайти ключ DES швидше, ніж послідовний перебір).

В той же час, повний 16-раундовий DES стійкий до диференційного криптоаналізу.

Через високу розповсюдженість DES було запропоновано багато ідей щодо підвищення його безпеки, зокрема, замінити S-блоки DES новими, стійкими до лінійної атаки. Однак, широке практичне застосування жодна з видозмінених версій DES не набула. Винятком є потрійний DES, однак, це не видозміна алгоритму, а лише особливий режим шифрування звичайним DES.

Посилання[ред.ред. код]

Програмна реалізація DES