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 в зависимости от размера ключа: 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 = (KB <<< 0) >> 64; k2 = (KB <<< 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 = (KB <<< 30) >> 64; k8 = (KB <<< 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 = (KB <<< 60) >> 64; k16 = (KB <<< 60) & MASK64; k17 = (KL <<< 77) >> 64; k18 = (KL <<< 77) & MASK64; ke5 = (KA <<< 77) >> 64; ke6 = (KA <<< 77) & MASK64; k19 = (KR <<< 94) >> 64; k20 = (KR <<< 94) & MASK64; k21 = (KA <<< 94) >> 64; k22 = (KA <<< 94) & MASK64; k23 = (KL <<< 111) >> 64; k24 = (KL <<< 111) & MASK64; kw3 = (KB <<< 111) >> 64; kw4 = (KB <<< 111) & MASK64;
Шифрование Шифрование происходит по схеме Фейстеля с 18 этапами для 128-битного ключа и 24 этапами для 192- и 256-битных ключей. Каждые 6 этапов применяются функции FL и FLINV. 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, k19); D1 = D1 ^ F(D2, k20); D2 = D2 ^ F(D1, k21); D1 = D1 ^ F(D2, k22); D2 = D2 ^ F(D1, k23); 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 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
Криптостойкость По словам авторов алгоритма:
Мы доказали, что успех дифференциальногоM. Matsui,Linear Cryptanalysis Method for