4. Стандарт шифрування даних (des). Критерії, що лежать в основі конструкції des. Алгоритми "Подвійний" та "Потрійний" des.

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

Найпопулярніша сучасна схема шифрування базується на стандарті DES (Data Encryption Standard - стандарт шифрування даних), прийнятому в 1977 році Національним бюро стандартів (NBS) США, тепер званим Національним інститутом стандартів і технології США (NIST). Фгот стандарт отримав офіційне ім'я Федеральний стандарт обробки інформації 46 (МФП § PUB 46). Відповідно до цього стандарту дані шифруються 64 - бітовими блоками з використанням 56 - бітового ключа. Багатокроковий алгоритм перетворює 64 - бітові блоки, які надходять на вхід, в 64- бітові блоки шифрованого тексту. Той же алгоритм з тим же ключем служить для зворотного перетворення шифрованого тексту у відкритий.

Стандарт DES завоював широку популярність, неодноразово стаючи при цьому об'єктом полеміки на тему забезпечуваного ним ступеня безпеки. Щоб зрозуміти суть цієї полеміки, давайте коротко розглянемо історію створення та становлення DES.

Наприкінці 60 -х IBM почала науково -дослідний проект в області комп'ютерної криптографії, який очолив Хорст Файстель (Horst Feistel). В результаті роботи над проектом на 1971 році був створений алгоритм під кодовою назвою LUCIFER [ FEIS73 ], який був проданий банку Ллойда (Lloyd's of London) для використання в системі управління оборотом готівки, теж розробленої IBM. Шифр LUCIFER представляв собою блоковий шифр Файстеля, що оперував блоками розміром 64 біта і використав ключ довжиною 128 бітів. Грунтуючись на багатообіцяючі результати проекту LUCIFER, IBM взяла курс на створення комерційного варіанту шифру, який в ідеалі можна було б розмістити в одній мікросхемі. Цей напрямок очолили Уолтер Тачман (Walter Tuchman) і Карл Мейер (Carl Meyer), що підключили до досліджень не тільки фахівців з IBM, але і консультантів і технічних фахівців NSA (National Security Agency - Управління національної безпеки США). В результаті їхніх зусиль була створена вдосконалена версія шифру LUCIFER, що володіє більшою стійкістю до криптоаналізу, але зменшеним до 56 бітів ключем, щоб алгоритм міг вміститися в одній мікросхемі,

У 1973 році Національне бюро стандартів оголосило конкурс на кращий проект по створенню загальнодержавного стандарту шифрування. Компанія IBM представила на конкурс результати проекту Тачман - Мейєра. Їх алгоритм виявився безумовно кращим з усіх запропонованих, і в 1977 році він був затверджений в якості стандарту шифрування даних (DES).

Але перш ніж стати офіційним стандартом, запропонований IBM алгоритм був підданий жорсткій критиці, яка не вщухає й донині. Нападкам піддаються в основному дві особливості шифру. По-перше, у вихідному алгоритмі LUCIFER фірми IBM використовувалися ключі довжиною 128 бітів, а в запропонованому стандарті довжина ключа зменшена до 56 бітів. Критики побоювалися (і побоюються дотепер), що такий розмір ключа занадто малий для того, щоб шифр міг гарантовано протистояти спробам криптоаналізу з простим перебором всіх можливих варіантів. Друге серйозне заперечення критиків було спрямоване проти того факту, що внутрішня структура DES, а саме структура S- матриць, була засекречена. Тому користувачі не могли бути впевнені в тому, що у внутрішній структурі DES немає будь-яких прихованих дефектів, за допомогою яких фахівці NSA могли б розшифрувати повідомлення, не володіючи ключем. Подальші дослідження, зокрема останні роботи по диференціальному криптоанализу, дозволяють з більшою впевненістю стверджувати, що DES володіє досить надійною внутрішньою структурою. Більше того, за твердженням учасників проекту з боку IBM, єдиними змінами, внесеними представлений ними проект стандарту, були запропоновані NSA зміни в структурі S- матриць, метою яких було зміцнення ймовірних слабких місць алгоритму, виявлених в ході оцінки проекту.

Як би то не було, DES вийшов у світ і став дуже популярним, особливо у фінансових додатках. У 1994 році NIST підтвердив використання DES як федерального стандарту ще на п'ять років і рекомендував його до застосування в додатках, не призначених для захисту секретної інформації. Варто додати новішої інформації, після 2010р.

Шифрування DES

Загальна схема процесу шифрування DES показана на рис. 4.1. Як і у випадку будь-якої схеми шифрування, тут на вхід функції шифрування подається два типу даних - відкритий текст, який потрібно зашифрувати, і ключ. У даному випадку довжина відкритого тексту передбачається рівною 64 бітам, а довжина ключа - 56 бітам (Насправді функція вимагає введення 64 - бітового ключа, але в якості ключа шифрування використовується тільки 56 бітів. Решта 8 бітів можуть бути бітами парності або взагалі будь-якими довільними.). З лівої частини рис. 4.1 видно, що процес перетворення відкритого тексту складається з трьох етапів. Спочатку 64 - бітовий блок відкритого тексту надходить для обробки на вхід початкової перестановки (IP), в результаті чого виходять переставлені вхідні дані. Потім слідує етап, що складається з 16 раундів застосування однієї і тієї ж функції, в якій використовуються як операції перестановки, так і підстановки. На виході останнього (16 -го) раунду є 64 - бітова послідовність, що є деякою функцією відкритого тексту і ключа. Ліва і права половини отриманої послідовності даних міняються місцями, утворюючи передрезультат (preoutput). Нарешті, цей передрезультат проходить через перестановку IP^-1, зворотну початковій, в результаті чого виходить 64 - бітовий блок шифрованого тексту. Якщо виключити початкову та кінцеву перестановки, структура DES виявиться ідентичною структурі шифру Файстеля (див. рис. 3.2).

Рис.4.1. Загальна схема алгоритму шифрування DES

У правій частині рис. 4.1 показано, яким чином використовується 56 - бітовий ключ. Спочатку до ключа теж застосовується функція перестановки. Потім за допомогою циклічного зсуву вліво і деякої перестановки з отриманого результату для кожного з 16 раундів генерується підключ (К_і). Функція перестановки одна і та ж для всіх раундів, але підключі які генеруються, виявляються різними через те, що в результаті циклічного зсуву на її вхід надходять різні біти ключа.

Таб. 4.1. Таблиці перестановок, які використовуються в DES(а) початкових перестановок (IP)

(б) перестановка, обернена до початкової (IP^-1)

(в) перестановка з розширенням (Е)

(г) перестановка (Р)

Початкова перестановка

І початкова перестановка, і зворотна їй, задаються табличним способом, як показано в табл. 4.1(a) і 4.1(б) відповідно. Щоб переконатися в тому, що представлені цими двома таблицями функції є взаємно оборотними, розглянемо наступну вхідну 64-бітову послідовність М.

М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

Тут кожне М представляє одну двійкову цифру. Після перестановки отримаємо послідовність X = ІР(М) наступного вигляду.

М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

Застосувавши зворотну перестановку, отримаємо Y = IP^-1(Х) = ІР^-1(ІР(М)), і простою перевіркою можна безпосередньо переконатися в тому, що на виході біти будуть слідувати в порядку, повністю відповідаючи вихідному.

Деталі алгоритму шифрування

Рис. 4.2. Один раунд шифрування алгоритму DES

На рис. 4.2 показана внутрішня структура алгоритму, що використовується при ітераціях. Як і спершу, почнемо розгляд з лівої частини малюнка. Ліва (L) і права (R) половини кожного 64-бітового значення розглядаються як і залежні 32-бітові величини. Як і у випадку будь-якого класичного шифру Файстеля, операції, що виконуються на кожній ітерації, можна записати у вигляді наступних формул:

L_i = R_i-1,

R_i = L_i-1 F(R_i-1, K_i).

Для будь-якого раунду довжина ключа К, дорівнює 48 бітам, а довжина елемента вхідних даних R - 32 бітам. Спочатку вхідна значення R розширюється до 48 бітів за допомогою таблиці, яка задає перестановку з розширенням (див. табл. 4.1 (в)), що полягає в повторенні 16 бітів значення R. Отримане 48 - бітове значення додається до К_і за допомогою операції XOR (виключаюче "АБО"). Результат, довжина якого теж дорівнює 48 бітам, передається функції підстановки, яка генерує 32 - бітове значення, яке визначається за табл. 4.1 (г).

Роль S- матриць у функції F розкривається ілюстрацією на рис. 4.3. Механізм підстановки визначається набором з восьми S- матриць, кожна з яких отримує на вхід 6 бітів даних і видає 4 - бітовий результат. Перетворення визначаються за табл. 4.2 за наступним правилом. Перший і останній біти вхідного значення для матриці S_і представляють 2 - бітове двійкове число, що задає одну з чотирьох підстановок, що визначаються чотирма рядками таблиці для S_і. Інші чотири біта визначають стовпець. Десяткове значення, що знаходиться на перетині заданих таким чином стовпця і стрічки, в 4- бітовому представленні буде результатом. Наприклад, якщо на вхід S, надходить значення 011001, воно задає рядок 01 (десяткове 1) і стовпець 1100 (десяткове 12). На перетині рядка 1 і стовпця 12 знаходиться значення 9, тому результат у двійковому поданні буде мати вигляд 1001.

Кожен рядок S- матриці визначає деяку оборотну підстановку. Щоб зрозуміти суть відображень, які задаються підстановками, необхідно використовувати рис. 3.1, на якому показана підстановка для рядка 0 матриці S₁.

Тут слід зробити ще кілька зауважень про структуру S- матриць. На хвилинку забудемо про те, що перетворення залежить від ключа К_і. З таблиці, яка задає перестановку з розширенням, видно, що 32 біта даних які надходять на вхід розділяються на групи по 4 біта, які потім перетворюються на 6 - бітові групи за допомогою додавання до кожної групи зовнішніх бітів з сусідніх груп

Таблиця 4.2. Визначення S-матриць алгоритму DES

Наприклад, якщо частиною надійшовшого на вхід слова буде

...EFGH IJKL MNOP...,

ця частина буде перетворена до виду

...DEFGHI HIJKLM LMNOPQ...

У кожній групі значення двох зовнішніх бітів визначають одну з чотирьох можливих підстановок (рядок S-матриці). Потім вихідне 4-бітове значення заміщає відповідне вхідне 4-бітове значення (чотири середні біта). Після цього отримане таким чином за допомогою восьми S-матриць 32-бітове вихідне значення обробляється за допомогою перестановки, щоб від вихідних значень кожної з S-матриць залежало якомога більше число результатів підстановок в наступному раунді шифрування.

Рис. 4.3. Обрахунок F(R,K)

Обчислення ключів

Повертаючись до рис. 4.1 і 4.2, зауважимо, що 56 - бітові ключі, які використовються в якості вхідних даних алгоритму, спочатку перетворюються за допомогою перестановки, що задається таблицею першої перестановки з вибором (РС-1), табл. 4.3 (a). Отримане в результаті 56 - бітове значення розглядається як комбінація двох 28 - бітових значень, для яких використовуються позначення С₀ і D₀. У кожному раунді шифрування до значень С_і-1 і D_і-1 окремо застосовуються операції циклічного зсуву вліво (обертання) на 1 або 2 біта відповідно до табл. 4.3 (в). Отримані після зсуву значення надходять на вхід наступного раунду шифрування. Ті ж значення подаються на вхід другої перестановки з вибором (РС-2) (див. табл. 4.3(б)), за допомогою якої виходить 48 - бітове вихідне значення К_і необхідне для виконання функції F (R_і-1,K_і).

Дешифрування DES

В даному випадку, як і у випадку будь-якого шифру Файстеля, для дешифрування використовується той же алгоритм, що і для шифрування, але ключі при дешифрувального ¬ вання повинні подаватися алгоритмом в зворотному порядку.

Таблиця 4.3. Обрахування ключів в алгоритмі DES (а) перша перестановка з вибором (PC-1)

(б) друга перестановка з вибором (РС-2)

(в) таблиця зсувів вліво

Лавинний ефект

Бажаною властивістю будь-якого алгоритму шифрування повинна бути висока чутливість результату до зміни початкових даних - будь-які незначні зміни відкритого тексту або ключа повинні призводити до значних змін в зашифрованому тексті (лавинний ефект). Зокрема, зміна значення всього одного біта відкритого тексту або ключа повинна відображатися в зміні значень багатьох бітів шифрованого тексту. Якщо зміни шифрованого тексту теж будуть незначними, це може дозволити противнику звузити простір ключів або область пошуку відкритого тексту.

Алгоритм DES демонструє досить сильний лавинний ефект. У табл. 4.4 показані деякі результати, взяті з [ KONH81 ] . Дані таблиці були отримані для двох наступних фрагментів відкритого тексту, які відрізняються один від одного всього одним бітом.

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

Як ключ шифрування використовувалося наступне значення. 0000001 1001011 0100100 1100010 0011100 0011000 0011000 0110010

З таблиці видно, що після трьох раундів шифрування відмінності у перетворених блоках будуть спостерігатися вже для 21 біта. Після закінчення шифрування відмінності будуть спостерігатися в 34 позиціях.

У табл. 4.4 (б) наводяться аналогічні результати для випадку, коли шифрується один фрагмент відкритого тексту

01101000 10000101 0010111 01111010 00010011 01110110 11101011 10100100

з двома різними ключами, що відрізняються один від іншого всього одним бітом:

1110010 1111011 1101111 0011000 0011101 0000100 0110001 1101110

0110010 1111011 1101111 0011000 0011101 0000100 0110001 1101110

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

Таблиця 4.4. Лавинний ефект в DES

(а) Зміни в відкритому тексті		(б) Зміни в ключі
Раунд	Число різних бітів	Раунд	Число різних бітів
0	1	0	0
1	6	1	2
2	21	2	14
3	35	3	28
4	39	4	32
5	34	5	30
6	32	6	32
7	31	7	35
8	29	8	34
9	42	9	40
10	44	10	38
11	32	11	31
12	30	12	33
13	30	13	28
14	26	14	26
15	29	15	34
16	34	16	35

Надійність DES

Після того як DES був затверджений в якості федерального стандарту США, постійно виникали дискусії з приводу його надійності і того рівня безпеки, який їм забезпечується. Ці дискусії стосуються в основному двох питань: розміру ключа і внутрішньої природи алгоритму. Можна додати нової інформації

Критерії, що лежать в основі конструкції DES

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

Згідно [ СОРР94 ], критерії, що використовувалися при розробці DES, стосуються структури S- матриць і функції Р, на вхід якої надходять дані, обчислені за допомогою цих S- матриць (див. рис. 4.3). При розробці S- матриць використовувалися такі критерії.

1. Ніякий біт вихідних даних S- матриці не повинен дуже добре апроксимуватсь лінійною функцією від вхідних бітів. Конкретніше, якщо взяти будь-який вихідний біт і будь-яку підмножину шести вхідних бітів, то відносна частка вхідних значень, для яких вихідний біт виявляється рівним результату застосування операції XOR до обраних вхідних бітів, не повинна бути близькою ні до 0, ні до 1, а повинна бути приблизно рівна 0,5.

2. Кожен рядок S- матриці (яка визначається значеннями крайніх бітів вхідної послідовності) повинен містити всі 16 можливих вихідних комбінацій бітів.

3. Якщо вхідні значення S- матриці відрізняються лише одним бітом, вихідні значення повинні відрізнятися як мінімум двома бітами.

4. Якщо вхідні значення S- матриці відрізняються точно в двох середніх бітах, вихідні значення повинні відрізнятися як мінімум двома бітами.

5. Якщо вхідні значення S- матриці відрізняються двома першими бітами і збігаються в двох останніх бітах, вихідні значення не повинні ставати однаковими.

6. Для будь-якої ненульової різниці 6-бітових вхідних значень, не більше ніж для 8 з 32 пар вхідних значень, що мають таку різницю, можуть давати одне і те ж фіксоване значення вихідної різниці.

7. Аналог критерію з п. 6 для трьох послідовних застосувань S- матриць.

Копперсміт (Coppersmith) відзначає, що п. 1 в наведеному списку необхідний тому, що S-матриці є єдиною нелінійною складовою DES. Якщо в S-матрицях буде проявлятися лінійність (тобто вихідні біти будуть лінійними комбінаціями вхідних бітів), весь алгоритм виявиться лінійним і тому простим для криптоаналізу. Це видно при аналізі шифру Хілла, який має лінійну природу [столлінгс]. Решта критеріїв покликані вирішити завдання протидії диференціальному криптоаналізу шифру і допомогти досягти хороших показників конфузії.

При створенні перестановки Р використовувалися такі критерії.

1. Чотири вихідних біта результату S- матриці раунду i мають розподілятися таким чином, щоб два з них впливали на «середні біти» раунду і + 1, а два інших - на крайні біти. При цьому не повинно трапитися так, щоб для двох сусідніх S- матриць два середніх вхідних біта виявилися однаковими. Крайніми бітами є два перших і два останніх біти вхідних даних, однакові для сусідніх S- матриць.

2. Чотири вихідних біта S- матриці в наступному раунді повинні впливати на результати шести різних S- матриць, і ніякі два з цих чотирьох вихідних бітів не повинні потрапити на вхід одній S- матриці.

3. Для двох S-матриць, S_j і S_k, якщо деякий вихідний біт матриці S_j в наступному раунді впливає на середні біти S_k, то ніякий вихідний біт S_k не повинен впливати на середні біти S_j. Наприклад, при j = k ніякий вихідний біт S_j не повинен впливати на середні біти S_j.

Ці критерії покликані забезпечити алгоритму необхідний рівень дифузії.

Структура S- матриць

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

Очевидно, однією з важливих характеристик S- матриці є її розмір. S- матриця розміру n × m припускає n-бітові вхідні значення і m-бітові вихідні. В алгоритмі DES використовуються S-матриці розміром 6×4. Алгоритми Blowfish і CAST використовують матриці 8×32. Взагалі кажучи, чим більші S-матриці, тим вища стійкість алгоритму по відношенню до методів диференціального та лінійного криптоаналізу [SCHN96]. З іншого боку, чим більше n, тим більша (в експоненційній залежності) таблиця, яка задає перетворення. Тому виходячи з практичних міркувань значення n, як правило, вибирають в діапазоні від 8 до 10. Крім того, чим більша S- матриця, тим складніше її проектування.

Як правило, структура яка застосовується сьогодні в S- матрицях відмінна від структури S- матриць, передбачених у DES. Тепер S- матриця порядку n × m зазвичай складається з 2ⁿ m - бітових рядків. Вхідні n бітів задають рядок S- матриці, а m бітів цього рядка визначають вихідне значення. Наприклад, якщо для S- матриці 8 х 32 вхідним значення є 00001001, то вихідним значенням буде 8 - бітове значення, що знаходиться в рядку 9 (перший рядок має номер 0).

Містер (Mister) і Адамі (Adams) [MIST96] висунули низку критеріїв для проектування S- матриць. Серед інших вимог є і вимога, щоб S -матриця задовольняла як суворому критерію лавинного ефекту, так і критерію незалежності бітів. Крім того, Містер і Адамі запропонували, щоб лінійні комбінації стовпців S- матриці задавалися так званими бент - функціями (bent - відхиляється, в даному випадку від лінійних). Бент - функції утворюють спеціальний клас булевих функцій, що характеризуються, відповідно до визначеного математичного критерію, вищим ступенем нелінійності [ADAM9 ].

Схожий критерій для S- матриць був запропонований в роботі [HEYS95]. Згідно з наведеним там визначенням, S- матриця задовольняє критерію гарантованого лавинного ефекту (GA - guaranteed avalanche) порядку у, якщо при зміні одного біта вхідних даних змінюються як мінімум у вихідних бітів. Автори роблять висновок, що властивість гарантованого лавинного ефекту порядку у в діапазоні від 2 до 5 забезпечує прекрасні дифузійні характеристики для будь-якого алгоритму шифрування.

При проектуванні досить великих S- матриць, до яких можна віднести і матриці розміру 8 × 32, виникає питання про вибір методу, за допомогою якого підбираються елементи S- матриці, що забезпечують відповідність згаданим вище критеріям. Найберг (Nyberg) запропонував використовувати такі підходи (наводяться по [ ROBS95 ]).

• Випадковий вибір. Елементи S- матриць вибираються за допомогою генератора або спеціальних таблиць псевдовипадкових чисел. У разі невеликого розміру (6 х 4) такий спосіб може призвести до створення S- матриць з небажаними характеристиками, але для великих матриць (8 х 32) він повинен бути цілком прийнятним.

• Випадковий вибір з перевіркою. Елементи S- матриці вибираються випадковим чином, але після цього отримані результати повинні перевірятися на відповідність різним критеріям з відсіювання тих матриць, які не витримали такої перевірки.

• Вибір вручну. Елементи S- матриці вибираються практично вручну з використанням елементарних математичних перетворень. Мабуть, саме ця методика лягла в основу розробки DES. Для великих S- матриць використання даного підходу пов'язане з чималими труднощами.

• Математичний підхід. Елементи S- матриці генеруються на основі тих чи інших математичних принципів. Такий підхід забезпечує S- матриці, що гарантують заданий рівень надійності по відношенню до методів лінійного та диференційного криптоаналізу, а також хороші показники дифузії. Саме цей підхід демонструє алгоритм CAST.

Варіацією першого підходу є випадковий вибір елементів S-матриці в додатковій залежності від деякого ключа. Приклад використання такого підходу являє алгоритм Blowfish, в якому S-матриці спочатку заповнюються псевдовипадковими числами, а потім коригуються за допомогою ключа. Значною перевагою залежних від ключа S-матриць є те, що їх неможливо заздалегідь проаналізувати на предмет наявності вразливих місць з огляду на те, що вони не є постійними.

Алгоритм обчислення ключів

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

Холл ( Hall) припустив [ADAM94], що алгоритм обчислення ключів відносно ключ / шифрований текст повинен задовольняти як мінімум строгому критерію лавинного ефекту і критерію незалежності бітів.

„Подвійний" DES

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

(а) Подвійне шифрування

(б) Потрійне шифрування

Рис. 4.4. Багатократне шифрування

Багаторазове шифрування у своїй простій формі пропонує дві стадії шифрування і два ключа (рис. 4.4 (a)). Для відкритого тексту Р і двох ключів шифрування К₁ і К₂ шифрований текст С створюється за правилом

С = E_K2[E_Kl[P]].

При дешифровании ключі застосовуються в зворотному порядку:

P = D_K1[D_K2[C]].

При використанні в якості базового шифру DES довжина ключа становить 56 х 2 = 112 бітів, що значно збільшує кріптоаналітичну стійкість шифру.

Отже, розумно припустити, що при послідовному використанні алгоритму DES двічі з двома різними ключами буде отримано відображення, відмінне від всіх тих, які виходять при одноразовому застосуванні DES. Тут слід зауважити, що, незважаючи на численні й цілком очевидні аргументи на користь такого твердження, воно було строго доведено тільки в 1992 році [САМР92].

Повторне застосування DES задає відображення, що не еквівалентне отображениям, одержуваних при одноразовому використанні DES. Але для криптоаналізу цієї схеми існує й інший шлях, що не залежить від конкретних особливостей DES, а, навпаки, відповідний для всіх блокових шифрів.

Відповідний алгоритм, який отримав назву методу двосторонньої атаки (meet-in-the-midd! e attack), вперше був описаний в [DIFF77].

"Потрійний"DES із двома ключами

Очевидним рішенням проблеми протидії методам двосторонньої атаки є потрійне шифрування з використанням трьох різних ключів. Це збільшує складність завдання криптоаналізу з відомим відкритим текстом до 2¹¹², що виходить за рамки як сьогоднішніх реальних можливостей, так і можливостей осяжного майбутнього. Однак недоліком такого підходу є вимога використання ключа розміром 56 х 3 = 168 бітів, який можна вважати аж надто громіздким.

Як альтернатива Тачман (Tuchman) запропонував потрійне шифрування з використанням тільки двох ключів [TUCH79]. Відповідна функція представляє послідовність операцій шифрування - дешифрування шифрування (EDE - encrypt - decrypt - encrypt), див. рис. 4.4 (б);

C = E_Kl[D_K2[E_Kl[P]]].

Те, що на другій стадії використовується операція дешифрування, що не суттєво з точки зору шифрування, але це дає можливість користувачам "потрійного" DES розшифровувати дані, зашифровані іншими користувачами з використанням більш старої, звичайної версії DES:

C = E_Kl[D_K1[E_Kl[P]]].= E_Kl[P].

"Потрійний"DES із двома ключами є досить популярною альтернативою DES, рекомендованої стандартами управління ключами ANS X9.17 (American National Standard : Financial Institution Key Management (Wholesale) - Американський національний стандарт управління ключами фінансових організацій (оптова торгівля)) та ISO 8732

До теперішнього часу невідомі ніякі практично здійсненні методи криптоаналізу "потрійного" DES. Копперсміт в роботі [СОРР94] зазначає, що складність аналізу потрійного" DES з використанням перебору всіх ключів має порядок 2¹¹² ≈ (5×10³³), а складність диференціального криптоаналізу порівняно із звичайним алгоритмом DES росте по експоненті, перевищуючи в результаті 10⁵².

„ Потрійний"DES із трьома ключами

Хоча описані у відкритих джерелах методи криптоаналізу і виявляються неспроможними з практичної точки зору, використання "потрійного" DES із двома ключами може викликати деякі побоювання щодо його криптоаналітичної стійкості. Тому багато фахівців схиляються до думки, що більш надійною альтернативою є "потрійний" DES із трьома ключами. Останній використовує ключ, ефективна довжина якого становить 168 бітів, і виконує перетворення, що задається формулою

C = E_K3[D_K2[E_Kl[P]]]

Зворотна сумісність з DES буде забезпечена, якщо покласти К₃ = К₂ або K₁ = К₂