Camellia (алгоритм)

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
У этого термина существуют и другие значения, см. Camellia.
Camellia
Создатель Mitsubishi, NTT
Создан 2000 г.
Опубликован 2000 г.
Размер ключа 128, 192 или 256 бит
Размер блока 128 бит
Число раундов 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-битные.
Вычисление Ka и Kb
  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  = (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.

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, 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

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;

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[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

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

По словам авторов алгоритма:

Мы доказали, что успех дифференциального[2] и линейного [3] криптоанализов практически невозможен против полного цикла Camellia с 18 этапами. Более того, Camellia был разработан для того, чтобы противостоять более сложным криптографическим атакам, таким как дифференциальные атаки высоких порядков[4][5], интерполяционные атаки[6][7], атаки "на связанных ключах"[8][9], укороченные дифференциальные атаки[10][11] и другие

Применение

Поддержка Camellia была добавлена в финальной версии Mozilla Firefox 3 в 2008 году[12]. Позднее в том же году команда разработчиков FreeBSD объявила, что поддержка данного шифрования также была включена в FreeBSD 6.4-RELEASE. В сентябре 2009 года GNU Privacy Guard добавили поддержку Camellia в версии 1.4.10. Кроме того, многие популярные библиотеки безопасности, такие как Crypto++, GnuTLS, PolarSSL и OpenSSL[13] также включают в себя поддержку 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

[14]

Разработчики

См. также

Примечания

  1. ↑ Bug 1036765 — Disable cipher suites that are not in the «Browser Cipher Suite» proposal that are still enabled. Дата обращения: 18 сентября 2015. Архивировано 3 февраля 2018 года.
  2. ↑ M. Matsui,Linear Cryptanalysis Method for DES Cipher - Lecture Notes in Computer Science, стр.386–397, Springer-Verlag, 1994
  3. ↑ E. Biham and A. Shamir, Linear Cryptanalysis Method for DES Cipher - Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1994
  4. ↑ L.R.Knudsen, “Truncated and Higher Order Differentials,” Fast Software Encryption — Second In-ternational Workshop, Lecture Notes in ComputerScience 1008, pp.196–211, Springer-Verlag, 1995.
  5. ↑ T. Jakobsen and L. R. Knudsen, The Interpolation Attack on Block Ciphers, Fast Software Encryption, FSE’97, Lecture Notes in Computer Sci-ence 1267, pp.28–40, Springer-Verlag, 1997.
  6. ↑ T. Jakobsen and L. R. Knudsen, The Interpolation Attack on Block Ciphers, Fast Software Encryption, FSE’97, Lecture Notes in Computer Science 1267, pp.28–40, Springer-Verlag, 1997.
  7. ↑ K. Aoki, “Practical Evaluation of Security against Generalized Interpolation Attack,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Japan), Vol.E83-A, No.1, pp.33–38, 2000.
  8. ↑ E. Biham, New Types of Cryptanalytic Attacks Using Related Keys, Journal of Cryptology, Vol.7, No.4, pp.229–246, Springer-Verlag, 1994.
  9. ↑ J.Kelsey, B.Schneier and D.Wagner, “Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES,” Advances in Cryptology — CRYPTO’96, Lecture Notes in Computer Science 1109, pp.237–251, Springer-Verlag, 1996.
  10. ↑ L.R.Knudsen, Truncated and Higher Order Dif-ferentials, Fast Software Encryption — Second International Workshop, Lecture Notes in Computer Science 1008, pp.196–211, Springer-Verlag, 1995.
  11. ↑ M. Matsui and T. Tokita, Cryptanalysis of a Reduced Version of the Block Cipher E2, Fast Software Encryption — 6th International Workshop, FSE’99, Lecture Notes in Computer Science 1636, pp.71–80, Springer-Verlag, 1999.
  12. ↑ Camellia cipher added to Firefox (недоступная ссылка). Mozilla in Asia. Mozilla (30 июля 2009). Архивировано 29 февраля 2012 года.
  13. ↑ NTT (2006-11-08). The Open Source Community OpenSSL Project Adopts the Next Generation International Standard Cipher "Camellia" Developed in Japan. Пресс-релиз. Архивировано из первоисточника 8 марта 2008. Проверено 2008-02-29.
  14. ↑ 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

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Camellia_(алгоритм)&oldid=12903973