Здавалка
Главная | Обратная связь

Конструкція блокового шифру на основі мереж Фейстеля



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

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

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

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

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

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

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

 

Алгоритмічний опис

  1. блок відкритого тексту ділиться на 2 рівні частини (L0, R0 )
  2. у кожному раунді обчислюється ( 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. Можна помітити, що на останньому етапі не обов'язково виконувати перестановку T.

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

X = G1TG2T … Gm-1TGmT(Ym) = G1TG2T … Gm-1T(Ym-1) = … = G1T(Y1) = X.







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.