Kamélie (algoritmus)

Kamélie
Tvůrce Mitsubishi
Vytvořeno 2000
zveřejněno 2000
Velikost klíče 128, 192 nebo 256 bitů
Velikost bloku 128 bit
Počet kol 18 nebo 24
Typ Síť Feistel

Camellia je symetrický algoritmus blokové šifry (velikost bloku 128 bitů, klíč 128, 192, 256 bitů ), jeden z finalistů evropské soutěže NESSIE (spolu s AES a Shacal-2 ), vyvinutý japonskými společnostmi Nippon Telegraph a Telephone Corporation. a Mitsubishi Electric Corporation (předloženo 10. března 2000 ). Certifikováno japonskou organizací CRYPTREC jako algoritmus doporučený pro průmyslové a vládní použití.

Camellia je dalším vývojem šifrovacího algoritmu E2 , jednoho z algoritmů přihlášených do soutěže AES a využívajícího prvky algoritmu MISTY1 .

Struktura algoritmu je založena na klasickém Feistelově řetězci s předběžným a konečným bělením . Funkce smyčky používá nelineární transformaci (S-boxy), blok lineárního rozptylu každých 16 cyklů ( operace XOR bajt po bajtu ) a bajtovou permutaci.

V závislosti na délce klíče má 18 cyklů (128bitový klíč) nebo 24 cyklů (192 a 256bitový klíč).

Podpora pro algoritmus Camellia byla představena v roce 2008 v Mozilla Firefox 3, ale byla deaktivována v roce 2014 v Mozilla Firefox 33 [1] . Algoritmus je patentován, ale distribuován pod řadou bezplatných licencí, zejména je součástí projektu OpenSSL .

Popis

Generování pomocného klíče

Označení Význam
& Bitové AND (AND)
| Bitové NEBO (NEBO)
^ Bitový exkluzivní OR (XOR)
<< Logický posun doleva
>> Logický posun doprava
<<< Otočit doleva
~y Inverze
Konstantní Význam
MASKA8 0xff
MASKA32 0xffffffff
MASKA64 0xffffffffffffffff
MASKA128 0xffffffffffffffffffffffffffffffff
C1 0xA09E667F3BCC908B
C2 0xB67AE8584CAA73B2
C3 0xC6EF372FE94F82BE
C4 0x54FF53A5F1D36F1C
C5 0x10E527FADE682D1D
C6 0xB05688C2B3E6C1FD
1. Klíč (K) je rozdělen na 2 128bitové části KL a KR.
Klíč KL KR
128 K 0
192 K >> 64 ((K & MASK64) << 64) | (~(K&MASK64))
256 K >> 128 K&MASK128
2. Vypočítejte 128bitová čísla KA a KB (viz schéma). Proměnné D1 a D2 jsou 64bitové. D1 = (KL ^ KR) >> 64; D2=(KL^KR)&MASK64; D2 = D2^ F(D1, Cl); Dl = Dl^ F(D2, C2); D1=D1^(KL>>64); D2=D2^(KL&MASK64); D2 = D2^ F(D1, C3); Dl = Dl^ F(D2, C4); KA = (D1 << 64) | D2; D1 = (KA ^ KR) >> 64; D2=(KA^KR)&MASK64; D2 = D2^ F(D1, C5); Dl = Dl^ F(D2, C6); KB = (D1 << 64) | D2; 3. Vypočítejte pomocné 64bitové klíče kw1, ..., kw4, k1, ..., k24, ke1, ..., ke6 v závislosti na velikosti klíče:
128 bit

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 a 256 bitů

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;

Šifrování

Šifrování probíhá podle Feistelova schématu s 18 stupni pro 128bitový klíč a 24 stupni pro 192bitové a 256bitové klíče. Každých 6 kroků se použijí funkce FL a FLINV.

128 bit

Dl = M> 64; // Šifrovaná zpráva je rozdělena na dvě 64bitové části

D2=M&MASK64; D1 = D1^kw1; // Předbělení D2 = D2^kw2; D2 = D2^ F(D1, k1); D1 = D1 ^ F(D2, k2); D2 = D2^ F(Dl, k3); Dl = Dl^ F(D2, k4); D2 = D2^ F(Dl, k5); Dl = Dl^ F(D2, k6); D1 = FL(D1, ke1); // FL D2 = FLINV(D2, ke2); // FLINV D2 = D2^ F(Dl, k7); Dl = Dl^ F(D2, k8); D2 = D2^ F(Dl, k9); D1 = D1 ^ F(D2, k10); D2 = D2^ F(Dl, kll); D1 = D1 ^ F(D2, k12); D1 = FL(D1, ke3); // FL D2 = FLINV(D2, ke4); // FLINV D2 = D2^ F(Dl, k13); Dl = Dl^ F(D2, k14); D2 = D2^ F(Dl, k15); Dl = Dl^ F(D2, k16); D2 = D2^ F(Dl, k17); Dl = Dl^ F(D2, k18); D2 = D2^kw3; // Konečné bělení D1=D1^kw4; C = (D2 << 64) | D1;
192 a 256 bitů

Dl = M> 64; // Šifrovaná zpráva je rozdělena na dvě 64bitové části

D2=M&MASK64; D1 = D1^kw1; // Předbělení D2 = D2^kw2; D2 = D2^ F(D1, k1); D1 = D1 ^ F(D2, k2); D2 = D2^ F(Dl, k3); Dl = Dl^ F(D2, k4); D2 = D2^ F(Dl, k5); Dl = Dl^ F(D2, k6); D1 = FL(D1, ke1); // FL D2 = FLINV(D2, ke2); // FLINV D2 = D2^ F(Dl, k7); Dl = Dl^ F(D2, k8); D2 = D2^ F(Dl, k9); D1 = D1 ^ F(D2, k10); D2 = D2^ F(Dl, kll); D1 = D1 ^ F(D2, k12); D1 = FL(D1, ke3); // FL D2 = FLINV(D2, ke4); // FLINV D2 = D2^ F(Dl, k13); Dl = Dl^ F(D2, k14); D2 = D2^ F(Dl, k15); Dl = Dl^ F(D2, k16); D2 = D2^ F(Dl, k17); Dl = Dl^ F(D2, k18); D1 = FL(D1, ke5); // FL D2 = FLINV(D2, ke6); // FLINV D2 = D2^ F(Dl, k19); Dl = Dl^ F(D2, k20); D2 = D2^ F(Dl, k21); Dl = Dl^ F(D2, k22); D2 = D2^ F(Dl, k23); Dl = Dl^ F(D2, k24); D2 = D2^kw3; // Konečné bělení D1=D1^kw4; C = (D2 << 64) | D1;

Pomocné funkce F, FL, FLINV

Funkce F, FL a FLINV přijímají 2 64bitové parametry jako vstup - data F_IN a klíč KE.
Funkce F používá 16 8bitových proměnných t1, ..., t8, y1, ..., y8 a 1 64bitovou proměnnou. Výstupem funkce je 64bitové číslo.
Funkce FL a FLINV používají 4 32bitové proměnné x1,x2,k1,k2. Výstupem funkce je 64bitové číslo. Funkce FLINV - inverzní k FL

F funkce

x = F_IN^KE;

ti = 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; ti = 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;
Funkce FL

var x1, x2 jako 32bitové celé číslo bez znaménka;

var k1, k2 jako 32bitové celé číslo bez znaménka; 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;
Funkce FLINV

var y1, y2 jako 32bitové celé číslo bez znaménka;

var k1, k2 jako 32bitové celé číslo bez znaménka; 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-bloky

Hodnota funkce SBOX1 je určena z následující tabulky:

0 jeden 2 3 čtyři 5 6 7 osm 9 A b C d E F
0 112 130 44 236 179 39 192 229 228 133 87 53 234 12 174 65
jeden 35 239 107 147 69 25 165 33 237 čtrnáct 79 78 29 101 146 189
2 134 184 175 143 124 235 31 206 62 48 220 95 94 197 jedenáct 26
3 166 225 57 202 213 71 93 61 217 jeden 90 214 81 86 108 77
čtyři 139 13 154 102 251 204 176 45 116 osmnáct 43 32 240 177 132 153
5 223 76 203 194 52 126 118 5 109 183 169 49 209 23 čtyři 215
6 dvacet 88 58 97 222 27 17 28 padesáti patnáct 156 22 83 24 242 34
7 254 68 207 178 195 181 122 145 36 osm 232 168 96 252 105 80
osm 170 208 160 125 161 137 98 151 84 91 třicet 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 deset 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

Například: SBOX1(0x7a)=232.
SBOX2, SBOX3 a SBOX4 jsou definovány z SBOX1 takto:

SBOX2[x] = SBOX1[x] <<< 1; SBOX3[x] = SBOX1[x] <<< 7; SBOX4[x] = SBOX1[x <<< 1];

Dešifrování

Algoritmus dešifrování je totožný s šifrováním, pouze s tím rozdílem, že pomocné klíče jsou prohozeny podle následujícího schématu v závislosti na délce původního klíče:

Velikost klíče
128 bit 192 nebo 256 bitů
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



Příklad šifrování

Klíč: 0123456789abcdeffedcba9876543210

Šifrovaná zpráva: 0123456789abcdefeffedcba9876543210

Šifrovaná zpráva: 67673138549669730857065648eabe43

Klíče

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]=d169240a795f8ukv 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

Zabezpečení

Podle autorů algoritmu:

Ukázali jsme, že úspěch diferenciální [2] a lineární [3] kryptoanalýzy je téměř nemožný proti plnému 18-kolovému cyklu Camellia. Camellia byla navíc navržena tak, aby odolala sofistikovanějším kryptografickým útokům, jako jsou diferenciální útoky vyššího řádu [4] [5] , interpolační útoky [6] [7] , útoky "linked-key" [8] [9] , zkrácené diferenciální útoky [10] [11] a další

Původní text  (anglicky)[ zobrazitskrýt] Potvrdili jsme, že je extrémně nepravděpodobné, že by diferenciální a lineární útoky uspěly proti celé 18kolové Camellii. Kromě toho byla Camellia navržena tak, aby nabízela zabezpečení proti dalším pokročilým kryptoanalytickým útokům včetně diferenciálních útoků vyššího řádu, interpolačních útoků, útoků souvisejících klíčů, zkrácených diferenciálních útoků atd.

Aplikace

Podpora pro Camellia byla přidána do finální verze Mozilla Firefox 3 v roce 2008 [12] . Později téhož roku vývojový tým FreeBSD oznámil, že podpora pro toto šifrování byla také zahrnuta do FreeBSD 6.4-RELEASE. V září 2009 GNU Privacy Guard přidal podporu pro Camellia ve verzi 1.4.10. Kromě toho mnoho populárních bezpečnostních knihoven, jako je Crypto++, GnuTLS, PolarSSL a OpenSSL [13] , také obsahuje podporu pro Camellia.

Srovnání s vrstevníky

Algoritmus Počet logických prvků Doba výpočtu klíče, ns Doba šifrování/dešifrování, ns Šířka pásma, Mb/s
Šifrování/dešifrování Klíče Celkové množství
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
Had 298,533 205,096 503,770 114,07 137,40 931,58
Dvě ryby 200,165 231,682 431,857 16,38 324,80 394,08
Kamélie 216,911 55,907 272,819 24,36 109,35 1170,55

[čtrnáct]

Vývojáři

Viz také

Poznámky

  1. ↑ Chyba 1036765 – Zakažte šifrovací sady, které nejsou v návrhu „Browser Cipher Suite“, které jsou stále povolené . Získáno 18. září 2015. Archivováno z originálu 3. února 2018.
  2. ↑ M. Matsui , Metoda lineární kryptoanalýzy pro šifru DES – poznámky k přednáškám z informatiky, str. 386–397, Springer-Verlag, 1994
  3. ↑ E. Biham a A. Shamir , Metoda lineární kryptoanalýzy pro šifru DES – Diferenciální kryptoanalýza standardu pro šifrování dat, Springer-Verlag, 1994
  4. ↑ LRKnudsen , “Truncated and Higher Order Differentials,” Fast Software Encryption – Second International Workshop, Lecture Notes in ComputerScience 1008, pp.196–211, Springer-Verlag, 1995.
  5. ↑ T. Jakobsen a LR Knudsen , The Interpolation Attack on Block Ciphers, Fast Software Encryption, FSE'97, Lecture Notes in Computer Science 1267, pp.28–40, Springer-Verlag, 1997.
  6. ↑ T. Jakobsen a LR 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 , „Praktické hodnocení bezpečnosti proti útoku generalizované interpolace“, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Japonsko), svazek E83-A, č. 1, s. 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 a 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, s.237–251, Springer-Verlag, 1996.
  10. ↑ LRKnudsen , Zkrácené diferenciály a diferenciály vyššího řádu, Rychlé softwarové šifrování – druhý mezinárodní workshop, Poznámky k přednáškám z informatiky 1008, s. 196–211, Springer-Verlag, 1995.
  11. ↑ M. Matsui a T. Tokita , Kryptoanalýza redukované verze blokové šifry E2, Rychlé softwarové šifrování – 6. mezinárodní seminář, FSE'99, Poznámky k přednáškám z informatiky 1636, s. 71–80, Springer-Verlag, 1999 .
  12. ↑ Šifra kamélie přidána do Firefoxu (downlink) . Mozilla Asie . Mozilla (30. července 2009). Archivováno z originálu 29. února 2012. 
  13. ↑ NTT (2006-11-08). Open Source Community OpenSSL Project přijímá mezinárodní standardní šifru nové generace „Camellia“ vyvinutou v Japonsku . Tisková zpráva . Archivováno z originálu 8. března 2008. Získáno 29. 2. 2008 .
  14. ↑ Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko Nakajima a Toshio Tokita Camellia: 128bitová bloková šifra vhodná pro více platforem – návrh a analýza

Odkazy

 Symetrické kryptosystémy
Streamové šifry
Síť Feistel
Síť SP
jiný