Криптографічні методи захисту інформації (стр. 5 из 7)
При застосуванні із асиметричними алгоритмами шифрування для передачі ключів, майже завжди використовуються генератори криптографічно стійких псевдовипадкових чисел для генерування симетричних ключів сеансу. Однак, брак достатнього рівня випадковості в цих генераторах, або в їх початкових векторах, в минулому часто призводив до втрати конфіденційності при передачі даних. Дуже ретельний підхід до впровадження криптосистеми та генерація випадкових чисел із використанням високоякісних джерел випадкових чисел є дуже важливим для збереження конфіденційності даних, що передаються. []
Мережа Фейстеля (конструкція Фейстеля) - один з методів побудови блокових шифрів. Мережа являє собою певну багаторазову структуру що повторюється (ітерована) і називається осередком Фейстеля. При переході від однієї комірки до іншої змінюється ключ, причому вибір ключа залежить від конкретного алгоритму. Операції шифрування та розшифрування на кожному етапі дуже прості, і при певній доробці збігаються, вимагаючи тільки зворотного порядку використовуваних ключів. Шифрування за допомогою даної конструкції легко реалізується як на програмному рівні, так і на апаратному, що забезпечує широкі можливості застосування. Більшість сучасних блокових шифрів використовують мережу Фейстеля в якості основи. Альтернативою мережі Фейстеля є узагальнення-перестановочне мережу. [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-розрядного S-блоку