Стандарт шифрування DES

Лабораторна робота 2

Стандарт шифрування DES

Мета роботи – опанувати методику шифрування алгоритмами збивання. На прикладі DES здійснити шифрування. Усвідомити сильні сторони в застосуванні даного методу шифрування.

Теоретичні відомості

Алгоритм DES (data encryption standard) був державним стандартом США і здійснює шифрування 64-бітових блоків даних за допомогою 64-бітового ключа. Процес шифрування полягає в початковій перестановці бітів 64-бітового блоку і 16 циклах шифрування, а розшифрування – 16 циклах розшифрування і у кінцевій перестановці бітів.

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

Підключ – деяка ключова інформація, яка отримується з основного ключа шифрування. На кожному раунді використовується нове значення підключа Ki (довжиною 48 біт), яке обчислюється з початкового 64-бітового ключа K з 8 бітами контролю парності, розташованими в позиціях 8,16,24,32,40,48,56,64. Для вилучення контрольних бітів і підготовки ключа до роботи використовується функція PC1 первісної підготовки ключа. Докладно процес одержання підключей показано на рис 1.1.

Результат перетворення PC1(K) розбивається на дві половини C0 і D0 по 28 біт кожна. Перші чотири рядки матриці PC1 визначають, як вибираються біти послідовності C0, останні чотири рядки – послідовності D0. Для генерації послідовностей не використовуються біти 8,16,24,32,40,48,56 і 64 ключа шифру. Таким чином, у дійсності ключ шифру є 56-бітовим.

Після визначення С0 і D0 рекурсивно визначаються Сi і Di, i = 1, 2,..., 16.

Для цього застосовуються операції циклічного зрушення вліво на один чи два біти в залежності від номера кроку раунду, як показано в таблиці, що приведена в додатку. Ключ Ki, обумовлений на кожнім кроці раунду, є результатом вибору конкретних бітів з 56-бітової послідовності Сi Di, і їхньої перестановки згідно з таблицею PC2, яка наведена в додатку. Іншими словами, ключ Ki=PC2(Ci Di) [17].

Рис. 1.1. Цикл отримання підключів для кожного раунду

Процес шифрування виглядає в такий спосіб. Нехай з файлу вхідного тексту був прочитаний черговий 64-бітовий (8-байтовий) блок T. Цей блок T обробляється за допомогою матриці початкової перестановки IP: біти вхідного блоку (64 біта) переставляються відповідно до матриці IP [2]. Отримана послідовність бітів розділяється на 2 послідовності: L0-ліві старші біти, R0-праві молодші біти, кожна з яких містить 32 біта. Потім виконується ітеративний процес шифрування, що складається з 16 раундів. (рис 1.2) 

Рис 1.2. Структурна схема алгоритму DES

Нехай Ti- результат i-ого раунду: 

Ti=LiRi,(1.1)

де Li – перші 32 біта послідовності, Ri – останні 32 біта послідовності. Тоді результат i-ого раунду описується наступними формулами:

Li=Ri-1, i=1,2,3, …, 16,(1.2)

Ri=Li-1 xor f(Ri-1, Ki), i=1,2,3, …, 16.(1.3)

Функція f називається функцією шифрування. Її аргументами є послідовність Ri-1, одержувана на попередньому кроці раунду, і 48-бітовий підключ Ki, що є результатом перетворень 64-бітового ключа шифру K.

На останньому кроці раунду одержують послідовності R16 і L16, що об’єднуються в 64-бітову послідовність – здійснюється відновлення позицій бітів за допомогою матриці зворотної перестановки IP-1 [17]. Елементи матриць IP і IP-1 зв’язані між собою.

Тепер розглянемо, що ховається під перетворенням, позначеним літерою f. Для обчислення значення функції f використовуються:

функція E (розширення 32 біт до 48);

функція S1,S2, …,S8  (перетворення 6-бітового числа в 4-бітове);

функція P (перестановка бітів у 32-бітовій послідовності).

Приведемо визначення цих функцій і процес шифрування більш докладно.

1. Функція розширення E приймає блок з 32 біт і породжує блок з 48 біт, відповідно до матриці E.

2. Отриманий результат складається по модулю 2 (операція XOR) з поточним значенням ключа Ki і потім розбивається на вісім 6-бітових блоків B1,B2, …,B8... 

3. Далі кожний з цих блоків використовується як номер елемента у блоках S1,S2, …,S8, що мають 4-бітові значення. Нехай на вхід функції Sj надходить 6-бітовий блок Bj=b1b2b3b4b5b6, тоді двохбітове число b1b6 указує номер рядка матриці, а чотирьохбітове число b2b3b4b5 – номер стовпця в наступній таблиці.

Сукупність 6-бітових блоків B1,B2, …,B8 забезпечує вибір чотирьохбітового елемента в кожній з функцій S1,S2, …,S8... У результаті одержуємо S1(B1) S2(B2) … S8(B8), або 32-бітовий блок (оскільки матриці Sj містять 4-бітові елементи).

4. Цей 32-бітовий блок перетвориться за допомогою функції перестановки бітів P. Таким чином, функція шифрування f (Ri-1,Ki)=P (S1 (B1) S2 (B2) … S8 (B8))...

5. Далі випливає додавання по модулю 2 лівого підблока й результату перетворення правого підблока.

Процес розшифровування даних є інверсним стосовно процесу шифрування. Усі дії повинні бути виконані в зворотному порядку. Це означає, що дані, що розшифровуються, спочатку переставляються відповідно до матриці IP-1 ,а потім над послідовністю бітів R16L16 виконуються ті ж дії, що й у процесі шифрування, але в зворотному порядку.

Ітеративний процес розшифрування може бути описаний наступними формулами:

Ri=Li, i=1,2,3, …, 16,(1.4)

Li-1=Ri xor f (Li, Ki), i=1,2,3, …, 16. R16L 16(1.5)

Таким чином, для процесу розшифрування з