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. Алгоритм запатентований, однак поширюється під рядом вільних ліцензій, зокрема, є частиною проекту 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 біт 192 і 256 біт 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; 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 біт 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); D2 = D2 ^ kw3; // Фінальне забілювання D1 = D1 ^ kw4; C = (D2 << 64) | D1; 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 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-функція FL-функція FLINV-функція 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; 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; 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;

S — блоки Значення функції 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=ae71c3d55ba6bf1d k=169240a795f89256 k=a2b3c4d5e6f7ff6e k=5d4c3b2a19080091 k=e1eaadd35f8e8b49 k=2053cafc492b5738 k=79bdffdb97530eca k=8642002468acf135 k=d7e3a2d24814f2bf k=00123456789abcde k=d169240a795f8уцкв k=6ae71c3d55ba6bf1 k=1d950c840048d159 k=e26af37bffb72ea6 k=e57e2495ab9c70f5 k=56e9afc745a49029 kw=0123456789abcdef kw=fedcba9876543210 kw=492b5738e1eaadd3 kw=5f8e8b492053cafc ke=56e9afc745a49029 ke=e57e2495ab9c70f5 ke=97530eca86420024 ke=68acf13579bdffdb

Криптостійкість

Застосування Підтримка Camellia була додана у фінальній версії Mozilla Firefox 3 в 2008 році. Пізніше в тому ж році команда розробників FreeBSD оголосила, що підтримка даного шифрування також була включена в FreeBSD 6.4-RELEASE. У вересні 2009 року GNU Privacy Guard додали підтримку Camellia у версії 1.4.10. Крім того, багато популярних бібліотек безпеки, такі як Crypto++, GnuTLS, PolarSSL і OpenSSL також включають в себе підтримку 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 and Toshio Tokita Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms — Design and Analysis

Розробники

Kazumaro Aoki Tetsuya Ichikawa Masayuki Kanda Mitsuru Matsui Shiho Moriai Junko Nakajima Toshio Tokita Nippon Telegraph and Telephone Corporation Mitsubishi Electric Corporation

Див. також

Мережа Фейстеля Додавання по модулю 2

Примітки

Посилання