Serpent («змія», деякі попередні розробки авторів теж носили назви на честь тварин, наприклад Tiger, Bear) - симетричний блочний алгоритм шифрування, розроблений Россом Андерсоном, Елі Біхамом та Ларсом Кнудсеном. Алгоритм був одним з фіналістів 2-го етапу конкурсу AES. Як і інші алгоритми, які брали участь у конкурсі AES, Serpent має розмір блоку 128 біт і можливі довжини ключа 128, 192 або 256 біт. Алгоритм являє собою 32-раундовий шифр на основі SP-мережі, і працює з блоком з чотирьох 32-бітових слів. Serpent був розроблений так, що всі операції можуть бути виконані паралельно, використовуючи 32-а 1-бітних «потоків».
Розробники | Росс Андерсон, Елі Біхам, Ларс Кнудсен |
---|---|
Уперше оприлюднений | 1998 р. |
Раундів | 32 |
Тип | SP-мережа |
При розробці 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 подключів довжиною 128 біт. Довжина використовуваного ключа може приймати різні значення, але для конкретики зафіксуємо їх довжину в 128, 192 або 256 біт. Короткі ключі довжиною менше 256 біт доповнюються до повної довжини в 256 біт.
Шифрування складається з наступних основних кроків:
- Початкова перестановка;
- 32 раунд, кожен з яких складається з операції змішування з 128-бітовим ключем (побітове логічне виключаюче «або»), таблична заміна (S-box) і лінійне перетворення. В останньому раунді лінійне перетворення замінюється додатковим накладанням ключа;
- Кінцева перестановка;
Початкова і кінцева перестановки не мають будь-якої криптографічного значущості. Вони використовуються для спрощення оптимізованої реалізації алгоритму і підвищення обчислювальної ефективності.
Рівняння структури алгоритму:
- ,
де
- ,
де - це застосування таблиці підстановки 32 раз паралельно і - лінійне перетворення.
Розширення ключа
Як і інші алгоритми, що брали участь в конкурсі AES, Serpent має можливі довжини ключа 128, 192 або 256 біт. «Неповний» ключ довжиною менше 256 біт доповнюється за наступним правилом: додається одиничний біт справа, за ним слід стільки нульових бітів, щоб довжина ключа стала дорівнює 256 бітам.
Алгоритм вибору підключів з ключа
Спочатку при необхідності ключ доповнюється до 256 біт і перетвориться в 33 підключа довжиною 128 біт наступним способом:
Вихідний ключ представляється у вигляді 8 32-бітових слів для обчислення проміжного ключа за правилом:
- ,
де - це дробова частина золотого перерізу або 0x9e3779b9 в шістнадцятковій системі числення, а - це циклічний бітовий зсув.
Раундові ключі обчислюються з проміжних ключів використанням таблиць підстановки наступним чином:
Проміжні 32-бітові величини перенумеровуються і виходять 128-бітні підключі:
При стандартному описі алгоритму ми повинні застосувати початкову перестановку до раундового ключа, щоб розташувати біти ключа в належному порядку, тобто
Початкова перестановка
Дана перестановка задається наступною таблицею, де вказується позиція, на яку перейде відповідний біт (наприклад, біт 1 перейде на 32 позицію):
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 таблиць підстановки.
Нижче представлені таблиці підстановки:
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 |
І інверсні таблиці підстановки:
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 |
Лінійне перетворення
Лінійне перетворення задається наступною таблицею, де біти перераховані від 0 до 127 (наприклад, вихідний 2 біт утворений 2, 9, 15, 30, 76, 84, 126 битами, складеними за модулем 2) . В кожному рядку описується 4 вихідних біти, які разом складають вхідні дані на одну таблицю замін в наступному раунді. Варто зазначити, що даний набір являє собою таблицю , де і є те лінійне перетворення.
Таблиця лінійного перетворення:
{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} |
Таблиця зворотного лінійного перетворення, яке використовується при розшифровці:
{ 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} |
Кінцева перестановка
Дана перестановка є зворотною до початкової, тобто , і задається наступною таблицею:
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 раундів. Відкритий текст є першими проміжними даними . Потім виконується 32 раунди, кожен i-й раунд складається з:
- Змішування з ключем. Проводиться побітове виключаюче «або» проміжних даних з ключем довжиною 128 біт;
- Застосування таблиць підстановки. Вхідні дані довжиною 128 біт поділяються на 4 слова по 32 біта. Таблиця підстановки, реалізована послідовністю логічних операцій (як якщо це було б реалізовано апаратно), застосовується до цих 4 словам. В результаті виходить 4 вихідних слова. Таким чином, центральний процесор виконує підстановку по 32 копій таблиці одночасно;
- Лінійне перетворення. 32-бітові слова перетворюються таким чином:
- ,
де позначає циклічний бітовий зсув, а - бітовий зсув. В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем
Першою причиною вибору такого лінійного перетворення є максимізація лавинного ефекту. Такі таблиці підстановки мають властивість, що зміна кожного вхідного біта призведе до зміни 2 вихідних бітів. Таким чином, кожен вхідний біт відкритого тексту вже через 3 раунди впливає на всі вихідні біти. Аналогічно кожен біт ключа впливає на результат шифрування.
Друга причина полягає в простоті перетворення. Воно може бути реалізоване на будь-якому сучасному процесорі з мінімальними витратами.
Безпека і крипостійкість
При розробці та аналізі алгоритму Serpent не було виявлено будь-яких вразливостей в повній 32-раундовій версії. Але при виборі переможця конкурсу AES, це було справедливо і до решти алгоритмів-фіналістів.
На думку творців Serpent, алгоритм може бути зламаний, тільки якщо буде створена нова потужна .
Варто відзначити, що , якщо буде доведена ефективність її проведення, послабить крипостійкість Serpent.
Література
- ~ rja14/Papers/serpent.pdf|author = Ross Anderson, Eli Biham, Lars Knudsen. Serpent: A Proposal for the Advanced Encryption Standard [ 11 серпня 2004 у Wayback Machine.]
- ~ rja14/Papers/serpentcase.pdf|author = Ross Anderson, Eli Biham and Lars Knudsen. The Case for Serpent [ 11 серпня 2004 у Wayback Machine.]
- ~ rja14/Papers/ventura.pdf|author = Ross Anderson, Eli Biham, Lars Knudsen. Serpent: A Flexible Block Cipher With Maximum Assurance [ 11 серпня 2004 у Wayback Machine.]
- T. Courtois, Josef Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations [недоступне посилання з червня 2019]
Посилання
- ~ rja14/serpent.html Домашня сторінка Serpent [ 11 серпня 2004 у Wayback Machine.]
- # Serpent SCAN's entry for Serpent [Архівовано 28 січня 2012 у WebCite]
- In Pellicano Case, Lessons in Wiretapping Skills [ 27 травня 2012 у Wayback Machine.]
- Конкурс AES [ 10 лютого 2012 у Wayback Machine.]
- Конкурс на новий криптостандарт [ 3 липня 2011 у Wayback Machine.]
- Основні параметри [ 9 березня 2016 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Serpent zmiya deyaki poperedni rozrobki avtoriv tezh nosili nazvi na chest tvarin napriklad Tiger Bear simetrichnij blochnij algoritm shifruvannya rozroblenij Rossom Andersonom Eli Bihamom ta Larsom Knudsenom Algoritm buv odnim z finalistiv 2 go etapu konkursu AES Yak i inshi algoritmi yaki brali uchast u konkursi AES Serpent maye rozmir bloku 128 bit i mozhlivi dovzhini klyucha 128 192 abo 256 bit Algoritm yavlyaye soboyu 32 raundovij shifr na osnovi SP merezhi i pracyuye z blokom z chotiroh 32 bitovih sliv Serpent buv rozroblenij tak sho vsi operaciyi mozhut buti vikonani paralelno vikoristovuyuchi 32 a 1 bitnih potokiv SerpentRozrobnikiRoss Anderson Eli Biham Lars KnudsenUpershe oprilyudnenij1998 r Raundiv32TipSP merezha Pri rozrobci Serpent vikoristovuvavsya konservativnishij pidhid do bezpeki nizh u inshih finalistiv AES proektuvalniki shifru vvazhali sho 16 raundiv dostatno shob protistoyati vidomim vidam kriptoanalizu ale zbilshili chislo raundiv do 32 shob algoritm mig krashe protistoyati she ne vidomim metodam kriptoanalizu Stavshi finalistom konkursu AES algoritm Serpent v rezultati golosuvannya zajnyav 2 misce Shifr Serpent ne zapatentovanij i ye gromadskim nadbannyam Osnovni principiAlgoritm stvoryuvavsya pid gaslom kriptografichnij algoritm 21 stolittya dlya uchasti v konkursi AES Pri stvorenni novogo algoritmu Serpent jogo avtori dotrimuvalisya konservativnih poglyadiv na proektuvannya sho pidtverdzhuyetsya pervisnim rishennyam pro vikoristannya tablic pidstanovki z vidomogo bagato rokiv ranishe algoritmu shifruvannya DES yakij protyagom dovgogo chasu vivchavsya providnimi fahivcyami v oblasti kriptografiyi ta zahistu informaciyi i chiyi vlastivosti i osoblivosti buli dobre vidomi naukovomu svitu Odnochasno z cim do novogo algoritmu mig buti zastosovanij vicherpnij analiz vzhe rozroblenij dlya DES Ne vikoristovuvalisya novi neperevireni i neviprobuvani tehnologiyi pri stvorenni shifru yakij u razi prijnyattya buv bi vikoristanij dlya zahistu velicheznih masiviv finansovih tranzakcij ta uryadovoyi informaciyi Osnovnoyu vimogoyu do uchasnikiv konkursu AES bulo te sho algoritm pretendent povinen buti shvidshim nizh 3DES i nadavati yak minimum takij zhe riven bezpeki vin povinen mati blok danih dovzhinoyu 128 bit i klyuch zavdovzhki 256 bit 16 raundovij Serpent buv bi takim zhe nadijnim yak 3DES ale v dva razi shvidshim Odnak avtori virishili sho dlya bilshoyi nadijnosti varto zbilshiti kilkist raundiv do 32 Ce zrobilo shifr takim zhe shvidkim yak DES i nabagato nadijnishim nizh 3DES Struktura algoritmuAlgoritm Serpent ye SP merezheyu u kotrij ves blok danih dovzhinoyu 128 bit na kozhnomu raundi rozbivayetsya na 4 slova dovzhinoyu 32 biti Vsi znachennya sho vikoristovuyutsya pri shifruvanni ye bitovimi potokami Bitovi indeksi zminyuyut znachennya vid 0 do 31 dlya 32 bitovih sliv vid 0 do 127 dlya 128 bitovih blokiv ta vid 0 do 255 dlya 256 bitovih klyuchiv tosho Dlya vnutrishnih obchislen vsi biti velichin predstavleni v pryamomu poryadku little endian Serpent shifruye vidkritij tekst P dovzhinoyu 128 bit v shifrotekst C dovzhinoyu takih zhe 128 bit za 32 raund za dopomogoyu 33 podklyuchiv K 0 K 32 displaystyle K 0 K 32 dovzhinoyu 128 bit Dovzhina vikoristovuvanogo klyucha mozhe prijmati rizni znachennya ale dlya konkretiki zafiksuyemo yih dovzhinu v 128 192 abo 256 bit Korotki klyuchi dovzhinoyu menshe 256 bit dopovnyuyutsya do povnoyi dovzhini v 256 bit Shifruvannya skladayetsya z nastupnih osnovnih krokiv Pochatkova perestanovka 32 raund kozhen z yakih skladayetsya z operaciyi zmishuvannya z 128 bitovim klyuchem pobitove logichne viklyuchayuche abo tablichna zamina S box i linijne peretvorennya V ostannomu raundi linijne peretvorennya zaminyuyetsya dodatkovim nakladannyam klyucha Kinceva perestanovka Pochatkova i kinceva perestanovki ne mayut bud yakoyi kriptografichnogo znachushosti Voni vikoristovuyutsya dlya sproshennya optimizovanoyi realizaciyi algoritmu i pidvishennya obchislyuvalnoyi efektivnosti Rivnyannya strukturi algoritmu B 0 I P P displaystyle hat B 0 IP P B i 1 R i B i displaystyle hat B i 1 R i hat B i C F P B 32 displaystyle C FP hat B 32 de R i X L S i X K i i 0 30 displaystyle R i X L hat S i X oplus hat K i i 0 30 R i X S i X K i K 32 i 31 displaystyle R i X hat S i X oplus hat K i oplus hat K 32 i 31 de S i displaystyle hat S i ce zastosuvannya tablici pidstanovki S i m o d 8 displaystyle hat S imod8 32 raz paralelno i L displaystyle L linijne peretvorennya Rozshirennya klyuchaYak i inshi algoritmi sho brali uchast v konkursi AES Serpent maye mozhlivi dovzhini klyucha 128 192 abo 256 bit Nepovnij klyuch dovzhinoyu menshe 256 bit dopovnyuyetsya za nastupnim pravilom dodayetsya odinichnij bit sprava za nim slid stilki nulovih bitiv shob dovzhina klyucha stala dorivnyuye 256 bitam Algoritm viboru pidklyuchiv z klyuchaSpochatku pri neobhidnosti klyuch dopovnyuyetsya do 256 bit i peretvoritsya v 33 pidklyucha K 0 K 32 displaystyle K 0 K 32 dovzhinoyu 128 bit nastupnim sposobom Vihidnij klyuch predstavlyayetsya u viglyadi 8 32 bitovih sliv w 8 w 1 displaystyle w 8 w 1 dlya obchislennya promizhnogo klyucha za pravilom W i w i 8 w i 5 w i 3 w i 1 ϕ i lt lt lt 11 displaystyle W i w i 8 w i 5 w i 3 w i 1 phi i lt lt lt 11 de ϕ displaystyle phi ce drobova chastina zolotogo pererizu 5 1 2 displaystyle frac sqrt 5 1 2 abo 0x9e3779b9 v shistnadcyatkovij sistemi chislennya a lt lt lt displaystyle lt lt lt ce ciklichnij bitovij zsuv Raundovi klyuchi obchislyuyutsya z promizhnih klyuchiv vikoristannyam tablic pidstanovki nastupnim chinom k 0 k 1 k 2 k 3 S 3 w 0 w 1 w 2 w 3 displaystyle left k 0 k 1 k 2 k 3 right S 3 left w 0 w 1 w 2 w 3 right k 4 k 5 k 6 k 7 S 2 w 4 w 5 w 6 w 7 displaystyle left k 4 k 5 k 6 k 7 right S 2 left w 4 w 5 w 6 w 7 right k 8 k 9 k 10 k 11 S 1 w 8 w 9 w 10 w 11 displaystyle left k 8 k 9 k 10 k 11 right S 1 left w 8 w 9 w 10 w 11 right k 12 k 13 k 14 k 15 S 0 w 12 w 13 w 14 w 15 displaystyle left k 12 k 13 k 14 k 15 right S 0 left w 12 w 13 w 14 w 15 right k 16 k 17 k 18 k 19 S 7 w 16 w 17 w 18 w 19 displaystyle left k 16 k 17 k 18 k 19 right S 7 left w 16 w 17 w 18 w 19 right displaystyle cdots cdots cdots cdots cdots cdots cdots cdots cdots k 124 k 125 k 126 k 127 S 4 w 124 w 125 w 126 w 127 displaystyle left k 124 k 125 k 126 k 127 right S 4 left w 124 w 125 w 126 w 127 right k 128 k 129 k 130 k 131 S 3 w 128 w 129 w 130 w 131 displaystyle left k 128 k 129 k 130 k 131 right S 3 left w 128 w 129 w 130 w 131 right Promizhni 32 bitovi velichini k j displaystyle k j perenumerovuyutsya i vihodyat 128 bitni pidklyuchi K i k 4 i k 4 i 1 k 4 i 2 k 4 i 3 displaystyle K i left k 4i k 4i 1 k 4i 2 k 4i 3 right Pri standartnomu opisi algoritmu mi povinni zastosuvati pochatkovu perestanovku I P displaystyle IP do raundovogo klyucha shob roztashuvati biti klyucha v nalezhnomu poryadku tobto K i I P K i displaystyle hat K i IP K i Pochatkova perestanovka I P displaystyle IP Dana perestanovka I P displaystyle IP zadayetsya nastupnoyu tabliceyu de vkazuyetsya poziciya na yaku perejde vidpovidnij bit napriklad bit 1 perejde na 32 poziciyu Pochatkova perestanovka I P displaystyle 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 127S boksi tablici zamin V algoritmi Serpent tablici zamin ye 4 bitovimi perestanovkami z vlastivostyami stijkosti do diferencialnogo kriptoanalizu do linijnogo kriptoanalizu i takoyu vlastivistyu sho poryadok vihidnih bit yak funkciyi vhidnih povinen buti maksimalnij tobto buti rivnim 3 Tablicya pidstanovki generuyetsya z vidomih i dobre vivchenih tablic dlya algoritmu DES v iteracijnomu procesi poki ne budut otrimani bazhani diferencialni j linijni vlastivosti Takim chinom stvoryuyetsya 8 tablic pidstanovki Nizhche predstavleni tablici pidstanovki Tablicya pidstanovok S i displaystyle 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 I inversni tablici pidstanovki Tablicya inversnih pidstanovok S i 1 displaystyle 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 2Linijne peretvorennya L T displaystyle LT Linijne peretvorennya L T displaystyle LT zadayetsya nastupnoyu tabliceyu de biti pererahovani vid 0 do 127 napriklad vihidnij 2 bit utvorenij 2 9 15 30 76 84 126 bitami skladenimi za modulem 2 V kozhnomu ryadku opisuyetsya 4 vihidnih biti yaki razom skladayut vhidni dani na odnu tablicyu zamin v nastupnomu raundi Varto zaznachiti sho danij nabir yavlyaye soboyu tablicyu I P L T F P x displaystyle IP LT FP x de L T displaystyle LT i ye te linijne peretvorennya Tablicya linijnogo peretvorennya Linijne peretvorennya L T displaystyle 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 Tablicya zvorotnogo linijnogo peretvorennya yake vikoristovuyetsya pri rozshifrovci Zvorotne linijne peretvorennya I L T displaystyle 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 Kinceva perestanovka F P displaystyle FP Dana perestanovka ye zvorotnoyu do pochatkovoyi tobto F P I P 1 displaystyle FP IP 1 i zadayetsya nastupnoyu tabliceyu Kinceva perestanovka F P displaystyle 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 127Efektivna realizaciyaEfektivna realizaciya algoritmu Bazhannya avtoriv zrobiti algoritm same takim yakim vin ye staye zrozumilim pri rozglyadi jogo efektivnoyi nizkorivnevoyi realizaciyi Serpent buv stvorenij takim chinom shob vsi operaciyi v procesi shifruvannya i rozshifruvannya odnogo bloku mogli buti vikonani paralelno v 32 potokah Do togo zh nizkorivnevij opis algoritmu nabagato prostishij nizh standartnij opis Niyakih pochatkovih i kincevih perestanovok ne potribno Shifruvannya skladayetsya z 32 raundiv Vidkritij tekst ye pershimi promizhnimi danimi B 0 P displaystyle B 0 P Potim vikonuyetsya 32 raundi kozhen i j raund skladayetsya z Zmishuvannya z klyuchem Provoditsya pobitove viklyuchayuche abo promizhnih danih B i displaystyle B i z klyuchem dovzhinoyu 128 bit Zastosuvannya tablic pidstanovki Vhidni dani dovzhinoyu 128 bit podilyayutsya na 4 slova po 32 bita Tablicya pidstanovki realizovana poslidovnistyu logichnih operacij yak yaksho ce bulo b realizovano aparatno zastosovuyetsya do cih 4 slovam V rezultati vihodit 4 vihidnih slova Takim chinom centralnij procesor vikonuye pidstanovku po 32 kopij tablici odnochasno Linijne peretvorennya 32 bitovi slova peretvoryuyutsya takim chinom X 0 X 1 X 2 X 3 S i B i K i displaystyle X 0 X 1 X 2 X 3 S i B i oplus K i X 0 X 0 lt lt lt 13 displaystyle X 0 X 0 lt lt lt 13 X 2 X 2 lt lt lt 3 displaystyle X 2 X 2 lt lt lt 3 X 1 X 1 X 0 X 2 displaystyle X 1 X 1 oplus X 0 oplus X2 X 3 X 3 X 2 X 0 lt lt 3 displaystyle X 3 X 3 oplus X 2 oplus X 0 lt lt 3 X 1 X 1 lt lt lt 1 displaystyle X 1 X 1 lt lt lt 1 X 3 X 3 lt lt lt 7 displaystyle X 3 X 3 lt lt lt 7 X 0 X 0 X 1 X 3 displaystyle X 0 X 0 oplus X 1 oplus X3 X 2 X 2 X 3 X 1 lt lt 7 displaystyle X 2 X 2 oplus X 3 oplus X 1 lt lt 7 X 0 X 0 lt lt lt 5 displaystyle X 0 X 0 lt lt lt 5 X 2 X 2 lt lt lt 22 displaystyle X 2 X 2 lt lt lt 22 B i 1 X 0 X 1 X 2 X 3 displaystyle B i 1 X 0 X 1 X 2 X 3 de lt lt lt displaystyle lt lt lt poznachaye ciklichnij bitovij zsuv a lt lt displaystyle lt lt bitovij zsuv V ostannomu raundi ce linijne peretvorennya zamineno dodatkovim zmishuvannyam z klyuchem B 32 S 7 B 31 K 31 K 32 displaystyle B 32 S 7 B 31 oplus K 31 oplus K 32 Pershoyu prichinoyu viboru takogo linijnogo peretvorennya ye maksimizaciya lavinnogo efektu Taki tablici pidstanovki mayut vlastivist sho zmina kozhnogo vhidnogo bita prizvede do zmini 2 vihidnih bitiv Takim chinom kozhen vhidnij bit vidkritogo tekstu vzhe cherez 3 raundi vplivaye na vsi vihidni biti Analogichno kozhen bit klyucha vplivaye na rezultat shifruvannya Druga prichina polyagaye v prostoti peretvorennya Vono mozhe buti realizovane na bud yakomu suchasnomu procesori z minimalnimi vitratami Bezpeka i kripostijkistPri rozrobci ta analizi algoritmu Serpent ne bulo viyavleno bud yakih vrazlivostej v povnij 32 raundovij versiyi Ale pri vibori peremozhcya konkursu AES ce bulo spravedlivo i do reshti algoritmiv finalistiv Na dumku tvorciv Serpent algoritm mozhe buti zlamanij tilki yaksho bude stvorena nova potuzhna Varto vidznachiti sho yaksho bude dovedena efektivnist yiyi provedennya poslabit kripostijkist Serpent Literatura rja14 Papers serpent pdf author Ross Anderson Eli Biham Lars Knudsen Serpent A Proposal for the Advanced Encryption Standard 11 serpnya 2004 u Wayback Machine rja14 Papers serpentcase pdf author Ross Anderson Eli Biham and Lars Knudsen The Case for Serpent 11 serpnya 2004 u Wayback Machine rja14 Papers ventura pdf author Ross Anderson Eli Biham Lars Knudsen Serpent A Flexible Block Cipher With Maximum Assurance 11 serpnya 2004 u Wayback Machine T Courtois Josef Pieprzyk Cryptanalysis of Block Ciphers with Overdefined Systems of Equations nedostupne posilannya z chervnya 2019 Posilannya rja14 serpent html Domashnya storinka Serpent 11 serpnya 2004 u Wayback Machine Serpent SCAN s entry for Serpent Arhivovano 28 sichnya 2012 u WebCite In Pellicano Case Lessons in Wiretapping Skills 27 travnya 2012 u Wayback Machine Konkurs AES 10 lyutogo 2012 u Wayback Machine Konkurs na novij kriptostandart 3 lipnya 2011 u Wayback Machine Osnovni parametri 9 bereznya 2016 u Wayback Machine