1.2.Опис алгоритму.
DES є блоковим шифром - дані шифруються блоками по 64 біти - 64 бітний блок явного тексту є на одному кінці алгоритму, а 64-бітний блок шифрограми отримується на другому кінці алгоритму. Крім того, як під час шифрування, так і під час дешифрування використовується один і той самий алгоритм (за винятком дещо іншого шляху утворення робочих ключів).
Ключ має довжину 56 біт (як правило, в джерельному вигляді ключ має довжину 64 біти, де кожний 8-й біт є бітом паритету, крім того, ці контрольні біти можуть бути винесені в останній байт ключа). Ключем може бути довільна 64-бітна комбінація, яка може бути змінена в любий момент часу. Частина цих комбінацій вважається слабкими ключами, оскільки може бути легко визначена. Безпечність алгоритму базується на безпечності ключа.
На найнижчому рівні алгоритм є ніщо інше, ніж поєднання двох підставних технік шифрування: перемішування і підстановки. Цикл алгоритму, з яких і складається DES є комбінацією цих технік, коли в якості об”єктів перемішування виступають біти тексту, ключа і блоків підстановок.
В DES використовується 16 циклів , вихідними даними для кожного з них 64 є біти текту явного (у першому циклі) чи 64 біти шифрограми (у всіх наступних), ключ і блоки підстановок.
Алгоритм використовує лише стандартні елементарні логічні операції (зсув, сума по модулю два) на числах довжиною 64 біти, що значно полегшує програмування алгоритму і прискорює його роботу. Циклічний характер алгоритму в сумі з ідеальною здатністю до запрограмовування робить алгоритм швидким і легким до розуміння.
1.3.Компоненти алгоритму des.
1. Текст явний.
Це 64-бітні блоки явного тексту (чи будь якої іншої цифрової інформації), який необхідно піддати процедурі шифрування.
2.Початковий вектор перестановок.
Це послідовність чисел, згідно з якою перед початком шифрування біти явного тексту переставляються місцями з метою підготування останнього до процедури шифрування.
3. 56-бітний ключ, званий головним ключем, біти якого в різних комбінаціях використовуються алгоритмом для сумування по модулю два з бітами тексту явного (шифрограми).
4.16 робочих 48-бітних ключів, утворених з головного ключа, які сумуються по модулю два в кожному циклі з бітами тексту явного (шифрограми) і використовуються лише один раз.
5. Таблиця перестановки з розширенням, яка з 32-бітної половини тексту явного (шифрограми) дозволяє отримати 48-бітну послідовність.
6. S-блоки - набори 4-бітних послідовностей, які певним чином використовуються для заміни 6-бітних послідовностей 4-бітними з метою отримання 32-бітної послідовності з 48- бітної.
7. P-блок - вектор перестановок, аналогічний за призначенням і принципом дії вектору початкових перестановок, з тою різницею, що працює на 32-ох бітах.
8. Вектор кінцевої перестановки - аналог вектора початкової перестановки.
9. Вектор перестановок головного ключа.
10. Таблиця ротації головного ключа.
11.Таблиця компресії головного ключа.
1.4.Робота алгоритму.
Розглянемо поетапно роботу алгоритму алгоритму DES.
Блок-схема алгоритму DES наведена на рисунку 1.
Етап 1.
Підготовка даних до шифрування.
На цьому етапі біти 64-бітного блоку даних переставляються місцями згідно з початковим вектором перестановок. Результатом є новий 64-бітний блок, який в свою чергу розбивається на дві 32-бітні половини - ліву і праву.
Початковий вектор перестановок у класичному DES записується у вигляді таблиці (дивись таблицю 1) , яка при використанні зчитується послідовоно зліва направо і зверху вниз. Таким чином, згідно до наведеного вектору перестановок, першим буде стояти 58 біт, другим - 50, третім - 42 і так дальше.
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 |
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 |
Таблиця 1. Вектор початкової перестановки.
Слід зауважити, що впливу на безпеку алгоритиму ні початкова, ні кінцева перестановки не здійснюють і з огляду на те, що така операція важко оптимізується в часі з точки зору апаратно-програмної реалізації, в багатьох наступних версіях DES вони не вводяться. Але в цьому випадку слід сказати, що такі модифікацї алгоритму не повинні називатись DES, оскільки в ньому ці вектори перестановок запатентовані.
Етап 2.
Підготовка ключа до шифрування.
Як уже було сказано, початково існує 64 біти ключа, 8 з яких є бітами парності. З цих 64-ох бітів, відкидаючи біти парності, формується 56-бітний головний ключ за допомогою вектора перестановок головного ключа.
Вектор перестановок головного ключа записується у вигляді таблиці (дивись таблицю 2) , яка при використанні зчитується послідовно зліва направо і зверху вниз. Результатом роботи вектора перстановк є сформований 56-бітний головний ключ.
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 |
Таблиця 2. Вектор перестановок головного ключа.
Наступним кроком цього етапу є розділ головного ключа на дві половини по 28 біт.
Тепер для кожного з 16-ти циклів на основі головного ключа за допомогою таблиці ротації головного ключа формуються 16 робочих ключів.
Здійснюється це наступним чином:
Кожна половина (28 біт) згідно з таблицею ротації головного ключа зсувається вліво на кількість біт, вказану в таблиці. Після кожного такого зсуву за допомогою таблиці компресії головного ключа з новоутвореної 56-бітної послідовності вибирають 48 біт, які в сумі і становлять робочий ключ циклу.
Приклад таблиці ротації головного ключа наведено в таблиці 3. Особливістю цієї таблиці є те, що сума зсувів - тобто сумарний зсув - після формування 16-ти ключів становить 28, тобто після формування робочих ключів головний ключ автоматично приводиться до початкового вигляду і знову готовий до використання.
Цикл |
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 |
Таблиця 3. Таблиця ротації головного ключа.
Тепер необхідно з 56-ти біт головного ключа вибрати 48 біт для робочого ключа. Ця операція виконується за допомогою таблиці компресії головного ключа.
Приклад таблиці компресії головного ключа наведений в таблиці 4. Згідно до неї, першим бітом робочого ключа буде 14-тий біт модифікованого головного ключа, другим - 17-тий, третім - 11-тий і так дальше.
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 |
Таблиця 4. Таблиця компресії головного ключа.
Результатом цього етапу є отримання 16-ти 48-бітних робочих ключів, кожен з яких буде використаний лише раз.
Графічно підготовку робочих ключів можна зобразити наступним чином (Рис.2)
Етап 3.
Цикл алгоритму DES.
Рис.1.
Блок-схема алгоритму DES.
Вхідними даними цього етапу є:
32-бітні ліва і права частини бітового ланцюжку даних, 48-бітний робочий ключ.
Рис. 2. Формування робочих ключів.
Тобто, як бачимо, існує різниця в довжині між 32-бітними даними і 48-бітним ключем.
Алгоритм передбачає наступні дії:
права 32-бітна половина даних, над якою власне і будуть проводитись майме всі операції циклу за допомогою таблиці перестановок з розширенням (Е-таблиці) переписується до вигляду 48-бітного ланцюжка. Приклад таблиці перестановок з розширенням наведений в таблиці 5.
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 |
Таблиця 5. Таблиця перестановки з розширенням.
Як бачимо, збільшення кількості бітів відбувається за рахунок використання деяких бітів двічі. Для наведеної як приклад Е-таблиці графічне преставлення формування 48-бітного ланцюжка даних виглядає наступним чином:
Рис. 3. Графічне преставлення формування 48-бітного ланцюжка даних за допомогою Е-таблиці.
Метою такої операції є :
отримання ланцюжка бітів, рівного з робочим ключем для здійснення операції сума по модулю два;
подовження даних для наступної компресії за допомогою S-блоків.
Але жодна з них не є метою криптографічною. Криптографічним в даному випадку можна вважати ефект поширення за рахунок повторного використання впливу деяких бітів на сусідні біти після виконання операції сума по модулю два. Такий ефект має назву лавинного, оскільки на наступних циклах цей вплив розширюється дальше, і цим самим здійснюється реалізація мети шифрування: максимальний вплив кожного біту тексту явного і кожного біту ключа на кожний біт вихідної шифрограми.
Після отримання 48 біт даних вони сумуються по модулю 2 з 48-бітним робочим ключем циклу. Результат сумування по модулю два піддається операції підстановки.
Підстановка здійснюється за допомогої блоків підстановки, тобто S-блоків.
Ланцюжок довжиною 48 бітів розбивається на 8 6-бітних послідовностей, замість кожної з яких за допомогою S-блоків підставляються 4 біти.
S-блоки являють собою таблиці, приклад яких наведений в таблиці 6. Треба сказати, що існує 8 S-блоків - по одному на кожну 6-бітну послідовність.
S-блок 1
|
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 |
S-блок 2
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
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 |
S-блок 3
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
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 |
S-блок 4
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
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 |
S-блок 5
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
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 |
S-блок 6
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
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 |
S-блок 7
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
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 |
S-блок 8
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
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 |
Таблиця 6. S-блоки.
Кожний S-блок містить 4 рядки і 16 стовпчиків. Елементом S-блоку є 4-бітне число. Номер рядка і номер стовпчика в S-блоку вказує на число (4-бітна послідовність), яке необхідно підставити як результат.
Вибір елемента S-блоку здійснюється наступним чином:
Нехай 6-бітна послідовність записується так: б1,б2,б3,б4,б5,б6. Тоді біти б1 і б6 становлять собою двохбітну послідовність, яка є номером рядка S-блоку. Біти б2,б3,б4,б5 - 4-бітна комбінація, яка вказує на один з 16-ти стовпчиків S-блоку. На перетині рядка і стовпчика, на які вказує 6-бітна послідовність, в S-блоці стоїть 4-бітне число, яке і підставляється замість 6 біт.
Описаний процес є “серцем” алгортму. Всі інші операції алгоритму є лінійними і тому легкими для аналізу. S-блок реалізує нелінійну операцію і тому вносить найбільший вклад в криптостійкість алгоритму.
Результатом підстановок є 8 4-бітних послідовностей, які в сумі становлять 32-ох бітовий результуючий ланцюжок.
Наступним кроком є застосування до цього 32-бітного ланцюжка Р-блока перестановок, дія якого є аналогічною до всіх інших таблиць перестановок. Приклад Р-блоку наведений в таблиці 7. Згідно до цієї таблиці першим буде 16-тий біт, другим - 7 і так дальше. Слід зауважити, що у таких перестановках жоден біт не використовується двічі і жоден біт не втрачається.
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 |
Таблиця 7. Р-блок.
Наприкінці цього етапу результат перестановки згідно з Р-блоком сумується по модулю два з лівою частиною даних (шифрограми) і частини міняються місцями.
Етап 4.
Кінцева перестановка.
Кінцева перестановка є аналогічною до початкової і здійснюється згідно вектора кінцевої перестановки, приклад якого наведений в таблиці 8 і правила користування аналогічні до правил користування вектором початкової перестановки.
Зауважимо, що після закінчення останнього циклу алгоритму DES не виконується перестановка лівої і правої частин шифрограми. Замість цього отриманий поєднанням лівої і правої частин 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 |
Таблиця 2.8. Вектор кінцевих перестановок.