Технології захисту інформації - копия

Рис. 4.12. I-й раунд алгоритму IDEA

102

Операція розгортання ключа

П’ятдесят два 16-бітних підключа розгортаються зі 128-бітного ключа шифрування в такий спосіб. Перші вісім підключів, які позначають Z1, Z2, ..., Z8, отримуються безпосередньо з ключа, при цьому Z1 дорівнює першим 16 бітам, Z2 – наступним 16 бітам і т. д. Потім виконується циклічний зсув ключа шифрування вліво на 25 бітів, і створюються наступні вісім підключів. Ця процедура повторюється доти, поки не будуть створені всі 52 підключі.

Зазначимо, що кожний перший підключ раунду отримується зі своєї підмножини бітів ключа. Якщо весь ключ позначити як Z [1..128], то першими ключами у восьми раундах будуть:

103

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

Операція розшифрування

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

1.Перші чотири підключі першого раунду розшифрування отримуються як перші чотири підключі 10-го раунду шифрування, якщо вважати стадію заключного перетворення 9-м раундом. Перший і четвертий підключі розшифрування еквівалентні мультиплікативній інверсії за модулем (216 + 1) відповідно першого і четвертого підключів шифрування. Для раундів з 2 по 8 другий і третій підключі розшифрування еквівалентні адитивній інверсії за модулем 216 відповідно третього та другого підключів шифрування. Для раундів 1 і 9 другий і третій підключі розшифрування еквівалентні адитивній інверсії за модулем 216 відповідно другого і третього підключів шифрування.

2.Для перших восьми раундів останні два підключа i раунди розшифрування еквівалентні останнім двом підключам 9-го раунду

шифрування. Для мультиплікативної інверсії використовується нотація Zj-1, тобто:

Zj • Zj-1 =1 mod (216 + 1).

Через те, що (216 + 1) є простим числом, кожне ненульове ціле Zj≤ ≤ 216 має унікальну мультиплікативну інверсію за модулем (216 + 1). Для адитивної інверсії використовується нотація – Zj, таким чином маємо:

– Zj + Zj = 0 mod 216.

Для доведення коректності алгоритму розшифрування розглянемо його одночасно з процесом шифрування. Кожний з восьми раундів розбитий на дві стадії перетворення, перша з яких називається трансформацією, а друга – шифруванням (рис. 4.14, 4.15).

104

Рис. 4.14. Блок-схема процесу шифрування IDEA

Х1 Х2 Х3 Х4

Заключне U49...U52 перетворення

Рис. 4.15. Блок-схема процесу розшифрування IDEA

При шифруванні підтримуються такі співвідношення на виході трансформації:

Y1 = W81 • Z49; Y3 = W82 + Z51;

Y2 = W83 + Z50; Y4 = W84 • Z52.

105

Для першої стадії першого раунду процесу розшифрування справедливі такі співвідношення:

J11 = Y1 • U1; J13 = Y3 + U3;

J12 = Y2 + U2; J14 = Y4 • U4.

Підставляючи відповідні значення, одержимо:

J11 = Y1 • Z49-1 = W81 • Z49 • Z49-1 = W81;

J12 = Y2 + -Z50 = W83 + Z50 = W83 + Z50 + –Z50 = W83;

J13 = Y3 + -Z51 = W82 + Z51 + -Z51 = W82;

J14 = Y4 • Z52-1 = W84 • Z52 • Z52-1 = W84.

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

W81 = I81 MAR(I81 I83, I82 I84)

W82 = I83 MAR(I81 I83, I82 I84)

W83 = I82 MAL(I81 I83, I82 I84)

W84 = I84 MAL(I81 I83, I82 I84),

де MAR(X, Y) – правий вихід МД-структури із входами Х та Y; MAL(X, Y) – лівий вихід МД-структури із входами Х та Y.

У результаті одержимо:

V11 = J11 MAR (J11 J13, J12 J14) = W81 MAR(W81 W82, W83W84)= I81 MAR(I81 I83, I82 I84) MAR [I81 MAR(I81 I83, I82 I84) I83MAR(I81 I83, I82 I84) I82 MAL(I81 I83, I82 I84) I84 MAL(I81 I83, I82I84) ] =I81 MAR(I81 I83, I82 I84) MAR(I81 I83, I82 I84) = I81.

Аналогічно будемо мати:

V12 = I83, V13 = I82, V14 = I84.

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

V81 = I11, V82 = I13, V83 = I12, V84 = I14.

Таким чином, легко показати, що вихід всього процесу шифрування еквівалентний входу процесу шифрування.

106

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

Алгоритм складається із двох частин: розгортання ключа і шифрування даних. Розгортання ключа перетворює ключ довжиною, принаймні 448 бітів, у кілька масивів підключів загальною довжиною 4168 байтів. Кожний раунд шифру складається з перестановки, залежної від ключа, і заміни, яка залежить, і від ключа, і від даних. Раундовими операціями є XOR і додавання 32-бітних слів.

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

1.Р – масив, що містить вісімнадцять 32-бітних підключів: Р1, Р2, ..., Р18.

2.Чотири 32-бітних S-бокси з 256 входами кожний. Перший індекс означає номер S-боксу, другий індекс – номер входу:

S1,0, S1,1, … S1,255;

S2,0, S2,1, … S2,255;

S3,0, S3,1, … S3,255;

S4,0, S4,1, … S4,255.

Метод, який використовується для обчислення цих підключів, описано далі.

Процес шифрування

Входом алгоритму є 64-бітний блок даних X, який ділиться на дві 32-бітні половини: XL і XR.

XL = XL XOR Pi XR = F (XL) XOR XR Swap XL and XR.

Структура функції F

Розділити XL на чотири 8-бітних елементи A, B, C, D.

F (XL) = ((S1,А + S2,B mod 232) XOR S3,C) + S4,D mod 232.

Розшифрування відрізняється від шифрування тим, що Pi використовуються у зворотному порядку.

108

Генерування підключів

Підключі обчислюються з використанням самого алгоритму Blowfish:

1.Ініціалізувати перший Р-масив і чотири S-бокси фіксованим рядком.

2.Виконати операцію XOR P1 з першими 32 бітами ключа, операцію XOR P2 із другими 32 бітами ключа і т. д. Повторювати цикл доти, доки увесь Р-масив не буде побітово підсумований з усіма бітами ключа. Для коротких ключів виконується конкатенація ключа із самим собою.

3.Зашифрувати нульовий рядок алгоритмом Blowfish, використовуючи підключі, описані в пунктах (1) і (2).

4.Замінити Р1 і Р2 виходом, отриманим на кроці (3).

5.Зашифрувати вихід кроку (3), використовуючи алгоритм Blowfish

змодифікованими підключами.

6.Замінити Р3 і Р4 виходом, отриманим на кроці (5).

7.Продовжити процес, замінюючи всі елементи Р-масиву, а потім всі чотири S-бокси виходами відповідним чином модифікованого алго-

ритму Blowfish.

Для створення всіх підключів потрібна 521 ітерація.

4.6. Огляд алгоритмів українського конкурсу на сертифікований симетричний криптоалгоритм

У грудні 2000 р. Департамент спецзв’язку та захисту інформації СБУ та Інститут кібернетики імені В. Глушкова оголосили відкритий конкурс симетричних криптоалгоритмів з метою розробити український стандарт криптографічного захисту інформації на заміну ГОСТ 28147-89, який діє в Україні й досі.

Організатори висували такі вимоги до криптолгоритму [61]:

1.Параметри: криптоалгоритм повинен бути симетричним блоковим; розмір блоку даних – 128, 256, 512 бітів; розмір разового (сеансового)

ключа – 128, 256, 512 бітів.

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

109

3.Реалізація криптоалгоритму: криптоалгоритм повинен дозволяти реалізацію на 32-х або 64-х розрядних процесорах; зазначені в криптоалгоритмі операції повинні мати ефективну програмну та апаратну реалізацію; необхідний для роботи об’єм пам’яті має враховувати можливість реалізації криптоалгоритму у мікропристроях; за можливості необхідно передбачити можливість паралельного виконання декількох операцій.

4.Ключова система: криптоалгоритм повинен передбачати наявність довгострокового ключа; довжина синхропосилки – не менше 64 бітів.

5.У криптоалгоритмі повинні бути передбачені такі режими шифрування: проста заміна; зчеплення блоків шифрованого тексту; зворотній зв’язок за входом; зворотній зв’язок за виходом; режим вироблення гами ("довгого циклу").

Розглянемо основні поняття алгоритмів, які брали участь у цьому конкурсі. Детальніше з ними можна ознайомитися у книзі [22].

4.6.1. Алгоритм RSB-32

Алгоритм RSB-32 (назва походить від англійських слів Round, Step, Block – Раунд, Крок, Блок) – ітераційний блоковий шифр зі змінними довжинами ключа, блоку та елементів блоків, над якими виконуються нелінійні операції заміни. На відміну від інших симетричних шифрів у RSB таблиці заміни змінюються залежно від стану секретного ключа. Алгебраїчні перетворення у RSB виконуються над кільцем лишків за деяким модулем m. Загальні параметри шифру такі:

Довжина раундового ключа – 32 біти.

Довжина загального (крокового) ключа: r 64, r = 1, 2,...

Кількість кроків шифрування:s = 1, 2,...

Кількість раундів шифрування:r s. Розмір блоку: 256, 512, 1024 біти.

Розмір елементів заміни: 8, 16, або 32 біти, тобто RSB – криптосистема, орієнтована на роботу з 8- ,16-, або 32-розрядними процесорами.

Загальний ключ (Common Key) у RSB-шифрі утворюється конкатенацією r 32-розрядних раундових ключів (Rоund Key). Узагальнена структурна схема RSB-алгоритму показана на рис. 4.16.

110