Дипломная работа: Криптографічні методи захисту інформації

Мережа Фейстеля (конструкція Фейстеля) - один з методів побудови блокових шифрів. Мережа являє собою певну багаторазову структуру що повторюється (ітерована) і називається осередком Фейстеля. При переході від однієї комірки до іншої змінюється ключ, причому вибір ключа залежить від конкретного алгоритму. Операції шифрування та розшифрування на кожному етапі дуже прості, і при певній доробці збігаються, вимагаючи тільки зворотного порядку використовуваних ключів. Шифрування за допомогою даної конструкції легко реалізується як на програмному рівні, так і на апаратному, що забезпечує широкі можливості застосування. Більшість сучасних блокових шифрів використовують мережу Фейстеля в якості основи. Альтернативою мережі Фейстеля є узагальнення-перестановочне мережу. [18]

У 1971 Хорст Фейстель (Horst Feistel) запатентував два пристрої, які реалізували різні алгоритми шифрування, названі потім загальною назвою «Люцифер» (Lucifer). Одне з пристроїв використовувало конструкцію, згодом названу «мережею Фейстеля» («Feistel cipher», «Feistel network»). Робота над створенням нових криптосистем велася ним у стінах IBM разом з Доном Копперсмітом (Don Coppersmith). Проект «Люцифер» був скоріше експериментальним, але став базисом для алгоритму Data Encryption Standard (DES). У 1973 Хорст Фейстель в журналі Scientific American опублікував статтю «Криптографія і Комп'ютерна безпека» [1] [2] («Cryptography and Computer Privacy»), в якій розкрив ряд важливих аспектів шифрування і привів опис першої версії проекту «Люцифер» , не використала мережу Фейстеля. У 1977 DES став стандартом у США на шифрування даних, і до останнього часу широко використовувався в криптографічних системах. Ітеративний структура алгоритму дозволяла спростити його реалізацію у програмних і апаратних середовищах. Згідно з деякими даними вже в 1970-і роки в КДБ (СРСР) розроблявся блоковий шифр, що використав мережу Фейстеля і, ймовірно, саме він пізніше був прийнятий як ГОСТ 28147-89 в 1990 році. [14]

У 1987 були розроблені алгоритми FEAL і RC2 . Широке поширення мережі Фейстеля отримали в 1990-і роки, коли з'явилися такі алгоритми, як: Blowfish, CAST-128, TEA, XTEA, XXTEA, RC5, RC6 та ін.

Розглянемо випадок, коли ми хочемо зашифрувати деяку інформацію, представлену в двійковому вигляді в комп'ютерної пам'яті (наприклад, файл ) або електроніці, як послідовність нулів і одиниць (рис. 1.3).

·  Вся інформація розбивається на блоки фіксованої довжини. У разі, якщо довжина вхідного блоку менше, ніж розмір, який шифрується заданим алгоритмом, то блок подовжується будь-яким способом. Як правило довжина блоку є ступенем двійки, наприклад: 64 біта, 128 біт. Далі будемо розглядати операції відбуваються тільки з одним блоком, тому що з іншими в процесі шифрування виконуються ті ж самі операції.

·  Обраний блок ділиться на два рівних подблока - «лівий» (L0) і «правий» (R0).

·  «Лівий подблок» L0 видозмінюється функцією f (L0, K0) залежно від раундового ключа K0, після чого він складається за модулем 2 з «правим подблоком» R0.

·  Результат складання присвоюється новому лівому подблоку L1, який буде половиною вхідних даних для наступного раунду, а «лівий подблок» L 0 присвоюється без змін новому правому подблоку R 1 (див. схему), який буде іншою половиною.

·  Після чого операція повторюється N-1 раз, при цьому при переході від одного етапу до іншого змінюються раундовий ключі (K0 на K1 і т. д.) за будь-яким математичному правилом, де N - кількість раундів в заданому алгоритмі.

·  Розшифровка інформації відбувається так само, як і шифрування, з тим лише виключенням, що ключі ідуть у зворотному порядку, тобто не від першого до N-го, а від N-го до першого (рис. 1.4).

Рис. 1.3 Шифрування

Рис. 1.4 Розшифрування

Конструкцію Фейстеля можна описати так:

·  блок відкритого тексту ділиться на 2 рівні частини

·  в кожному раунді обчислюється ( — номер раунду)

,

де f - деяка функція, а K i - 1 ключ i-го раунду.

Результатом виконання n раундів є . Але зазвичай в n-му раунді перестановка L n і R n не проводиться, що дозволяє використовувати ту ж процедуру і для розшифрування, просто інвертувати порядок використання раундової ключової інформації:

,

Невеликою зміною можна добитися і повної ідентичності процедур шифрування і дешифрування. Одна з переваг такої моделі - оборотність алгоритму незалежно від використовуваної функції f, і вона може бути як завгодно складною.

Математичний опис опис полягає в наступному. Інволюція - взаємно-однозначне перетворення, яке є зворотним самому собі. Розглянемо на прикладі: Нехай X - вхідний блок, а A - деякий інволютивно перетворення, Y - результат. При одноразовому застосуванні перетворення до вхідного блоку вийде: Y = A X, при застосуванні перетворення до результату попереднього перетворення вийде:

.

Нехай вхідний блок X = (L, R) складається з двох підблоків (L і R) однакової довжини. Визначимо два перетворення

(шифрування ключем K) і T (L, R) = (R, L) (перестановкапідблоків). Введемо позначення:

Доведемо їх інволютивно:

1.  Нескладно помітити, що перетворення G міняє лише лівий підблок L, залишаючи правий R незмінним. Тому далі будемо розглядати тільки підблок L. Після того як перетворення G буде двічі застосовано до L отримаємо:

2. 

Таким чином G2 X = X, отже G - інволюція.

3.  T2 X = T 2 (L,R) = T (R,L) = (L,R ) = X.

Розглянемо сам процес шифрування. Визначимо X як вхідний значення. Нехай Gi - перетворення з ключем Ki, а Yi - вихідне значення після i-го раунду. Тоді перетворення на i +1- му раунді можна записати у вигляді

Yi+1 = T Gi Yi,

крім першого, де

Y1 = T G1 X

Отже, вихідне значення після m раундів шифрування буде

.

Можна помітити, що на останньому етапі не обов'язково виконувати перестановку T.

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

 [16]

У своїй роботі «Криптографія і Комп'ютерна безпека» Хорст Фейстель описує два різних блоку перетворень (функцій ) — блок підстановок (S-блок) та блок перестановок (P-блок). Можна показати, що будь-яке бінарне перетворення над двійковим блоком фіксованої довжини, зводяться до S-блоку, але на практиці в силу складності будови n-розрядного S-блоку при великих n, застосовують більш прості конструкції. Термін «блок» в оригінальній статті використовується замість функції внаслідок того, що мова йде про блокове шифрі і передбачалося, що S-і P-блоки будуть цифровими мікросхемами (цифровими блоками).

Блок підстановок (S-блок) складається з дешифратора, що перетворює n-розрядний двійковий сигнал у однорозрядної сигнал по підставі 2n, системи комутаторів внутрішніх з'єднань (усього з'єднань 2n!) і шифратора , переводить сигнал з однорозрядною 2n-річно в n- розрядний двійковий. Аналіз n-розрядного S-блоку при великому n вкрай складний, проте реалізувати такий блок на практиці дуже складно, так як число можливих з'єднань вкрай велике (2n!). На практиці блок підстановок використовується як частина більш складних систем (Рис. 1.5).

У загальному випадку S-блок може мати неспівпадаючі число входів/виходів, в цьому випадку в системі комутації від кожного виходу дешифратора може йти не строго одне з'єднання, а 2 або більше чи не йти зовсім. Те ж саме справедливо і для входів шифратора. [14]

Рис. 1.5 Принципова схема 3-розрядного S-блоку

В електроніці можна безпосередньо застосовувати наведену схему, в програмуванні ж генерують таблиці заміни. Обидва цих підходу є еквівалентними, тобто файл, зашифрований на комп'ютері, можна розшифрувати на електронному пристрої і навпаки. [21]

Страницы: 1, 2, 3, 4, 5, 6, 7