Мережа Фейстеля

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

Історія

В 1973 році (Горст Файстель) (англ. Horst Feistel) в журналі Scientific American опублікував статтю «Криптографія і комп'ютерна безпека»(«Cryptography and Computer Privacy»), в якій розкрив деякі важливі аспекти шифрування, а також ввів конструкцію, названу пізніше мережею Файстеля. Ця схема була використана в проекті Lucifer фірми IBM, над яким працював Файстель і (Don Coppersmith). Цей проект був скоріше експериментальним, але став базисом для DES. Ітеративна структура алгоритму дозволяла спростити його реалізацію в апаратному середовищі.

Конструкція

Шифрування

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

• блок відкритого тексту ділиться на 2 рівні частини (${\displaystyle L_{0},\ R_{0})}$
• в кожному раунді вираховується (${\displaystyle i=1\ldots n}$ — номер раунду)

${\displaystyle L_{i}\ =\ R_{i-1}\oplus f(L_{i-1},K_{i-1})}$
${\displaystyle R_{i}\ =\ L_{i-1}}$,

де ${\displaystyle f}$ — деяка функція, а ${\displaystyle K_{i-1}}$ — ключ ${\displaystyle i}$-го раунду. Результатом виконання ${\displaystyle n}$ раундів є ${\displaystyle (L_{n},\ R_{n})}$. Але зазвичай в ${\displaystyle n}$-му раунді перестановка ${\displaystyle L_{n}}$ і ${\displaystyle R_{n}}$ не виконуються, що дозволяє використовувати ту ж процедуру і для розшифрування, просто інвертувавши порядок використання раундової ключової інформації:

${\displaystyle L_{i-1}\ =\ R_{i}\oplus f(L_{i},\ K_{i-1})}$
${\displaystyle R_{i-1}\ =\ L_{i}}$,

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

Модифікації мережі Файстеля

При великому розмірі блоків шифрування (128 біт і більше) реалізація такої мережі Файстеля на 32-розрядних архітектурах може викликати складнощі, тому використовуються модифіковані варіанти цієї конструкції. У звичайних ситуаціях використовуються мережі з 4 гілками. На малюнку показано найбільш розповсюджені модифікації. Також існують схеми, в яких довжини половинок ${\displaystyle L_{0}}$ і ${\displaystyle R_{0}}$ не збігаються. Вони називаються незбалансованими.

• Модифікації мережі Файстеля
• Тип 1
• Тип 2
• Тип 3

Шифри на основі мережі Файстеля

Такі шифри використовують класичну або модифіковану мережу Файстеля у своїй основі:

• Blowfish
• Camellia
• (CAST)
• DES
• (FEAL)
• (ГОСТ 28147-89)
• (KASUMI)
• (MacGuffin)
• MARS
• (MAGENTA)
• RC5
• RC6
• TEA
• Triple DES
• Twofish
• (XTEA)

Посилання

• Стаття Cryptography and Computer Privacy [ 18 лютого 2007 у Wayback Machine.] (англ.)