4. Створення підключів

Підключі зберігаються в масиві з (2r+2) слів, елементи якого позначені S[0], S[1],…,S[2r+1]. Використовуючи в якості вхідних даних параметри r та w, цей масив ініціалізується псевдовипадковими фіксованими значеннями. Потім ключ K[0…b-1] довжиною b байтів перетворюється в масив L[0…c-1], що містить c слів. Для цього байти ключа копіюються в масив L доповнюючи при необхідності останнє слово справа нулями. Зрештою виконується деяка операція змішування, що об'єднує вміст L з ініціалізованими значеннями S, в результаті чого отримують остаточне значення масиву S.

12. Стандарт шифрування idea.

Початковий варіант алгоритму IDEA з'явився в 1990 р. Розробники алгоритму, Ксуеджа Лай (Xuejia Lai) і Джеймс Мессі (James Massey) зі Швейцарського інституту ETH Zurich, дали йому назву PES (Proposed Encryption Standard - пропонований стандарт шифрування), оскільки даний алгоритм був запропонований на заміну стандарту DES. Через рік алгоритм був модифікований з метою посилення криптостійкості до диференціального криптоаналізу. Нова версія одержала назву IPES (Improved PES - покращений PES), а ще через рік алгоритм змінив назву на IDEA (International Data Encryption Algorithm - міжнародний алгоритм шифрування даних).

Основні характеристики і структура

Алгоритм IDEA шифрує дані блоками по 64 біт, а ключ шифрування алгоритму має розмір 128 біт. Блок шифрованих даних розбивається на чотири 16-бітних субблока A, B, C і D (рис. 1), над якими виконується вісім раундів перетворень:

A = A [x] Kr1

B = B + Kr2

C = C + Kr3

D = D [x] Kr4

T1 = A [+] C

T2 = B [+] D

T1 = T1 [x] Kr5

T2 = T1 + T2

T2 = T2 [x] Kr6

T1 = T1 + T2

A = A [+] T2

B = B [+] T1

C = C [+] T2

D = D [+] T1,

де Krn - з'єднання n раунду r, "+" - операція додавання 16-бітових операндів за модулем 2 {в 16-й ступеня}, [+] - побітова логічна операція "виключає або" (XOR), [x] - множення 16 -бітових операндів за модулем (2 {в 16-й ступеня} + 1), причому в якості значення субблока, що складається з одних нулів, береться значення 2 {в 16-й ступеня}.

Рис. 1. Структура алгоритма IDEA.

Після виконання описаних вище дій два внутрішніх субблока (B і C) міняються місцями - у всіх раундах, крім останнього. По завершенні восьми раундів виконуються додаткові перетворення (іноді звані дев'ятий раундом алгоритму):

A '= A [x] K91

B '= B + K92

C '= C + K93

D '= D [x] K94

Шифртекст представляє собою результат конкатенації отриманих значень A ', B', C 'і D'.

Операція розшифрування аналогічна зашифрування, з тією різницею, що при расшифровании використовуються модифіковані підключи і в іншій послідовності:

K'r1 = (K (10-r) 1) -1

K'r2 =-K (10-r) 3

K'r3 =-K (10-r) 2

K'r4 = (K (10-r) 4) -1

K'r5 = K (9-r) 5

K'r6 = K (9-r) 6,

за винятком раундів 1 і 9, в яких підключи K'r2 і K'r3 міняються місцями. Тут K'rn - з'єднання n раунду розшифрування r,-x і x-1 - зворотні значення x щодо описаних вище операцій додавання по модулю 2 {в 16-й ступеня} і множення за модулем (2 {в 16-й ступеня} + 1) відповідно. При цьому 0 {в-1-го ступеня} = 0.

Процедура розширення ключа

Завдання процедури розширення ключа - формування 52 16-бітових підключений, використовуваних у раундах шифрування і додаткових перетвореннях (тобто всього 832 біта ключової інформації). Ця процедура дуже проста, і виконується вона таким чином:

1. 128-бітний ключ шифрування ділиться на вісім підключів по 16 біт; вони стають першими вісьмома підключами алгоритму (K11, K12, K13, K14, K15, K16, K21, K22).

2. Ключ шифрування циклічно зсувається вліво на 25 біт.

3. Результат ділиться на вісім наступних підключів.

4. Ключ шифрування циклічно зсувається вліво на 25 біт, і так далі до вироблення необхідної кількості підключів.

Крипостійкість алгоритму

Вже в наступному році після появи алгоритму PES його автори опублікували роботу, в якій була доведена слабкість алгоритму по відношенню до диференціального криптоаналізу: для визначення ключа шифрування достатньо виконання 2 {в 64-го ступеня} операцій шифрування, тоді як повний перебір значень 128-бітного ключа зажадав б виконання 2 {в 128-го ступеня} операцій.

Алгоритм IDEA з'явився в результаті досить незначних модифікацій алгоритму PES (рис. 2). Якщо порівняти схеми алгоритмів IDEA і PES, видно не так вже й багато відмінностей:

    * Операція множення субблока B з другим підключимо раунду замінена операцією додавання,

    * Операція додавання субблока D з четвертим підключимо раунду замінена операцією множення,

    * По-іншому виконується зрушення субблоків в кінці раунду.

Рис. 2. Структура алгоритма PES.

Алгоритм IDEA виявився фактично невразливим до диференціального криптоаналізу, а в тій же книзі (що вийшла в 1996 р.) Брюс Шнайер відгукнувся про нього так: "Мені здається, це найкращий і надійний блочний алгоритм, опублікований до теперішнього часу".

Проте в тому ж 1996 р. відомий криптоаналітик Пол Кохер (Paul Kocher) винайшов досить складно реалізовану атаку, що дозволяє шляхом багаторазових високоточних вимірів часу виконання шифрування 2 {в 20-й ступеня} випадково вибраних відкритих текстів на ключах, пов'язаних певним співвідношенням з шуканим ключем , і подальшого аналізу результатів обчислити шуканий ключ шифрування. Дана атака (як і інші атаки на пов'язаних ключах) припускає, що криптоаналітик не має прямого доступу до шуканого ключа (наприклад, ключ прошитий в будь-якому апаратні шифратори або смарт-картки), але може змінювати певним чином різні фрагменти ключа.

А раніше, в 1993 р., дещо криптологів з Бельгії виявили в алгоритмі IDEA кілька класів слабких ключів (всього 2 {в 23-й ступеня} + 2 {в 35-й ступеня} + 2 {в 51-й ступеня} ключів різної ступеня слабкості), частина з яких, наприклад, можна обчислити криптоаналитической атакою з підібраним відкритим текстом. Проте самі автори даної атаки запропонували "протиотруту" - слабкі ключі виключаються шляхом накладення операцією XOR спеціальної шістнадцятковій константи 0DAE на кожен з'єднання перед його використанням.

Таким чином, незважаючи на виявлені недоліки, алгоритм IDEA вважається алгоритмом з високою криптостійкість. Незаперечна ж перевага даного алгоритму - висока швидкість зашифрування, не менше, ніж у два рази більше, ніж у алгоритму DES (залежно від платформи, на якій виконується шифрування). А можливість виконання операції розширення ключа "на льоту" (тобто паралельно з виконанням раундів шифрування) дуже вітається і в більш сучасних алгоритмах шифрування. Однак варто сказати, що швидкість розшифрування дещо знижується через наявність ресурсномістких операцій обчислення мультиплікативних зворотних величин по модулю (2 {в 16-й ступеня} + 1).

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