Serpent (cipher)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Алгоритм блочного шифрування
Serpent-linearfunction.svg
Назва: Serpent
Розробник: Росс Андерсон, Елі Біхам, Ларс Кнудсен
Створений: 1998 р.
Опублікований: 1998 р.
Розмір ключа: 128/192/256 біт
Розмір блоку: 128 біт
Число раундів: 32
Тип: SP-мережа

Serpent («змія», деякі попередні розробки авторів теж носили назви на честь тварин, наприклад Tiger, Bear) - симетричний блочний алгоритм шифрування, розроблений Россом Андерсоном, Елі Біхамом та Ларсом Кнудсеном. Алгоритм був одним з фіналістів 2-го етапу конкурсу AES. Як і інші алгоритми, які брали участь у конкурсі AES, Serpent має розмір блоку 128 біт і можливі довжини ключа 128, 192 або 256 біт. Алгоритм являє собою 32-раундовий шифр на основі SP-мережі, і працює з блоком з чотирьох 32-бітових слів. Serpent був розроблений так, що всі операції можуть бути виконані паралельно, використовуючи 32-а 1-бітних «потоків».

При розробці Serpent використовувався консервативніший підхід до безпеки, ніж у інших фіналістів AES, проектувальники шифру вважали, що 16 раундів достатньо, щоб протистояти відомим видам криптоаналізу, але збільшили число раундів до 32, щоб алгоритм міг краще протистояти ще не відомим методам криптоаналізу.

Ставши фіналістом конкурсу AES, алгоритм Serpent в результаті голосування зайняв 2 місце.

Шифр Serpent не запатентований і є громадським надбанням.

Основні принципи[ред.ред. код]

Алгоритм створювався під гаслом «криптографічний алгоритм 21 століття» для участі в конкурсі AES. При створенні нового алгоритму Serpent його автори дотримувалися консервативних поглядів на проектування, що підтверджується первісним рішенням про використання таблиць підстановки з відомого багато років раніше алгоритму шифрування DES, який протягом довгого часу вивчався провідними фахівцями в області криптографії та захисту інформації і чиї властивості і особливості були добре відомі науковому світу. Одночасно з цим до нового алгоритму міг бути застосований вичерпний аналіз, вже розроблений для DES. Не використовувалися нові, неперевірені і невипробувані технології при створенні шифру, який у разі прийняття був би використаний для захисту величезних масивів фінансових транзакцій та урядової інформації. Основною вимогою до учасників конкурсу AES було те, що алгоритм-претендент повинен бути швидшим, ніж 3DES, і надавати як мінімум такий же рівень безпеки: він повинен мати блок даних довжиною 128 біт і ключ завдовжки 256 біт. 16-раундовий Serpent був би таким же надійним, як 3DES, але в два рази швидшим. Однак, автори вирішили, що для більшої надійності варто збільшити кількість раундів до 32. Це зробило шифр таким же швидким, як DES, і набагато надійнішим, ніж 3DES.

Структура алгоритму[ред.ред. код]

Алгоритм Serpent являє собою SP-мережу, у котрій весь блок даних довжиною 128 біт на кожному раунді розбивається на 4 слова довжиною по 32 бита. Всі значення, що використовуються при шифруванні, представляються бітовими потоками. Індекси біт пробігають значення від 0 до 31 для 32-бітових слів, від 0 до 127 для 128-бітних блоків, від 0 до 255 для 256-бітних ключів і так далі. Для внутрішніх обчислень всі біти величин представлені в прямому порядку (little-endian).

Serpent шифрує відкритий текст P довжиною 128 біт в шифротекст C довжиною таких же 128 біт за 32 раунд за допомогою 33 подключів  K_ {0}, ..., K_ {32} \, довжиною 128 біт. Довжина використовуваного ключа може приймати різні значення, але для конкретики зафіксуємо їх довжину в 128, 192 або 256 біт. Короткі ключі довжиною менше 256 біт доповнюються до повної довжини в 256 біт.

Шифрування складається з наступних основних кроків:

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

Початкова і кінцева перестановки не мають будь-якої криптографічного значущості. Вони використовуються для спрощення оптимізованої реалізації алгоритму і підвищення обчислювальної ефективності.

Рівняння структури алгоритму:

 \hat B_0 = IP (P) \,
 \hat B_ {i +1} = R_i (\hat B_ {i}) \,
 C = FP (\hat B_ {32}) \, ,

де

 R_i (X) = L (\hat S_i (X \oplus \hat K_i)), i = 0, ..., 30 \,
 R_i (X) = \hat S_i (X \oplus \hat K_i) \oplus \hat K_ {32}, i = 31 \, ,

де  \hat S_i \, - це застосування таблиці підстановки  \hat S_ {i mod 8} \, 32 раз паралельно і  L \, - лінійне перетворення.

Розширення ключа[ред.ред. код]

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

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

Спочатку при необхідності ключ доповнюється до 256 біт і перетвориться в 33 підключа  K_ {0}, ..., K_ {32} \, довжиною 128 біт наступним способом:

Вихідний ключ представляється у вигляді 8 32-бітових слів  w_ {-8}, ..., w_ {-1} для обчислення проміжного ключа за правилом:

 W_i = (w_ {i-8} + w_ {i-5} + w_ {i-3} + w_ {i-1} + \phi + i) <<< 11 \, ,

де  \phi \, - це дробова частина золотого перерізу  \frac {\sqrt {5} +1} {2} або 0x9e3779b9 в шістнадцятковій системі числення, а  <<< \, - це циклічний бітовий зсув.

Раундові ключі обчислюються з проміжних ключів використанням таблиць підстановки наступним чином:

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

Проміжні 32-бітові величини  k_j \, перенумеровуються і виходять 128-бітні підключі:

K_i = \left \{ k_{4i}, k_{4i+1}, k_{4i+2}, k_{4i+3} \right \}\,

При стандартному описі алгоритму ми повинні застосувати початкову перестановку  IP \, до раундового ключа, щоб розташувати біти ключа в належному порядку, тобто  \hat K_i = IP (K_i) \,

Початкова перестановка  IP \, [ред.ред. код]

Дана перестановка  IP \, задається наступною таблицею, де вказується позиція, на яку перейде відповідний біт (наприклад, біт 1 перейде на 32 позицію):

Початкова перестановка  IP \,
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

S-бокси (таблиці замін)[ред.ред. код]

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

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

Нижче представлені таблиці підстановки:

Таблиця підстановок S_i \,
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

І інверсні таблиці підстановки:

Таблиця інверсних підстановок S_i^{-1} \,
InvS0: 13 3 11 0 10 6 5 12 1 14 4 7 15 9 8 2
InvS1: 5 8 2 14 15 6 12 3 11 4 7 9 1 13 10 0
InvS2: 12 9 15 4 11 14 1 2 0 3 6 13 5 8 10 7
InvS3: 0 9 10 7 11 14 6 13 3 5 12 2 4 8 15 1
InvS4: 5 0 8 3 10 9 7 14 2 12 11 6 4 15 13 1
InvS5: 8 15 2 9 4 1 13 14 11 6 5 3 7 12 10 0
InvS6: 15 10 1 13 5 3 6 0 4 9 14 7 2 12 8 11
InvS7: 3 0 6 13 9 14 15 8 5 12 11 7 10 1 4 2

Лінійне перетворення  LT \, [ред.ред. код]

Лінійне перетворення  LT \, задається наступною таблицею, де біти перераховані від 0 до 127 (наприклад, вихідний 2 біт утворений 2, 9, 15, 30, 76, 84, 126 битами, складеними за модулем 2) . В кожному рядку описується 4 вихідних біти, які разом складають вхідні дані на одну таблицю замін в наступному раунді. Варто зазначити, що даний набір представляє собою таблицю  IP (LT (FP (x))) \, , де  LT \, і є те лінійне перетворення.

Таблиця лінійного перетворення:

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

Таблиця зворотного лінійного перетворення, яке використовується при розшифровці:

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

Кінцева перестановка  FP \, [ред.ред. код]

Дана перестановка є зворотною до початкової, тобто  FP = IP ^ {-1} \, , і задається наступною таблицею:

Кінцева перестановка FP \,
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 раундів. Відкритий текст є першими проміжними даними  B_0 = P \, . Потім виконується 32 раунди, кожен i-й раунд складається з:

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

X_0, X_1, X_2, X_3 = S_i(B_i \oplus K_i)\,

X_0 = X_0 <<< 13\,
X_2 = X_2 <<< 3\,
X_1 = X_1 \oplus X_0 \oplus X2\,
X_3 = X_3 \oplus X_2 \oplus (X_0 << 3)\,
X_1 = X_1 <<< 1\,
X_3 = X_3 <<< 7\,
X_0 = X_0 \oplus X_1 \oplus X3\,
X_2 = X_2 \oplus X_3 \oplus (X_1 << 7)\,
X_0 = X_0 <<< 5\,
X_2 = X_2 <<< 22\,
B_{i+1} = X_0, X_1, X_2, X_3\,,

де  <<< \, позначає циклічний бітовий зсув, а  << \, - бітовий зсув. В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем  B_ {32} = S_7 (B_ {31} \oplus K_ {31}) \oplus K_ {32} \,

Першою причиною вибору такого лінійного перетворення є максимізація лавинного ефекту. Такі таблиці підстановки мають властивість, що зміна кожного вхідного біта призведе до зміни 2 вихідних бітів. Таким чином, кожен вхідний біт відкритого тексту вже через 3 раунди впливає на всі вихідні біти. Аналогічно кожен біт ключа впливає на результат шифрування.

Друга причина полягає в простоті перетворення. Воно може бути реалізоване на будь-якому сучасному процесорі з мінімальними витратами.

Безпека і крипостійкість[ред.ред. код]

При розробці та аналізі алгоритму Serpent не було виявлено будь-яких вразливостей в повній 32-раундовій версії. Але при виборі переможця конкурсу AES, це було справедливо і до решти алгоритмів-фіналістів.

На думку творців Serpent, алгоритм може бути зламаний, тільки якщо буде створена нова потужна математична теорія.

Варто відзначити, що XSL-атака, якщо буде доведена ефективність її проведення, послабить крипостійкість Serpent.

Література[ред.ред. код]

Посилання[ред.ред. код]