Відмінності між версіями «Шифр Serpent»

Рядок 194: Рядок 194:
 
<math>X_2 = X_2 <<< 22\,</math><br />
 
<math>X_2 = X_2 <<< 22\,</math><br />
 
<math>B_{i+1} = X_0, X_1, X_2, X_3\,</math>,<br />
 
<math>B_{i+1} = X_0, X_1, X_2, X_3\,</math>,<br />
В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем <math>B_{32} = S_7(B_{31} \oplus K_{31}) \oplus K_{32}\,</math>.
+
В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем <math>B_{32} = S_7(B_{31} \oplus K_{31}) \oplus K_{32}\,</math>.
 
Першою причиною вибору такого лінійного перетворення є максимізація лавинного ефекту. Такі таблиці підстановок мають властивість, що зміна кожного вхідного біта призведе до зміни 2 вихідних бітів. Таким чином, кожен вхідний біт відкритого тексту вже через 3 раунду впливає на всі вихідні біти. Аналогічно кожен біт ключа впливає на результат шифрування. Друга причина полягає в простоті перетворення. Воно може бути реалізовано на будь-якому сучасному процесорі з мінімальними витратами.
 
Першою причиною вибору такого лінійного перетворення є максимізація лавинного ефекту. Такі таблиці підстановок мають властивість, що зміна кожного вхідного біта призведе до зміни 2 вихідних бітів. Таким чином, кожен вхідний біт відкритого тексту вже через 3 раунду впливає на всі вихідні біти. Аналогічно кожен біт ключа впливає на результат шифрування. Друга причина полягає в простоті перетворення. Воно може бути реалізовано на будь-якому сучасному процесорі з мінімальними витратами.
  

Версія за 20:02, 28 квітня 2010

Алгоритм блочного шифрування
Назва: Serpent
Розробник: Елі Біхам, Ларс Кнудсен, Росс Андерсон
Створений: 1999
Опублікований: 2000
Розмір ключа: 128, 192, 256
Розмір блоку: 128 біт
Число раундів: 32
Тип: симетричний, блоковий
{{{img}}}
Імя Марія
Прізвище Стадник
По-батькові Андріївна
Факультет ФІС
Група СН-41
Залікова книжка № ПК-06-064











Основні відомості про шифр Serpent

Головна родзинка шифру SERPENT в тому, що всі три його автора - це "аси криптоаналізу", найбільш відомі розкриттям шифрів інших криптографів. Ізраїльський дослідник Елі Біхам - один з творців диференціального криптоаналізу - техніки, що лежить в основі більшості сучасних методів розкриття блокових шифрів. В даний час є професором ізраїльського технологічного інституту відділу інформатики. Починаючи з жовтня 2008 року, Biham є деканом факультету комп'ютерних наук, після роботи протягом двох років у якості головного аспірантури CS. Biham отримав докторський ступінь за винахід (публічно) диференціального криптоаналізу, працюючи разом із Аді Шамір.

Данець Ларс Кнудсен вже згадувався в цьому огляді у зв'язку з шифром угоди (Кнудсен - єдиний криптограф, що фігурує одразу в двох проектах). Після декількох ранніх робіт в банківській сфері, Кнудсен вступив в Орхус-університет в 1984 вивчав математику та інформатику, отримавши ступінь магістра в 1992 і ступінь доктора філософії в 1994 році. У 1997-2001 він працював в Університеті Бергена, Норвегія. В даний час, Кнудсен є професором на кафедрі математики в технічному університеті Данії.

Англієць Росс Андерсон з Кембриджського університету з початку 90-х років відомий своїми неординарними криптоаналітичних роботами. Росс Джон Андерсон, (р. 1956), дослідник, письменник і консультант у галузі безпеки, техніки. Він також є професором в області безпеки інженерії в Кембріджському університеті комп'ютерної лабораторії, де він бере участь у групі безпеки. У 1978 році Андерсон закінчив зі ступенем бакалавра в області математики і природничих наук у Трініті-коледжі в Кембриджі, а потім отримав кваліфікацію в галузі комп'ютерної техніки. Він працював в авіаційній промисловості і банківської перш ніж перейти в 1992 році до Кембриджського університету, для роботи над докторською дисертацією під керівництвом Роджера Нідхам і розпочав свою кар'єру як вчений-дослідник. Він отримав докторську ступінь у 1995 році і став викладачем в тому ж році.

Serpent має розмір блоку 128 біт і можливу довжинe ключа 128, 192 або 256 біт. Алгоритм представляє собою 32-раундову SP-мережу, що працює з блоком з чотирьох 32-бітових слів. Але Serpent був розроблений так, що всі операції можуть бути виконані паралельно, використовуючи 32 1-бітових потоки. При розробці Serpent використовувався більш консервативний підхід до безпеки, ніж у інших фіналістів AES, проектувальники шифру вважали, що 16 раундів достатньо, щоб протистояти відомим видам криптоаналізу, але збільшили число раундів до 32, щоб алгоритм міг краще протистояти ще не відомим методам криптоаналізу. Ставши фіналістом конкурсу AES, Serpent алгоритм в результаті голосування зайняв 2 місце. Особливостями алгоритму є: алгоритм оптимізовано для програмної реалізації в техніці "бітових зрізів" (bitslice) і має ряд обумовлених цим фактом особливостей, а саме, у ньому використовуються початкова та зворотна їй кінцева бітові перестановки, які не впливають на стійкість шифру і призначені для оптимізації його реалізації. При реалізації в техніці "бітових зрізів" виконання цих перестановок в явному вигляді не потрібно, при традиційній реалізації - потрібно. Крім того, з тієї ж самої причини в алгоритмі використовуються вузли замін малого розміру (4 на 4 біта), тому що в рамках зазначеної техніки вони реалізуються у вигляді серії логічних операцій над даними і при більшому розмірі це стає важко реалізованим.


Структура алгоритму

Алгоритм являє собою мережу Фейштеля для чотирьох гілок змішаного типу: 2 парні гілки змінюють сумісності значення непарних, потім міняються місцями. Як криптоперетворення використовуються тільки виключне "АБО", табличні підстановки і бітові зрушення. Алгоритм складається з 32 раундів. Самі раунди складені таким чином, що додавання до гілок матеріалу ключа на першому і останньому раундах утворює вхідне і вихідне забілювання. Алгоритм Serpent являє собою SP-мережу, в якій весь блок даних довжиною 128 біт на кожному раунді розбивається на 4 слова довжиною по 32 біта. Всі значення, що використовуються для шифрування, представляються бітовими потоками. Індекси біт пробігають значення від 0 до 31 для 32-бітових слів, від 0 до 127 для 128-бітових блоків, від 0 до 255 для 256-бітових ключів і так далі. Для внутрішніх обчислень всі біти величин представлені в прямому порядку (little-endian). Serpent шифрує відкритий текст P довжиною 128 біт в шифротекст C довжиною 128 біт за 32 раунди за допомогою 33 підключів [math]K_{0}, ..., K_{32}\,[/math] довжиною 128 біт. Довжина використовуваного ключа може приймати різні значення, але для конкретики зафіксуємо їх довжину у 128, 192 або 256 біт. Короткі ключі довжиною менше 256 біт доповнюються до повної довжини в 256 біт.
Шифрування складається з наступних основних кроків:

  • Початкова перестановка;
  • 32 раунди, кожен з яких складається з операції змішування з 128-бітовим ключем (побітове логічне що виключає «або»), таблична заміна (S-box) і лінійне перетворення. В останньому раунді лінійне перетворення замінюється додатковим накладанням ключа;
  • Кінцева перестановка;

Початкова і кінцева перестановки не мають будь-якої криптографічно] значущості. Вони використовуються для спрощення оптимізованої реалізації алгоритму і підвищення обчислювальної ефективності.
Рівняння стуктури алгоритму:
[math]\hat B_0 = IP(P)\,[/math]
[math]\hat B_{i+1} = R_i(\hat B_{i})\,[/math]
[math]C = FP(\hat B_{32})\,[/math],
де
[math]R_i(X) = L(\hat S_i(X \oplus \hat K_i)), i = 0, ..., 30\,[/math]
[math]R_i(X) = \hat S_i(X \oplus \hat K_i) \oplus \hat K_{32}, i = 31\,[/math],
де [math]\hat S_i\,[/math] - це змінні таблиці підстановки [math]\hat S_{i mod 8}\,[/math] 32 рази паралельно і [math]L\,[/math] — лінійне перетворення.

Розшифрування та розширення ключа

Розшифрування відрізняється від шифрування тільки тим, що повинні бути використані інверсні (зворотні) таблиці замін, а також зворотні лінійні перетворення, і ключі подаються у зворотному порядку. Як і інші алгоритми, що брали участь у конкурсі AES, Serpent має можливі довжини ключа 128, 192 або 256 біт. "Неповний» ключ довжиною менше 256 біт доповнюється за наступним правилом: додається одиничний біт праворуч, за ним іде стільки нульових бітів, щоб довжина ключа стала дорівнювати 256 бітам.

Алгоритм вибору підключів із ключа

Спочату при необхідності ключ доповнюється до 256 біт і перетворюється в 33 підключа [math]K_{0}, ..., K_{32}\,[/math] довжиною 128 біт наступним чином:
Оригінальний ключ представляється у вигляді 8 32-бітових слів [math]w_{-8}, ..., w_{-1}[/math] для обчислення проміжного ключа за правилом:
[math]w_i = (w_{i-8}+w_{i-5}+w_{i-3}+w_{i-1}+\phi+i) \lt \lt \lt 11 \,[/math],
де [math]\phi \,[/math] — це дробова частина золотого січення [math]\frac{\sqrt{5}+1}{2}[/math] або 0x9e3779b9 .
Раундовий ключі обчислюються з проміжних ключів використанням таблиць підстановок S-box наступним чином:

[math]\left \{ k_{0}, k_{1}, k_{2}, k_{3} \right \} = S_3\left ( w_{0}, w_{1}, w_{2}, w_{3} \right ) \,[/math]
[math]\left \{ k_{4}, k_{5}, k_{6}, k_{7} \right \} = S_2\left ( w_{4}, w_{5}, w_{6}, w_{7} \right ) \,[/math]
[math]\left \{ k_{8}, k_{9}, k_{10}, k_{11} \right \} = S_1\left ( w_{8}, w_{9}, w_{10}, w_{11} \right ) \,[/math]
[math]\left \{ k_{12}, k_{13}, k_{14}, k_{15} \right \} = S_0\left ( w_{12}, w_{13}, w_{14}, w_{15} \right ) \,[/math]
[math]\left \{ k_{16}, k_{17}, k_{18}, k_{19} \right \} = S_7\left ( w_{16}, w_{17}, w_{18}, w_{19} \right ) \,[/math]
[math]\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots \,[/math]
[math]\left \{ k_{124}, k_{125}, k_{126}, k_{127} \right \} = S_4\left ( w_{124}, w_{125}, w_{126}, w_{127} \right ) \,[/math]
[math]\left \{ k_{128}, k_{129}, k_{130}, k_{131} \right \} = S_3\left ( w_{128}, w_{129}, w_{130}, w_{131} \right ) \,[/math]

Проміжні 32-бітові величини [math]k_j\,[/math] перенумеровуються і виходять 128-бітові підключі:
[math]K_i = \left \{ k_{4i}, k_{4i+1}, k_{4i+2}, k_{4i+3} \right \}\,[/math]
При стандартному описі алгоритму ми повинні застосувати початкову перестановку [math]IP\,[/math] до раундового ключа, щоб розташувати біти ключа в належному порядку, тобто [math]\hat K_i = IP(K_i)\,[/math].


Перестановка, S-box, лінійне перетворення.

Початкова перестановка [math]IP \,[/math], задається наступною таблицею, де вказується позиція, на яку перейде відповідний біт (наприклад, біт 1 перейде на 32 позицію).

Таблиця початкової перестановки [math]IP \,[/math]
0 32 64 96 1 33 65 97 2 34 66 98 3 35 67 99
4 36 68 100 5 37 69 101 6 38 70 102 7 39 71 103
8 40 72 104 9 41 73 105 10 42 74 106 11 43 75 107
12 44 76 108 13 45 77 109 14 46 78 110 15 47 79 111
16 48 80 112 17 49 81 113 18 50 82 114 19 51 83 115
20 52 84 116 21 53 85 117 22 54 86 118 23 55 87 119
24 56 88 120 25 57 89 121 26 58 90 122 27 59 91 123
28 60 92 124 29 61 93 125 30 62 94 126 31 63 95 127

В алгоритмі Serpent таблиці заміни є 4-бітовими перестановками з властивостями стійкості до диференціального криптоаналізу, до лінійного криптоаналізу і тією властивістю, що порядок вихідних біт, як функції вхідних повинен бути максимальний, тобто бути рівним 3. Таблиця підстановок генерується з відомих і добре вивчених таблиць для алгоритму DES в ітераційному процесі, поки не будуть отримані бажані диференціальні й лінійні властивості. Таким чином, створюється 8 таблиць підстановок.

Таблиця підстановки [math]S_i \,[/math]
S0: 3 8 15 1 10 6 5 11 14 13 4 2 7 0 9 12
S1: 15 12 2 7 9 0 5 10 1 11 14 8 6 13 3 4
S2: 8 6 7 9 3 12 10 15 13 1 14 4 0 11 5 2
S3: 0 15 11 8 12 9 6 3 13 1 2 4 10 7 5 14
S4: 1 15 8 3 12 0 11 6 2 5 4 10 9 14 7 13
S5: 15 5 2 11 4 10 9 12 0 3 14 8 13 6 7 1
S6: 7 2 12 5 8 4 6 11 14 9 1 15 13 3 10 0
S7: 1 13 15 0 14 8 2 11 7 4 12 10 9 3 5 6

Лінійне перетворення LT задається наступною таблицею, де біти перераховані від 0 до 127 (наприклад, вихідний 2 біт утворений 2, 9, 15, 30, 76, 84, 126 бітами, складеними за модулем 2). У кожному рядку описується 4 вихідних бита, які разом складають вхідні дані на одну таблицю замін у наступному раунді. Варто зазначити, що даний набір являє собою таблицю [math]IP(LT(FP(x))) \,[/math], де [math]LT \,[/math] і є лінійне перетворення. Ця перестановка є зворотною до початкової [math]FP = IP^{-1} \,[/math], тобто і задається наступною таблицею:

Кінцева перестановка [math]FP \,[/math]
0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60
64 68 72 76 80 84 88 92 96 100 104 108 112 116 120 124
1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61
65 69 73 77 81 85 89 93 97 101 105 109 113 117 121 125
2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62
66 70 74 78 82 86 90 94 98 102 106 110 114 118 122 126
3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63
67 71 75 79 83 87 91 95 99 103 107 111 115 119 123 127

Ефективна реалізація

Бажання авторів зробити алгоритм саме таким, яким він є стає зрозумілим при розгляді його ефективної низькорівневою реалізації. Serpent був створений таким чином, щоб всі операції в процесі шифрування й розшифрування одного блоку могли бути виконані паралельно в 32 потоку. До того ж низькорівневе опис алгоритму набагато простіше, ніж стандартне опис. Ніяких початкових і кінцевих перестановок не потрібно. Шифрування складається з 32 раундів. Відкритий текст є першими проміжними даними О [math]B_0 = P \,[/math]. Після закінчення 32 раунду, i кожен раунд складається з:

  • Змішування з ключем. Проводиться побітове виключне АБО проміжних даних [math]B_i \,[/math] , з ключем довжиною 128 біт ;
  • Застосування таблиць підстановок. Вхідні дані довжиною 128 біт поділяються на 4 слова по 32 біта. Таблиця підстановок, реалізована послідовністю логічних операцій (як якщо це було б реалізовано апаратно), застосовується до цих 4 слів. У результаті виходить 4 вихідних слова. Таким чином, центральний процесор виконує підстановку по 32 копій таблиці одночасно;
  • Лінійне перетворення. 32-бітові слова перетворюються наступним чином:

[math]X_0, X_1, X_2, X_3 = S_i(B_i \oplus K_i)\,[/math]
[math]X_0 = X_0 \lt \lt \lt 13\,[/math]
[math]X_2 = X_2 \lt \lt \lt 3\,[/math]
[math]X_1 = X_1 \oplus X_0 \oplus X2\,[/math]
[math]X_3 = X_3 \oplus X_2 \oplus (X_0 \lt \lt 3)\,[/math]
[math]X_1 = X_1 \lt \lt \lt 1\,[/math]
[math]X_3 = X_3 \lt \lt \lt 7\,[/math]
[math]X_0 = X_0 \oplus X_1 \oplus X3\,[/math]
[math]X_2 = X_2 \oplus X_3 \oplus (X_1 \lt \lt 7)\,[/math]
[math]X_0 = X_0 \lt \lt \lt 5\,[/math]
[math]X_2 = X_2 \lt \lt \lt 22\,[/math]
[math]B_{i+1} = X_0, X_1, X_2, X_3\,[/math],
В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем [math]B_{32} = S_7(B_{31} \oplus K_{31}) \oplus K_{32}\,[/math]. Першою причиною вибору такого лінійного перетворення є максимізація лавинного ефекту. Такі таблиці підстановок мають властивість, що зміна кожного вхідного біта призведе до зміни 2 вихідних бітів. Таким чином, кожен вхідний біт відкритого тексту вже через 3 раунду впливає на всі вихідні біти. Аналогічно кожен біт ключа впливає на результат шифрування. Друга причина полягає в простоті перетворення. Воно може бути реалізовано на будь-якому сучасному процесорі з мінімальними витратами.