Camellia (алгоритм)
Розробники | Mitsubishi, NTT |
---|---|
Уперше оприлюднений | 2000 рік |
Раундів | 18 або 24 |
Тип | Мережа Фейстеля |
Camellia — алгоритм симетричного блочного шифрування (розмір блоку 128 біт ключа 128, 192, 256 біт), один із фіналістів європейського конкурсу NESSIE (поряд з AES і Shacal-2), розробка японських компаній Nippon Telegraph and Telephone Corporation і Mitsubishi Electric Corporation (представлений 10 березня 2000 р.). Сертифікований японською організацією CRYPTREC, як рекомендований для промислового й державного використання алгоритм.
Camellia є подальшим розвитком алгоритму шифрування E2, одного з алгоритмів, представлених на конкурсі AES з використанням елементів алгоритму MISTY1.
Структура алгоритму заснована на класичному ланцюгу Фейстеля з попереднім й фінальним забілюванням. Циклічна функція використовує нелінійне перетворення (S-блоки), блок лінійного розсіювання кожні 16 циклів (побайтова операція XOR) і байтову перестановку.
В залежності від довжини ключа, має 18 циклів (128 бітний ключ), або 24 циклу (192 і 256 бітний ключ).
Підтримка алгоритму Camellia введена в 2008 році в браузері Mozilla Firefox 3, однак відключена в 2014 році в Mozilla Firefox 33[1]. Алгоритм запатентований, однак поширюється під рядом вільних ліцензій, зокрема, є частиною проекту OpenSSL.
Позначення | Значення |
---|---|
& | Побітове І (AND) |
| | Побітове АБО (OR) |
^ | Побітове виключне АБО (XOR) |
<< | Логічний зсув вліво |
>> | Логічний зсув вправо |
<<< | Циклічний зсув вліво |
~y | Інверсія |
Константа | Значення |
---|---|
MASK8 | 0xff |
MASK32 | 0xffffffff |
MASK64 | 0xffffffffffffffff |
MASK128 | 0xffffffffffffffffffffffffffffffff |
C1 | 0xA09E667F3BCC908B |
C2 | 0xB67AE8584CAA73B2 |
C3 | 0xC6EF372FE94F82BE |
C4 | 0x54FF53A5F1D36F1C |
C5 | 0x10E527FADE682D1D |
C6 | 0xB05688C2B3E6C1FD |
- 1. Ключ (До) розбивається на 2 128-бітні частини KL і KR.
Ключ | KL | KR |
---|---|---|
128 | K | 0 |
192 | K >> 64 | ((K & MASK64) << 64) | (~(K & MASK64)) |
256 | K >> 128 | K & MASK128 |
- 2. Обчислюємо 128-бітні числа KA і KB (див. схему). Змінні D1 і D2 64-бітні.
D1 = (KL ^ KR) >> 64; D2 = (KL ^ KR) & MASK64; D2 = D2 ^ F(D1, C1); D1 = D1 ^ F(D2, C2); D1 = D1 ^ (KL >> 64); D2 = D2 ^ (KL & MASK64); D2 = D2 ^ F(D1, C3); D1 = D1 ^ F(D2, C4); KA = (D1 << 64) | D2; D1 = (KA ^ KR) >> 64; D2 = (KA ^ KR) & MASK64; D2 = D2 ^ F(D1, C5); D1 = D1 ^ F(D2, C6); KB = (D1 << 64) | D2;
- 3. Обчислюємо допоміжні 64-бітові ключі kw1, …, kw4, k1, …, k24, ke1, …, ke6 в залежності від розміру ключа:
128 біт
kw1 = (KL <<< 0) >> 64; kw2 = (KL <<< 0) & MASK64; k1 = (KA <<< 0) >> 64; k2 = (KA <<< 0) & MASK64; k3 = (KL <<< 15) >> 64; k4 = (KL <<< 15) & MASK64; k5 = (KA <<< 15) >> 64; k6 = (KA <<< 15) & MASK64; ke1 = (KA <<< 30) >> 64; ke2 = (KA <<< 30) & MASK64; k7 = (KL <<< 45) >> 64; k8 = (KL <<< 45) & MASK64; k9 = (KA <<< 45) >> 64; k10 = (KL <<< 60) & MASK64; k11 = (KA <<< 60) >> 64; k12 = (KA <<< 60) & MASK64; ke3 = (KL <<< 77) >> 64; ke4 = (KL <<< 77) & MASK64; k13 = (KL <<< 94) >> 64; k14 = (KL <<< 94) & MASK64; k15 = (KA <<< 94) >> 64; k16 = (KA <<< 94) & MASK64; k17 = (KL <<< 111) >> 64; k18 = (KL <<< 111) & MASK64; kw3 = (KA <<< 111) >> 64; kw4 = (KA <<< 111) & MASK64; |
192 і 256 біт
kw1 = (KL <<< 0) >> 64; kw2 = (KL <<< 0) & MASK64; k1 = (КБ <<< 0) >> 64; k2 = (КБ <<< 0) & MASK64; k3 = (KR <<< 15) >> 64; k4 = (KR <<< 15) & MASK64; k5 = (KA <<< 15) >> 64; k6 = (KA <<< 15) & MASK64; ke1 = (KR <<< 30) >> 64; ke2 = (KR <<< 30) & MASK64; k7 = (КБ <<< 30) >> 64; k8 = (КБ <<< 30) & MASK64; k9 = (KL <<< 45) >> 64; k10 = (KL <<< 45) & MASK64; k11 = (KA <<< 45) >> 64; k12 = (KA <<< 45) & MASK64; ke3 = (KL <<< 60) >> 64; ke4 = (KL <<< 60) & MASK64; k13 = (KR <<< 60) >> 64; k14 = (KR <<< 60) & MASK64; k15 = (КБ <<< 60) >> 64; k16 = (КБ <<< 60) & MASK64; k17 = (KL <<< 77) >> 64; k18 = (KL <<< 77) & MASK64; ke5 = (KA <<< 77) >> 64; ke6 = (KA <<< 77) & MASK64; к19 = (KR <<< 94) >> 64; k20 = (KR <<< 94) & MASK64; k21 = (KA <<< 94) >> 64; k22 = (KA <<< 94) & MASK64; к23 = (KL <<< 111) >> 64; k24 = (KL <<< 111) & MASK64; kw3 = (КБ <<< 111) >> 64; kw4 = (КБ <<< 111) & MASK64; |
Шифрування відбувається за схемою Фейстеля з 18 етапами для 128-бітного ключа і 24 етапами для 192 і 256-бітних ключів. Кожні 6 етапів застосовуються функції FL і FLINV.
128 біт
D1 = M >> 64; // Зашифроване повідомлення ділиться на дві 64-бітні частини D2 = M & MASK64; D1 = D1 ^ kw1; // Попереднє забілювання D2 = D2 ^ kw2; D2 = D2 ^ F(D1, k1); D1 = D1 ^ F(D2, k2); D2 = D2 ^ F(D1, k3); D1 = D1 ^ F(D2, k4); D2 = D2 ^ F(D1, k5); D1 = D1 ^ F(D2, k6); D1 = FL (D1, ke1); // FL D2 = FLINV(D2, ke2); // FLINV D2 = D2 ^ F(D1, k7); D1 = D1 ^ F(D2, k8); D2 = D2 ^ F(D1, k9); D1 = D1 ^ F(D2, k10); D2 = D2 ^ F(D1, k11); D1 = D1 ^ F(D2, k12); D1 = FL (D1, ke3); // FL D2 = FLINV(D2, ke4); // FLINV D2 = D2 ^ F(D1, k13); D1 = D1 ^ F(D2, k14); D2 = D2 ^ F(D1, k15); D1 = D1 ^ F(D2, k16); D2 = D2 ^ F(D1, k17); D1 = D1 ^ F(D2, k18); D2 = D2 ^ kw3; // Фінальне забілювання D1 = D1 ^ kw4; C = (D2 << 64) | D1; |
192 і 256 біт
D1 = M >> 64; // Зашифроване повідомлення ділиться на дві 64-бітні частини D2 = M & MASK64; D1 = D1 ^ kw1; // Попереднє забілювання D2 = D2 ^ kw2; D2 = D2 ^ F(D1, k1); D1 = D1 ^ F(D2, k2); D2 = D2 ^ F(D1, k3); D1 = D1 ^ F(D2, k4); D2 = D2 ^ F(D1, k5); D1 = D1 ^ F(D2, k6); D1 = FL (D1, ke1); // FL D2 = FLINV(D2, ke2); // FLINV D2 = D2 ^ F(D1, k7); D1 = D1 ^ F(D2, k8); D2 = D2 ^ F(D1, k9); D1 = D1 ^ F(D2, k10); D2 = D2 ^ F(D1, k11); D1 = D1 ^ F(D2, k12); D1 = FL (D1, ke3); // FL D2 = FLINV(D2, ke4); // FLINV D2 = D2 ^ F(D1, k13); D1 = D1 ^ F(D2, k14); D2 = D2 ^ F(D1, k15); D1 = D1 ^ F(D2, k16); D2 = D2 ^ F(D1, k17); D1 = D1 ^ F(D2, k18); D1 = FL (D1, ke5); // FL D2 = FLINV(D2, ke6); // FLINV D2 = D2 ^ F(D1, к19); D1 = D1 ^ F(D2, k20); D2 = D2 ^ F(D1, k21); D1 = D1 ^ F(D2, k22); D2 = D2 ^ F(D1, к23); D1 = D1 ^ F(D2, k24); D2 = D2 ^ kw3; // Фінальне забілювання D1 = D1 ^ kw4; C = (D2 << 64) | D1; |
F-, FL — і FLINV — функції на вхід отримують 2 64-бітних параметра — дані F_IN і ключ KE. Функція F використовує 16 8-бітових змінних t1, …, t8, y1, …, y8 і 1 64-бітну змінну. На виході функції 64-бітове число. Функції FL і FLINV використовують 4 32-бітні змінні x1,x2,k1,k2. На виході функції 64-бітове число. Функція FLINV — обернена до FL
F-функція
x = F_IN ^ KE; t1 = x >> 56; t2 = (x >> 48) & MASK8; t3 = (x >> 40) & MASK8; t4 = (x >> 32) & MASK8; t5 = (x >> 24) & MASK8; t6 = (x >> 16) & MASK8; t7 = (x >> 8) & MASK8; t8 = x & MASK8; t1 = SBOX1[t1]; t2 = SBOX2[t2]; t3 = SBOX3[t3]; t4 = SBOX4[t4]; t5 = SBOX2[t5]; t6 = SBOX3[t6]; t7 = SBOX4[t7]; t8 = SBOX1[t8]; y1 = t1 ^ t3 ^ t4 ^ t6 ^ t7 ^ t8; y2 = t1 ^ t2 ^ t4 ^ t5 ^ t7 ^ t8; y3 = t1 ^ t2 ^ t3 ^ t5 ^ t6 ^ t8; y4 = t2 ^ t3 ^ t4 ^ t5 ^ t6 ^ t7; y5 = t1 ^ t2 ^ t6 ^ t7 ^ t8; y6 = t2 ^ t3 ^ t5 ^ t7 ^ t8; y7 = t3 ^ t4 ^ t5 ^ t6 ^ t8; y8 = t1 ^ t4 ^ t5 ^ t6 ^ t7; F_OUT = (y1 << 56) | (y2 << 48) | (y3 << 40) | (y4 << 32)| (y5 << 24) | (y6 << 16) | (y7 << 8) | y8; |
FL-функція
var x1, x2 as 32-bit unsigned integer; var k1, k2 as 32-bit unsigned integer; x1 = FL_IN >> 32; x2 = FL_IN & MASK32; k1 = KE >> 32; k2 = KE & MASK32; x2 = x2 ^ ((x1 & k1) <<< 1); x1 = x1 ^ (x2 | k2); FL_OUT = (x1 << 32) | x2; |
FLINV-функція
var y1, y2 as 32-bit unsigned integer; var k1, k2 as 32-bit unsigned integer; y1 = FLINV_IN >> 32; y2 = FLINV_IN & MASK32; k1 = KE >> 32; k2 = KE & MASK32; y1 = y1 ^ (y2 | k2); y2 = y2 ^ ((y1 & k1) <<< 1); FLINV_OUT = (y1 << 32) | y2; |
Значення функції SBOX1 визначається із наступної таблиці:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 112 | 130 | 44 | 236 | 179 | 39 | 192 | 229 | 228 | 133 | 87 | 53 | 234 | 12 | 174 | 65 |
1 | 35 | 239 | 107 | 147 | 69 | 25 | 165 | 33 | 237 | 14 | 79 | 78 | 29 | 101 | 146 | 189 |
2 | 134 | 184 | 175 | 143 | 124 | 235 | 31 | 206 | 62 | 48 | 220 | 95 | 94 | 197 | 11 | 26 |
3 | 166 | 225 | 57 | 202 | 213 | 71 | 93 | 61 | 217 | 1 | 90 | 214 | 81 | 86 | 108 | 77 |
4 | 139 | 13 | 154 | 102 | 251 | 204 | 176 | 45 | 116 | 18 | 43 | 32 | 240 | 177 | 132 | 153 |
5 | 223 | 76 | 203 | 194 | 52 | 126 | 118 | 5 | 109 | 183 | 169 | 49 | 209 | 23 | 4 | 215 |
6 | 20 | 88 | 58 | 97 | 222 | 27 | 17 | 28 | 50 | 15 | 156 | 22 | 83 | 24 | 242 | 34 |
7 | 254 | 68 | 207 | 178 | 195 | 181 | 122 | 145 | 36 | 8 | 232 | 168 | 96 | 252 | 105 | 80 |
8 | 170 | 208 | 160 | 125 | 161 | 137 | 98 | 151 | 84 | 91 | 30 | 149 | 224 | 255 | 100 | 210 |
9 | 16 | 196 | 0 | 72 | 163 | 247 | 117 | 219 | 138 | 3 | 230 | 218 | 9 | 63 | 221 | 148 |
a | 135 | 92 | 131 | 2 | 205 | 74 | 144 | 51 | 115 | 103 | 246 | 243 | 157 | 127 | 191 | 226 |
b | 82 | 155 | 216 | 38 | 200 | 55 | 198 | 59 | 129 | 150 | 111 | 75 | 19 | 190 | 99 | 46 |
c | 233 | 121 | 167 | 140 | 159 | 110 | 188 | 142 | 41 | 245 | 249 | 182 | 47 | 253 | 180 | 89 |
d | 120 | 152 | 6 | 106 | 231 | 70 | 113 | 186 | 212 | 37 | 171 | 66 | 136 | 162 | 141 | 250 |
e | 114 | 7 | 185 | 85 | 248 | 238 | 172 | 10 | 54 | 73 | 42 | 104 | 60 | 56 | 241 | 164 |
f | 64 | 40 | 211 | 123 | 187 | 201 | 67 | 193 | 21 | 227 | 173 | 244 | 119 | 199 | 128 | 158 |
Для прикладу: SBOX1(0x7a)=232. SBOX2, SBOX3 і SBOX4 визначаються з SBOX1 наступним чином:
SBOX2[x] = SBOX1[x] <<< 1; SBOX3[x] = SBOX1[x] <<< 7; SBOX4[x] = SBOX1[x <<< 1];
Алгоритм розшифрування ідентичний шифруванню, з тим лише розходженням, що допоміжні ключі міняються місцями за наступною схемою, в залежності від довжини вихідного ключа:
Розмір ключа | |
---|---|
128 біт | 192 чи 256 біт |
kw1 <-> kw3 | kw1 <-> kw3 |
kw2 <-> kw4 | kw2 <-> kw4 |
k1 <-> k18 | k1 <-> k24 |
k2 <-> k17 | k2 <-> k23 |
k3 <-> k16 | k3 <-> k22 |
k4 <-> k15 | k4 <-> k21 |
k5 <-> k14 | k5 <-> k20 |
k6 <-> k13 | k6 <-> k19 |
k7 <-> k12 | k7 <-> k18 |
k8 <-> k11 | k8 <-> k17 |
k9 <-> k10 | k9 <-> k16 |
k10 <-> k15 | |
k11 <-> k14 | |
k12 <-> k13 | |
ke1 <-> ke4 | ke1 <-> ke6 |
ke2 <-> ke3 | ke2 <-> ke5 |
ke3 <-> ke4 |
Ключ: 0123456789abcdeffedcba9876543210
Зашифриване повідомлення: 0123456789abcdeffedcba9876543210
Зашифроване повідомлення: 67673138549669730857065648eabe43
Ключі
k[1]=ae71c3d55ba6bf1d k[2]=169240a795f89256 k[3]=a2b3c4d5e6f7ff6e k[4]=5d4c3b2a19080091 k[5]=e1eaadd35f8e8b49 k[6]=2053cafc492b5738 k[7]=79bdffdb97530eca k[8]=8642002468acf135 k[9]=d7e3a2d24814f2bf k[10]=00123456789abcde k[11]=d169240a795f8уцкв k[12]=6ae71c3d55ba6bf1 k[13]=1d950c840048d159 k[14]=e26af37bffb72ea6 k[15]=e57e2495ab9c70f5 k[16]=56e9afc745a49029 kw[1]=0123456789abcdef kw[2]=fedcba9876543210 kw[3]=492b5738e1eaadd3 kw[4]=5f8e8b492053cafc ke[1]=56e9afc745a49029 ke[2]=e57e2495ab9c70f5 ke[3]=97530eca86420024 ke[4]=68acf13579bdffdb |
Підтримка Camellia була додана у фінальній версії Mozilla Firefox 3 в 2008 році[2]. Пізніше в тому ж році команда розробників FreeBSD оголосила, що підтримка даного шифрування також була включена в FreeBSD 6.4-RELEASE. У вересні 2009 року GNU Privacy Guard додали підтримку Camellia у версії 1.4.10. Крім того, багато популярних бібліотек безпеки, такі як Crypto++, GnuTLS, PolarSSL і OpenSSL[3] також включають в себе підтримку Camellia.
Алгоритм | Кількість логічних елементів | Час обчислення ключів, нс | Час шифрування/дешифрування, нс | Пропускна здатність, Mb/s | ||
---|---|---|---|---|---|---|
Шифрування/дешифрування | Ключі | Повна кількість | ||||
DES | 42,204 | 12,201 | 54,405 | - | 55.11 | 1161.31 |
Triple-DES | 124,888 | 23,207 | 128,147 | - | 157.09 | 407.40 |
MARS | 690,654 | 2,245,096 | 2,935,754 | 1740.99 | 567.49 | 225.55 |
RC6 | 741,641 | 901,382 | 1,643,037 | 2112.26 | 627.57 | 203.96 |
Rijndael | 518,508 | 93,708 | 612,834 | 57.39 | 65.64 | 1950.03 |
Serpent | 298,533 | 205,096 | 503,770 | 114.07 | 137.40 | 931.58 |
Twofish | 200,165 | 231,682 | 431,857 | 16.38 | 324.80 | 394.08 |
Camellia | 216,911 | 55,907 | 272,819 | 24.36 | 109.35 | 1170.55 |
- Kazumaro Aoki
- Tetsuya Ichikawa
- Masayuki Kanda
- Mitsuru Matsui
- Shiho Moriai
- Junko Nakajima
- Toshio Tokita
- Nippon Telegraph and Telephone Corporation
- Mitsubishi Electric Corporation
- ↑ Bug 1036765 — Disable cipher suites that are not in the «Browser Cipher Suite» proposal that are still enabled. Архів оригіналу за 3 лютого 2018. Процитовано 21 квітня 2018.
- ↑ Camellia cipher added to Firefox. Mozilla in Asia. Mozilla. 30 липня 2009. Архів оригіналу за 29 лютого 2012.
- ↑ The Open Source Community OpenSSL Project Adopts the Next Generation International Standard Cipher "Camellia" Developed in Japan (Пресреліз). NTT. 8 листопада 2006. Архів оригіналу за 8 березня 2008. Процитовано 29 лютого 2008.
- ↑ Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko Nakajima and Toshio Tokita Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms — Design and Analysis
- Офіційна сторінка Camellia [Архівовано 6 травня 2018 у Wayback Machine.] (англ.)
- RFC 3713 Опис алгоритму Camellia (англ.)
- RFC 3657 Використання алгоритму Camellia в CMS
- RFC 4312 Використання алгоритму Camellia в IPsec
- Приклад програмної реалізації [Архівовано 26 вересня 2011 у Wayback Machine.] (англ.)
- Порівняння швидкості шифрування різних алгоритмів [Архівовано 15 жовтня 2008 у Wayback Machine.] (англ.)