ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.05.2024
Просмотров: 20
Скачиваний: 0
Практична робота № 8
Тема: Блочні шифри. Алгоритм DES
Мета: Навчитися використовувати алгоритм DES при шифруванні тексту.
Теоретичні відомості
Американський стандарт криптографічного захисту даних (Data Encryption Standard), прийнятий в 1978 році є типовим представником сімейства блочних шифрів. Цей шифр допускає ефективну апаратну та програмну реалізації, причому можливо досягнення швидкостей до декількох мегабайтів за секунду.
Алгоритм DES виконує шифрування 64-бітних блоків даних за допомогою 56 бітного ключа. Дешифрування в DES є оберненою операцією шифруванню і виконується шляхом повторення операцій шифрування в зворотній послідовності.
Процес шифрування полягає в початковій перестановці 64 бітів вхідного блоку, шістнадцяти циклах шифрування та зворотній перестановці бітів (рис. 1)
Необхідно звернути увагу на те, що всі таблиці алгоритму DES є стандартними і повинні включатися в реалізацію алгоритму в незмінному вигляді. Усі перестановки і коди в таблицях підібрані так, щоб зробити максимально важким процес зламування шляхом підбору ключа.
Рисунок 1 – Загальна схема процесу шифрування в алгоритмі DES
Розглянемо
алгоритм докладніше. Припустимо, з файлу
зчитано 64-бітний блок
,
який перетворюється за допомогою
початкової перестановки IP
(рис. 2)
в 64-бітний блок
.
Рисунок
2
– Матриця початкової перестановки
Після IP-перестановки
16 разів повторюється процедура шифрування
блока
за допомогою функції
.
Позначимо
– результат i-ї
ітерації;
– перші (ліві) 32
біти блоку
,
;
– останні (праві)
32 біти блоку
,
.
Таким чином,
.
Тоді результатом i-ї операції буде:
,
,
де
– операція додавання
за модулем 2;
– i-те
перетворення ключа шифрування
.
Функція
виконує операції над значенням
(результатом минулої операції) та
поточним значенням 48-бітного ключа
(з відокремленням зайвих бітів). До речі,
після 16-ї ітерації ліва і права половини
блока не міняються місцями (рис. 3).
По закінченні шифрування виконується
відновлення позицій бітів за допомогою
матриці перестановок
(рис. 4).
Розглянемо
докладніше функцію
.
Крок
1 На кожній ітерації
масив
розширюється до 48 бітів за допомогою
таблиці розподілення бітів
.
Блок
розбивається на вісім блоків по 4 біти
(рис. 5).
Рисунок 3 – Загальна схема алгоритму шифрування DES
Шляхом копіювання
крайніх елементів вісім 4-бітних блоки
перетворюються у вісім 6-бітних блоків
(рис. 6). Отриманий блок
має
48 бітів.
-
Рисунок 4 – Матриця зворотної перестановки
Рисунок 5 – Розбиття
на вісім блоків
Крок 2 Блок
порозрядно сумують за модулем 2 з
поточним значенням ключа
, а потім розбивають на вісім 6-бітних
блоки
,
тобто
.
Крок 3
Кожен
блок (
)
подається на вхід підстановки S-бокс
(рис 7). Індекс
вказує, який з масивів S-боксу
використовувати. Застосувавши операцію
вибору до кожного із блоків
,
одержимо 32-бітний потік.
Рисунок 6 – Таблиця
розподілення бітів
Відзначимо, що
вибір елемента в масиві
здійснюється досить оригінальним
способом. Нехай на вхід подається
6-бітний блок
,
дві крайні позиції
інтерпретуються як двійкове подання
цілих чисел з набору {0, 1, 2, 3}.
|
|
Номер стовпця |
|
||||||||||||||||
|
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 |
S1 |
|
1 |
0 |
15 |
7 |
4 |
14 |
2 |
13 |
1 |
10 |
6 |
12 |
11 |
9 |
5 |
3 |
8 |
||
|
2 |
4 |
1 |
14 |
89 |
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 |
S2 |
|
|
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 |
S3 |
|
|
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 |
S4 |
|
|
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 |
S5 |
|
|
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 |
S6 |
|
|
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 |
S7 |
|
|
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 |
S8 |
|
|
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 |
||
Рисунок 7 – S-бокс
Ці
числа визначають номер рядка (від 0 до
3) масиву
.
Чотири біти, що залишилися,
інтерпретуються як двійкове подання
цілих чисел з набору {0, 1, 2, … , 15} і
використовуються для визначення стовпця
(від 0 до 15) у масиві
.
Таким чином, вхідний
блок, наприклад,
,
відповідає десятковому числу 9, розміщеному
в другому рядку та в третьому стовпці
масиву
, Число 9 у двійковому поданні являє
собою 4-бітний блок (1001).
У результаті
застосувавши до кожного з блоків
( 
)
операцію вибору в S-боксі,
одержимо 32-бітний блок
.
Крок 4
Отриманий блок
перетворюється за допомогою матриці
перестановки
(рис. 8).
Рисунок 8
– Матриця перестановки
Таким чином,
.
Обчислення значень ключів
Ще раз відзначимо,
що на кожній ітерації використовується
нове значення ключа
,
яке обчислюється із початкового значення
ключа
.
Ключ K –
64-бітний блок з вісьмома бітами контролю
парності, що розміщені в позиціях 8, 16,
24, 32, 40, 48, 56, 64.
Для видалення
контрольних бітів і підготовки ключа
до роботи використовується матриця
(рис. 9).
Рисунок 9 – Матриця попередньої
підготовки ключа
Результат
перетворення
розбивається на дві половини
та
по 28 бітів кожна. Після цього блоки
та
на кожній ітерації послідовно зміщуються
вліво. Нехай
та
позначають значення, які отримані в
результаті i-ї
операції:
де
– i-й
елемент матриці здвигу
(рис. 10).
|
і |
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 |
