Camellia (algoritme)

Camellia
Skaber Mitsubishi
Oprettet 2000
offentliggjort 2000
Nøglestørrelse 128, 192 eller 256 bit
Blokstørrelse 128 bit
Antal runder 18 eller 24
Type Feistel netværk

Camellia er en symmetrisk blokchifferalgoritme ( blokstørrelse 128 bit, nøgle 128, 192, 256 bit ), en af ​​finalisterne i den europæiske NESSIE -konkurrence (sammen med AES og Shacal-2 ), udviklet af japanske virksomheder Nippon Telegraph and Telephone Corporation og Mitsubishi Electric Corporation (indsendt 10. marts 2000 ). Certificeret af den japanske organisation CRYPTREC som en algoritme, der anbefales til industriel og offentlig brug.

Camellia er en videreudvikling af E2 -krypteringsalgoritmen , en af ​​de algoritmer, der er indsendt til AES -konkurrencen og bruger elementer fra MISTY1- algoritmen .

Strukturen af ​​algoritmen er baseret på den klassiske Feistel-kæde med foreløbig og endelig blegning . Sløjfefunktionen bruger en ikke-lineær transformation (S-bokse), en lineær spredningsblok hver 16. cyklus (byte-for-byte XOR -operation ) og en byte-permutation.

Afhængigt af nøglelængden har den 18 cyklusser (128 bit nøgle) eller 24 cyklusser (192 og 256 bit nøgler).

Understøttelse af Camellia-algoritmen blev introduceret i 2008 i Mozilla Firefox 3, men blev deaktiveret i 2014 i Mozilla Firefox 33 [1] . Algoritmen er patenteret, men distribueres under en række gratis licenser, især er den en del af OpenSSL- projektet .

Beskrivelse

Generering af hjælpenøgler

Betegnelse Betyder
& Bitvis OG (OG)
| Bitvis ELLER (ELLER)
^ Bitvist eksklusiv ELLER (XOR)
<< Logisk skift til venstre
>> Logisk højreskift
<<< Drej til venstre
~y Inversion
Konstant Betyder
MASK 8 0xff
MASK32 0xffffffff
MASK64 0xffffffffffffffff
MASK128 0xffffffffffffffffffffffffffffffff
C1 0xA09E667F3BCC908B
C2 0xB67AE8584CAA73B2
C3 0xC6EF372FE94F82BE
C4 0x54FF53A5F1D36F1C
C5 0x10E527FADE682D1D
C6 0xB05688C2B3E6C1FD
1. Nøglen (K) er opdelt i 2 128-bit dele KL og KR.
Nøgle KL KR
128 K 0
192 K >> 64 ((K & MASK64) << 64) | (~(K&MASK64))
256 K >> 128 K&MASK128
2. Beregn 128-bit tal KA og KB (se diagram). Variable D1 og D2 er 64-bit. 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. Beregn ekstra 64-bit nøgler kw1, ..., kw4, k1, ..., k24, ke1, ..., ke6 afhængigt af nøglestørrelsen:
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 og 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;

Kryptering

Kryptering sker i henhold til Feistel-skemaet med 18 trin for en 128-bit nøgle og 24 trin for 192- og 256-bit nøgler. Hvert 6. trin anvendes FL- og FLINV-funktionerne.

128 bit

D1 = M >> 64; // Krypteret besked er opdelt i to 64-bit dele

D2=M&MASK64; D1 = D1^kw1; // Forblegning 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, kel); // 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, kll); 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; // Endelig blegning D1=D1^kw4; C = (D2 << 64) | D1;
192 og 256 bit

D1 = M >> 64; // Krypteret besked er opdelt i to 64-bit dele

D2=M&MASK64; D1 = D1^kw1; // Forblegning 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, kel); // 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, kll); 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; // Endelig blegning D1=D1^kw4; C = (D2 << 64) | D1;

Hjælpefunktioner F, FL, FLINV

F-, FL- og FLINV-funktioner modtager 2 64-bit parametre som input - F_IN data og KE nøgle.
F-funktionen bruger 16 8-bit variable t1, ..., t8, y1, ..., y8 og 1 64-bit variabel. Funktionens output er et 64-bit tal.
FL- og FLINV-funktionerne bruger 4 32-bit variable x1,x2,k1,k2. Funktionens output er et 64-bit tal. FLINV funktion - omvendt til FL

F-funktion

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 funktion

var x1, x2 som 32-bit heltal uden fortegn;

var k1, k2 som 32-bit heltal uden fortegn; 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 funktion

var y1, y2 som 32-bit heltal uden fortegn;

var k1, k2 som 32-bit heltal uden fortegn; y1 = FLINV_IN >> 32; y2 = FLINV_IN&MASK32; k1 = KE >> 32; k2=KE&MASK32; y1 = yl^(y2|k2); y2 = y2 ^ ((yl & k1) <<< 1); FLINV_OUT = (y1 << 32) | y2;

S-blokke

Værdien af ​​SBOX1-funktionen bestemmes ud fra følgende tabel:

0 en 2 3 fire 5 6 7 otte 9 -en b c d e f
0 112 130 44 236 179 39 192 229 228 133 87 53 234 12 174 65
en 35 239 107 147 69 25 165 33 237 fjorten 79 78 29 101 146 189
2 134 184 175 143 124 235 31 206 62 48 220 95 94 197 elleve 26
3 166 225 57 202 213 71 93 61 217 en 90 214 81 86 108 77
fire 139 13 154 102 251 204 176 45 116 atten 43 32 240 177 132 153
5 223 76 203 194 52 126 118 5 109 183 169 49 209 23 fire 215
6 tyve 88 58 97 222 27 17 28 halvtreds femten 156 22 83 24 242 34
7 254 68 207 178 195 181 122 145 36 otte 232 168 96 252 105 80
otte 170 208 160 125 161 137 98 151 84 91 tredive 149 224 255 100 210
9 16 196 0 72 163 247 117 219 138 3 230 218 9 63 221 148
-en 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 ti 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

For eksempel: SBOX1(0x7a)=232.
SBOX2, SBOX3 og SBOX4 er defineret fra SBOX1 som følger:

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

Dekryptering

Dekrypteringsalgoritmen er identisk med kryptering, med den eneste forskel, at hjælpenøglerne byttes i henhold til følgende skema, afhængigt af længden af ​​den originale nøgle:

Nøglestørrelse
128 bit 192 eller 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



Krypteringseksempel

Nøgle: 0123456789abcdeffedcba9876543210

Krypteret besked: 0123456789abcdefeffedcba9876543210

Krypteret besked: 67673138549669730857065648eabe43

Nøgler

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

Sikkerhed

Ifølge forfatterne af algoritmen:

Vi har vist, at succesen med differentiel [2] og lineær [3] kryptoanalyse er næsten umulig i forhold til en fuld 18-runders Camellia-cyklus. Desuden blev Camellia designet til at modstå mere sofistikerede kryptografiske angreb såsom højordens differentielle angreb [4] [5] , interpolationsangreb [6] [7] , "linked-key" angreb [8] [9] , forkortede differentielle angreb [10] [11] og andre

Originaltekst  (engelsk)[ Visskjule] Vi bekræftede, at det er ekstremt usandsynligt, at differentielle og lineære angreb vil lykkes mod hele 18-runders Camellia. Derudover er Camellia designet til at tilbyde sikkerhed mod andre avancerede kryptoanalytiske angreb, herunder højere ordens differentiale angreb, interpolationsangreb, relaterede nøgleangreb, trunkerede differentielle angreb og så videre

Ansøgning

Understøttelse af Camellia blev tilføjet i den endelige version af Mozilla Firefox 3 i 2008 [12] . Senere samme år annoncerede FreeBSD-udviklingsteamet, at understøttelse af denne kryptering også var inkluderet i FreeBSD 6.4-RELEASE. I september 2009 tilføjede GNU Privacy Guard understøttelse af Camellia i version 1.4.10. Derudover inkluderer mange populære sikkerhedsbiblioteker såsom Crypto++, GnuTLS, PolarSSL og OpenSSL [13] også understøttelse af Camellia.

Sammenligning med jævnaldrende

Algoritme Antal logiske elementer Nøgleberegningstid, ns Kryptering/dekrypteringstid, ns Båndbredde, Mb/s
Kryptering/dekryptering Nøgler Samlet mængde
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
Slange 298.533 205.096 503.770 114,07 137,40 931,58
To fisk 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

[fjorten]

Udviklere

Se også

Noter

  1. ↑ Fejl 1036765 - Deaktiver krypteringspakker, der ikke er i "Browser Cipher Suite", som stadig er aktiveret . Hentet 18. september 2015. Arkiveret fra originalen 3. februar 2018.
  2. ↑ M. Matsui , Linear Cryptanalysis Method for DES Cipher - Lecture Notes in Computer Science, s. 386–397, Springer-Verlag, 1994
  3. ↑ E. Biham og A. Shamir , Linear Cryptanalysis Method for DES Cipher - Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1994
  4. ↑ LRKnudsen , "Truncated and Higher Order Differentials," Fast Software Encryption - Second International Workshop, Lecture Notes in ComputerScience 1008, s.196–211, Springer-Verlag, 1995.
  5. ↑ T. Jakobsen og LR Knudsen , The Interpolation Attack on Block Ciphers, Fast Software Encryption, FSE'97, Lecture Notes in Computer Science 1267, s.28–40, Springer-Verlag, 1997.
  6. ↑ T. Jakobsen og LR Knudsen , The Interpolation Attack on Block Ciphers, Fast Software Encryption, FSE'97, Lecture Notes in Computer Science 1267, s.28–40, Springer-Verlag, 1997.
  7. ↑ K. Aoki , "Praktisk evaluering af sikkerhed mod generaliseret interpolationsangreb," 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 og 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 , Truncated and Higher Order Differentials, Fast Software Encryption - Second International Workshop, Lecture Notes in Computer Science 1008, s.196–211, Springer-Verlag, 1995.
  11. ↑ M. Matsui og 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, s.71–80, Springer-Verlag, 1999 .
  12. ↑ Camellia-chiffer tilføjet til Firefox (downlink) . Mozilla Asien . Mozilla (30. juli 2009). Arkiveret fra originalen den 29. februar 2012. 
  13. ↑ NTT (2006-11-08). Open Source Community OpenSSL-projektet vedtager den næste generation af internationale standardcifer "Camellia" udviklet i Japan . Pressemeddelelse . Arkiveret fra originalen 8. marts 2008. Hentet 2008-02-29 .
  14. ↑ Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko Nakajima og Toshio Tokita Camellia: En 128-bit blokcifer, der er egnet til flere platforme - design og analyse

Links

 Symmetriske kryptosystemer
Stream-cifre
Feistel netværk
SP netværk
Andet