МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ І СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Лабораторна робота №5
на тему:
“Симетричні блокові шифри на основі мережі Фейстеля”
з дисципліни:
“Захист інформації в комп'ютерних мережах”
Мета роботи: ознайомитися з методом побудови алгоритмів симетричного блокового шифрування на прикладі мережі Фейстеля.
Теоретичні відомості
Конструкція блокового шифру на основі мереж Фейстеля
Розглянемо випадок, коли ми хочемо зашифрувати деяку інформацію, представлену у двійковому вигляді в комп'ютерній пам'яті (наприклад, файл) або електроніці, як послідовність нулів й одиниць.
Вся інформація розбивається на блоки фіксованої довжини. У випадку, якщо довжина вхідного блоку менше, ніж розмір, що шифрується заданим алгоритмом, то блок подовжується яким-небудь способом. Як правило довжина блоку є ступенем двійки, наприклад: 64 біта, 128 біт. Далі будемо розглядати операції, що відбуваються тільки з одним блоком, тому що з іншими в процесі шифрування виконуються ті ж самі операції.
Обраний блок ділиться на два рівних подблока — «лівий» (L0) і «правий» (R0).
«Лівий подблок» L0 видозмінюється функцією f(L0,K0) залежно від раундового ключа K0, після чого він додається по модулі 2 з «правим підблоком» R0.
Результат додавання присвоюється новому лівому підблоку L1, що буде половиною вхідних даних для наступного раунду, а «лівий подблок» L0 присвоюється без змін новому правому підблоку1 (див. схему), що буде іншою половиною.
Після чого операція повторюється N-1 раз, при цьому при переході від одного етапу до іншого міняються раундові ключі (K0 на K1 і т.д.) за яким-небудь математичним правилом, де N — кількість раундів у заданому алгоритмі. Розшифрування інформації відбувається так само, як і шифрування, з тією лише відмінністю, що ключі йдуть у зворотному порядку, тобто не від першого до N-ному, а від N-го до першого.
/
/
Шифрування
Розшифрування
Алгоритмічний опис
блок відкритого тексту ділиться на 2 рівні частини (L0, R0 )
у кожному раунді обчислюється ( i=1…n - номер раунду)
Li = Ri-1 + f (Li-1, Ki-1)
Ri = Li-1
де f — деяка функція, а Ki − 1 — ключ i-го раунду.
Результатом виконання n раундів є (Ln, Rn ). Але звичайно в n-ом раунді перестановка Ln й Rn не виконується, що дозволяє використати ту ж процедуру й для розшифрування, просто інвертувавши порядок використання раундової ключової інформації:
Li-1 = Ri + f (Li, Ki-1)
Ri-1 = Li .
Невеликою зміною можна домогтися й повної ідентичності процедур шифрування й дешифрування.
Одна з переваг такої моделі — оборотність алгоритму незалежно від використовуваної функції f, і вона може бути як завгодно складною
Математичний опис
Інволюція — взаємо-однозначне перетворення, застосування якого двічі приводить до вихідного значення.
Нехай X — вхідний блок, а A - деяке інволютиве перетворення, Y - вихід.
При однократному застосуванні перетворення: Y = AX, при повторному: AY = A2X = AAX = XɣX .
Нехай вхідний блок X=(L, R) складається із двох підблоков (L й R) рівної довжини. Визначимо два перетворення G (X,K) = (L + F(K,R), R) (шифрування ключем K) і T(L,R) = (R,L) (перестановка подблоков). Введемо позначення: X′ = (L′, R′) =GX , X″= (L″, R″) = G2X.
Доведемо їх інволютивність:
Нескладно помітити, що перетворення G міняє тільки лівий подблок L, залишаючи правий R незмінним. Тому далі будемо розглядати тільки подблок L. Після того як перетворення G буде двічі застосоване до L одержимо:
L″= L′+ F(K, R′) = L′+ F(K, R) = L + F(K, R)+F(K,R) = L .
У такий спосіб G2X = X, отже G - інволюція.
T2X = T2(L,R) = T(R,L) = (L,R) = X.
Розглянемо сам процес шифрування.
Визначимо X як вхідне значення. Нехай Gi — перетворення із ключем Ki, а Yi — вихідне значення після i-го раунду. Тоді перетворення на i+1-му раунді можна записати у вигляді Yi + 1 = TGiYi, крім першого, де Y1 = TG1X. Отже, вихідне значення після m раундів шифрування буде Ym = TGmYm-1 = TGmTGm-1 … TG1X. Можна помітити, що на останньому етапі не обов'язково викону...
