Продовження таблиці 3.5
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| S5 | ||||||||||||||||
| 0 1 2 3 | 2 | 12 | 14 | 1 | 7 | 10 | 11 | 6 | 8 | 5 | 3 | 15 | 13 | 0 | 14 | 9 |
| 14 | 11 | 2 | 12 | 4 | 7 | 13 | 1 | 5 | 0 | 15 | 10 | 3 | 9 | 8 | 6 | |
| 4 | 2 | 1 | 11 | 10 | 13 | 7 | 8 | 15 | 9 | 12 | 5 | 6 | 3 | 0 | 14 | |
| 11 | 8 | 12 | 7 | 1 | 14 | 2 | 13 | 6 | 15 | 0 | 9 | 10 | 4 | 5 | 3 | |
| S6 | ||||||||||||||||
| 0 1 2 3 | 12 | 1 | 10 | 15 | 9 | 2 | 6 | 8 | 0 | 13 | 3 | 4 | 14 | 7 | 5 | 11 |
| 10 | 15 | 4 | 2 | 7 | 12 | 9 | 5 | 6 | 1 | 13 | 14 | 0 | 11 | 3 | 8 | |
| 9 | 14 | 15 | 5 | 2 | 8 | 12 | 3 | 7 | 0 | 4 | 10 | 1 | 13 | 11 | 6 | |
| 4 | 3 | 2 | 12 | 9 | 5 | 15 | 10 | 11 | 14 | 1 | 7 | 6 | 0 | 8 | 13 | |
| S7 | ||||||||||||||||
| 0 1 2 3 | 4 | 11 | 2 | 14 | 15 | 0 | 8 | 13 | 3 | 12 | 9 | 7 | 5 | 10 | 6 | 1 |
| 13 | 0 | 11 | 7 | 4 | 9 | 1 | 10 | 14 | 3 | 5 | 12 | 2 | 15 | 8 | 6 | |
| 1 | 4 | 11 | 13 | 12 | 3 | 7 | 14 | 10 | 15 | 6 | 8 | 0 | 5 | 9 | 2 | |
| 6 | 11 | 13 | 8 | 1 | 4 | 10 | 7 | 9 | 5 | 0 | 15 | 14 | 2 | 3 | 12 | |
| S8 | ||||||||||||||||
| 0 1 2 3 | 13 | 2 | 8 | 4 | 6 | 15 | 11 | 1 | 10 | 9 | 3 | 14 | 5 | 0 | 12 | 7 |
| 1 | 15 | 13 | 8 | 10 | 3 | 7 | 4 | 12 | 5 | 6 | 11 | 0 | 14 | 9 | 2 | |
| 7 | 11 | 4 | 1 | 9 | 12 | 14 | 2 | 0 | 6 | 10 | 13 | 15 | 3 | 5 | 8 | |
| 2 | 1 | 14 | 7 | 4 | 10 | 8 | 13 | 15 | 12 | 9 | 0 | 3 | 5 | 6 | 11 |
Кожна з функцій Sj (Bj) перетворює 6-бітову послідовність в 4-бітову по наступному алгоритму:
· перший та останній біти вихідної послідовності Bj (Bj = b1 b2 b3 b4 b5 b6, де bj = 0 чи 1) визначають номер рядка k. Тобто число b1 b6 , яке переведено з двійкової системи обчислення до десяткової – це номер рядка в таблиці 3.5;
· другий, третій, четвертий та п’ятий бити послідовності Bj з визначають номер стовпчика l. Тобто число b2 b3 b4 b5 , яке переведено з двійкової системи обчислення до десяткової – це номер стовпця в таблиці 3.5;
· результат перетворення обирається на перетинанні строки k та стовпця l.
Приклад. Нехай, B=011011. Тоді S(1)(B)=0101.
Дійсно, k = 1 (b1 b6 = 01(2) = 1(10))
l = 13 (b2 b3 b4 b5 = 1101(2) = 13(10))
На перетинанні стовпця 13 та рядка 1 задано число 5(10) = 0101(2) . Таким чином, послідовність 011011 перетворена на послідовність 0101.
Функція перестановки бітів P, задається таблицею 3.6.
Таблица 3.6 "Функція перестановки P"
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
На кожному кроці ітерації для функціонального перетворення використовується нове значення ключа Ki .
Нове значення ключа Ki обчислюється з його початкового значення. Ключ являє собою 64-бітний блок з 8 бітами контролю по парності, розташованих у позиціях 8, 16, 24, 32, 40, 48, 56, 64.
Для видалення контрольних бітів і підготовки ключа до роботи використовується функція первісної підготовки ключа G, таблиця 3.7
Таблиця 3.7- Функція первісного встановлення ключа
Результат перетворення G(K) розбивається на дві частини C0 і D0 по 28 біт кожна. Перші чотири рядки матриці визначають біти послідовності C0 (символи ключа зчитуються по рядках). Наступні чотири рядки матриці визначають біти послідовності D0. Після визначення C0 і D0 рекурсивно визначаються значення Ci і Di. З цією метою виконуються операції циклічного зсування вліво на число кроків, обумовлене таблицею 3.8
Таблиця 3.8 - Циклічні зсування
| Номер ітерації | Кількість зрушень вліво | Номер ітерації | Кількість зрушень вліво |
Операції зсування виконуються незалежно для послідовностей Ci і Di. Ключ Ki, обумовлений на кожнім кроці ітерації, є результат вибору конкретних 48-и біт з 56-и бітової послідовності і їхньої перестановки (рисунок 3.4)
 |
к1
к2
к16
Рисунок 3.4 - Схема алгоритму обчислювання ключів Кi
Порядок вибору визначається функцією Н.
Ki = H (Ci Di )
Функція H визначається матрицею, що завершує формування ключа за таблицею 3.9
Таблиця 3.9 - Функція H
Символи послідовностей Ci і Di. вписуються в матрицю Н, відповідно до номерів її осередків і, потім, зчитуються по рядках. Таким чином, виконується перестановка символів.
Усі перестановки і коди в таблицях підібрані розроблювачами таким чином, щоб максимально утруднити процес розшифровування шляхом підбору ключа.
Операції, виконувані в процесі шифрування з використанням алгоритму DES обернені. Процедура розшифровування на стороні приймача відрізняється тільки черговістю формування ключів Ki. Вони повинні подаватися в зворотному порядку K16 ¸ K1.
Початково стандарт DЕS використовувався лише для шифрування та розшифровування даних ЕОМ. Потім він став використовуватися для других завдань, наприклад, для автентифікації чи захисту повідомлень електронної системи платежів при операціях поміж клієнтами та банками.
Щоб використати алгоритм DES для рішення різноманітних криптографічних задач, було розроблено декілька режимів його використання.
3.4.1 Режим „ Електронна кодова книга ”
Режим „ Електрона кодова книга ”ECB (Electronic Code Book) передбачає виконання криптографічних перетворювань у відповідності з головним алгоритмом DES. Кожний 64-х розрядний блок перетворюють з використанням одного і того же ключа (рис.3.5).
Прийом
Передача
|
Рисунок 3.5 - Режим електронної кодової книги
Головною стороною такого алгоритму – простота реалізації. Однак він найменш тривалий до спроб розшифрування. Це пояснюється тим, що при відносно невеликій довжині блоку і великій довжині тексту, що передається, деякі блоки можуть повторюватися. Це надає криптоаналітику деяку інформацію про зміст повідомлення.
3.4.2 Режим „Зчеплення блоків шифру”
Цей режим передбачає розбиття повідомлення, що передається, на блоки
М = М1М2М3М4…
До першого блоку додається по модулю два первісний вектор S який регулярно змінюється на приймальній і передавальній сторонах. Після цього, отримана сума шифрується з використанням алгоритму DES. Таким чином, в канал передається 64 – х бітове повідомлення С1.
Отримана на стороні приймача сума С1 розшифровувається, потім від неї віднімається первісний вектор S.
На наступному етапі шифрування, при передачі наступного блоку, замість первісного вектору S до зашифрованного повідомлення додається передаване повідомлення С1. Ця процедура повторюється при передаванні кожного наступного 64 – розрядного блоку (рисунок 3.6)
Таким чином, останній блок шифртексту буде функцієй секретного ключа,
первісного вектору і кожного біту відкритого тексту, незалежно від його довжини. Цей блок називають кодом автентифікації повідомлення (КАП).
КАП можна легко здобути на стороні приймача шляхом повтору процедур, які виконуються на стороні передавача.
 |
Рисунок. 3.6 - Режим "Зчеплення блоків шифру"
3.4.3 Режим „Зворотний зв’язок по шифру”
Цей режим допускає, щоб довжина блоку відрізнялась від 64 біт. Припустимо, що довжина блоків, на які розбивається послідовність, яку треба зашифрувати менше 64 біт (рисунок 3.7)
3.4.4 Режим „Зворотний зв’язок по виходу”
Цей режим, аналогічно, як і попередній, припускає, щоб довжина блоку відрізнялась від 64 біт. Різниця даного методу є в організації зворотного зв’язку. Обновлення змісту вхідного блоку здійснюється не змістом шифртексту, що передається у канал зв’язку, а змістом зашифрованого вектора ініціалізіції на першому і наступних кроках шифрування блоків.
Нехай
М = М1М2 ,…, Мn
Для усіх і = 1,…, n
Ci = Mi Å Pi.
де Pi - старші k бітів операції DES Ci-1.
Алгоритм шифрування ілюструє схема на рис.3.8
Зсування
Зсув 
ання
1 k Вх.бл. Вх. бл. 1 k
Вих. бл. Вих. бл.
1 k 1 k
1 k 1 k
Шифрування Розшифровування
Рисунок 3.8- Схема алгоритму у режимі зворотного зв’язку по виходу
Слабкість алгоритму DЕS пов’язується з невеликою довжиною ключа.
У 1993 році Вінер продемонстрував, що за 1 000 000 долл. Можна зробити машину для пошуку ключів алгоритму DЕS. При відомих вихідного та зашифровуванного тексту ця машина зможе знайти ключ за 3,5 години. Крім цього, 15 липня 1998 року коаліція компанії Cryptography Research, Advanced Wireless Technology та Electronic Frontier Foundation оголосила про атаку, яка успішно була здійснена на алгоритм DЕS. Ці компанії створили машину, що здійснювала пошук ключів під назвою DЕS Cracker (відомою також під назвою Deep Cracker), яка коштувала 250 000 долл. Зо допомогою DЕS Cracker знайшли ключ алгоритма DЕS Challenge за 56 годин. Це було доказом того, що з урахуванням рівня обчислювальних технологій кінця 1990-х років, ключ, який має довжину 56 біт є дуже малим для того, щоб забезпечити стійкість шифру з секретним ключем.
X1(1) X2(1) X3(1) X4(1)
К1(1) К2(1) К3(1) К4(1)
К5(1)
К6(1)
К1(9) К2(9) К3(9) К4(9)
Y1 Y2 Y3 Y4
Х1 - 16-ти бітовий підблок відкритого текста.
Y1 - 16-ти бітовий підблок шифртекста.
К1(9) - 16-ти бітовий підблок ключа.
- побітове додавання по модулю два 16-ти бітових підблоків
- додавання по модулю 216 16-ти бітових цілих
- помноження по модулю 216 - 1 16-ти бітових цілих
Рис.3.9 Один етап шифрування IDEA
Цей алгоритм передбачає попереднє розділення вихідної послідовності на 64- х розрядні блоки, які шифруються за допомогою 128- и бітового ключа. Алгоритмпобудований на основі мережі Фейстеля (Рис.2.12). Алгоритм шифрування зворотний.
Загальним принципом шифрування IDEA, як і у більшісті блочних алгоритмів є змішення та розсіювання. Алгоритм передбачає з`єднання операцій основних алгебраїчних груп, до яких відносяться:
- ХОR (додавання по модулю два);
- додавання за модулем 216;
- множення за модулем 216 + 1.
Всі перелічені операції виконуються з 16 -ти бітовими блоками.
Спочатку 64 –х - розрядний блок розбивається на чотири 16 -ти - розрядних підблока Х1, Х2 , Х3 та Х4 , які є вхідними даними для алгоритма. Усього алгоритм передбачає виконання восьми етапів.
На кожному етапі чотири підблока піддаються операціям додавання (по модулю два), додавання (по модулю 216) та множення (по модулю 216 +1) кожен з кожним та з 6 -бітовими 16 -ти ключами.
Кожний етап передбачає виконання наступних операцій:
1.Помножуються Х1 і перший підключ.
2.Виконується додавання за модулем 216 Х2 та другого підключа.
3.Виконується додавання за модулем 216 Х3 та третього підключа.
4.Помножуються Х4 і четвертий підключ.
5.Виконується додавання за модулем два результатів (1) та (3) кроків.
6.Виконується додавання за модулем два результатів (2) та (4) кроків.
7.Помножуються результати кроку (5) та п`ятий підключ.
8.Додавання за модулем 216 результатів (6) та (7) кроків.
9.Помножуються результати кроку (8) та шостий підключ.
10. Виконується додавання за модулем 216 результати (7) та (9) кроків.
11. Виконується додавання за модулем два результатів (1) та (9) кроків.
12. Виконується додавання за модулем два результатів (3) та (9) кроків.
13. Виконується додавання за модулем два результатів (2) та (10) кроків.
14. Виконується додавання за модулем два результатів (4) та (10) кроків.
Вихідом цикла являються чотири підблока, які одержуються як результат виконання останніх чотирьох кроків алгоритма шифрування. Цикл шифрування завершується перестановкою двох внутрішніх блоків (за виключенням останнього цикла). Таким чином, формуються входи для наступного цикла.
По закінченні останнього восьмого цикла, виконується вихідне перетворення:
1. Помноження першого підблока Х1 та першого підключа К1.
2. Додавання за модулем 216 другого підблока Х2 та другого підключа К2.
3. Додавання за модулем 216 третього підблока Х3 та третього підключа К2.
4. Помноження четвертого підблока Х4 та першого підключа К4.
Отримані після виконання оціх чотирьох операцій результати Y1, Y2, Y3 та Y4 знову об`єднуються, створюючи шифрблок.
Алгоритм шифрувания IDEA передбачає використання 52 -х ключів (по шість для кожного із восьми циклів та ще чотирьох для формування вихідного блока). Спочатку 128 -и бітовий ключ розбивають на вісім 16 -ти бітових підключей, шість із яких використовується в першому циклі, а два залишаються для наступного циклу. Потім 128 -и бітовий ключ зсовують на 25 біт вліво та знову ділять на вісім ключей. Перші чотири з них використовують у другому циклі, останні чотири – у третьому циклі. Потім формування наступних ключів виконується аналогічно до завершення алгоритму.
Процес розшифровування супроводжується генерацієй ключів в зворотному порядку, причому деякі з них змінюються зворотними величинами.
Алгоритм IDEA може працювати в будь-якому режимі, передбаченному для блочного шифрування. Він володіє рядом переваг відносно алгоритму DES. По-перше, він безпечніше, оскільки його ключ удвічі длинше. По-друге, його внутрішня структура більш сложніша та тому більш стійкіша до криптоаналізу. По-третє, його програмна реалізація удвічі бистріша, ніж DES.
Цей алгоритм запатентован в странах Європи та США.
Ki
f(Ri-1 ,Ki)
Рисунок 3.10 - Реалізація мережі Фейстеля в алгоритмі ГОСТ 28147-89
Крім цього, операція заміни, яка виконується S-б локами не постійна, а може змінюватися при необхідністі і, до того ж, її треба держати в секреті, що еквівалентно збільшенню ключа, практично до 610 біт.
Алгоритм ГОСТ допускає декілька режимів роботи. До яких відноситься режим простої заміни, режим гаммування, режим гаммування із зворотнім зв¢язком і режим формування імітовставки.
КЗП - ключовий пристрій, що запам'ятовує на 256 біт;
