Data Encryption Standard

Історія розробки DES сягає початку 1970-х і почалась за ініціативи Національного Бюро Стандартів США (англ. National Bureau of Standards) — тепер, Національний Інститут Стандартів і Технологій (англ. National Institute of Standards and Technology) — для забезпечення засекречених урядових даних. 15 травня 1973, після консультування із Національним Бюром Безпеки США, НБС оголосило конкурс на розробку алгоритму шифрування який би відповідав поставленим строгим архітектурним вимогам, однак, таких пропозицій не надійшло. Лише на другий конкурс 27 серпня 1974 IBM подала розробку яка задовільняла поставленим вимогам — алгоритм, розроблений в період 1973–1974, в основу якого був покладений шифр Хорста Фейстеля Люцифер.

DES є блочним шифром - дані шифруються блоками по 64 біти - 64 бітний блок явного тексту подається на вхід алгоритму, а 64-бітний блок шифрограми отримується в результаті роботи алгоритму. Крім того, як під час шифрування, так і під час дешифрування використовується один і той самий алгоритм (за винятком дещо іншого шляху утворення робочих ключів).

Ключ має довжину 56 біт (як правило, в джерельному вигляді ключ має довжину 64 біти, де кожний 8-й біт є бітом паритету, крім того, ці контрольні біти можуть бути винесені в останній байт ключа). Ключем може бути довільна 64-бітна комбінація, яка може бути змінена у будь-який момент часу. Частина цих комбінацій вважається слабкими ключами, оскільки може бути легко визначена. Безпечність алгоритму базується на безпечності ключа.

На найнижчому рівні алгоритм є ніщо інше, ніж поєднання двох базовних технік шифрування: перемішування і підстановки. Цикл алгоритму, з яких і складається DES є комбінацією цих технік, коли як об'єкти перемішування виступають біти тексту, ключа і блоків підстановок.

Таблиці підстановки

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

S-блок ${\displaystyle 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	${\displaystyle 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	${\displaystyle 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	${\displaystyle 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	${\displaystyle 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	${\displaystyle 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	${\displaystyle 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	${\displaystyle 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	${\displaystyle 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 таблиці (ліва колонка).

Кінцева перестановка

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

Перестановка ${\displaystyle 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 біти, що значно полегшує програмування алгоритму і прискорює його роботу у інтегральних мікросхемах. Циклічний характер алгоритму в сумі з ідеальною здатністю до запрограмовування робить алгоритм швидким і легким до розуміння.

Ключі ${\displaystyle 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	${\displaystyle 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	${\displaystyle D_{0}}$

Ця перестановка визначається двома блоками ${\displaystyle C_{0}}$ і ${\displaystyle D_{0}}$ по 28 біт кожен. Перші 3 біта ${\displaystyle C_{0}}$ є біти 57, 49, 41 розширеного ключа. А перші три біта ${\displaystyle D_{0}}$ є біти 63, 55, 47 розширеного ключа.

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

Ключ ${\displaystyle k_{i}}$, i = 1, ... 16 складається з 48 біт, вибраних з бітів вектора ${\displaystyle C_{i}D_{i}}$ (56 біт) згідно з приведеною нижче таблицею. Перший і другий біти ${\displaystyle k_{i}}$ є біти 14, 17 вектора ${\displaystyle 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 векторів ${\displaystyle 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 такі, що ${\displaystyle DES_{k}(DES_{k}(x))=x}$, де x - 64-бітний блок.

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

Таблиця 9. DES-Слабкі ключі

Слабкі ключі (hexadecimal)	${\displaystyle C_{0}}$	${\displaystyle D_{0}}$
0101-0101-0101-0101	${\displaystyle [0]^{28}}$	${\displaystyle [0]^{28}}$
FEFE-FEFE-FEFE-FEFE	${\displaystyle [1]^{28}}$	${\displaystyle [1]^{28}}$
1F1F-1F1F-0E0E-0E0E	${\displaystyle [0]^{28}}$	${\displaystyle [1]^{28}}$
E0E0-E0E0-F1F1-F1F1	${\displaystyle [1]^{28}}$	${\displaystyle [0]^{28}}$

${\displaystyle [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