Camellia (algoritmi)

Camellia
Luoja	Mitsubishi
Luotu	2000
julkaistu	2000
Avaimen koko	128, 192 tai 256 bittiä
Lohkon koko	128 bittinen
Kierrosten lukumäärä	18 tai 24
Tyyppi	Feistelin verkko

Camellia on japanilaisten Nippon Telegraphin ja Telephone Corporationin kehittämä symmetrinen lohkosalausalgoritmi ( lohkokoko 128 bittiä, avain 128, 192, 256 bittiä ), yksi eurooppalaisen NESSIE-kilpailun finalisteista ( yhdessä AES :n ja Shacal-2 :n kanssa). ja Mitsubishi Electric Corporation (toimitettu 10. maaliskuuta 2000 ). Japanilaisen CRYPTREC -järjestön sertifioima algoritmi, jota suositellaan teollisuuden ja valtion käyttöön.

Camellia on E2 -salausalgoritmin jatkokehitys , yksi AES -kilpailuun lähetetyistä algoritmeista ja jossa käytetään MISTY1- algoritmin elementtejä .

Algoritmin rakenne perustuu klassiseen Feistel-ketjuun, jossa on esi- ja loppuvalkaisu . Silmukkafunktio käyttää epälineaarista muunnosa (S-laatikot), lineaarista sirontalohkoa 16 jakson välein (tavuittain XOR -operaatio ) ja tavupermutaatiota.

Avaimen pituudesta riippuen siinä on 18 jaksoa (128-bittinen avain) tai 24 jaksoa (192- ja 256-bittinen avain).

Camellia-algoritmin tuki otettiin käyttöön vuonna 2008 Mozilla Firefox 3 :ssa, mutta se poistettiin käytöstä vuonna 2014 Mozilla Firefox 33:ssa [1] . Algoritmi on patentoitu, mutta sitä jaetaan useilla ilmaisilla lisensseillä, erityisesti se on osa OpenSSL -projektia .

Kuvaus

Apuavainten luominen

Nimitys	Merkitys
&	Bitittain JA (JA)
|	Bittikohtainen TAI (OR)
^	Bittikohtaisesti poissulkeva TAI (XOR)
<<	Looginen siirto vasemmalle
>>	Looginen siirto oikealle
<<<	Käänny vasemmalle
~y	Inversio

Jatkuva	Merkitys
MASKIA8	0xff
MASKKI32	0xffffffff
MASKIA64	0xffffffffffffffffff
MASKIO 128	0xffffffffffffffffffffffffffffffff
C1	0xA09E667F3BCC908B
C2	0xB67AE8584CAA73B2
C3	0xC6EF372FE94F82BE
C4	0x54FF53A5F1D36F1C
C5	0x10E527FADE682D1D
C6	0xB05688C2B3E6C1FD

1. Avain (K) on jaettu kahteen 128-bittiseen osaan KL ja KR.

Avain	KL	KR
128	K	0
192	K >> 64	((K & MASK64) << 64) | (~(K&MASK64))
256	K >> 128	K&MASK128

2. Laske 128-bittiset luvut KA ja KB (katso kaavio). Muuttujat D1 ja D2 ovat 64-bittisiä. 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. Laske 64-bittiset lisäavaimet kw1, ..., kw4, k1, ..., k24, ke1, ..., ke6 avaimen koosta riippuen:

128 bittinen 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 ja 256 bittiä 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;

Salaus

Salaus tapahtuu Feistelin kaavan mukaan, jossa 128-bittiselle avaimelle on 18 vaihetta ja 192- ja 256-bittisille avaimille 24 vaihetta. FL- ja FLINV-toiminnot otetaan käyttöön 6 askeleen välein.

128 bittinen D1 = M >> 64; // Salattu viesti on jaettu kahteen 64-bittiseen osaan D2=M&MASK64; D1 = D1^kw1; // Esivalkaisu 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, 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; // Lopullinen valkaisu D1 = D1^kw4; C = (D2 << 64) | D1;

192 ja 256 bittiä D1 = M >> 64; // Salattu viesti on jaettu kahteen 64-bittiseen osaan D2=M&MASK64; D1 = D1^kw1; // Esivalkaisu 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, 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; // Lopullinen valkaisu D1 = D1^kw4; C = (D2 << 64) | D1;

Aputoiminnot F, FL, FLINV

F-, FL- ja FLINV-funktiot vastaanottavat 2 64-bittistä parametria syötteenä - F_IN data ja KE-avain.
F-funktio käyttää 16 8-bittistä muuttujaa t1, ..., t8, y1, ..., y8 ja 1 64-bittinen muuttuja. Toiminnon tulos on 64-bittinen luku.
FL- ja FLINV-funktiot käyttävät 4 32-bittistä muuttujaa x1,x2,k1,k2. Toiminnon tulos on 64-bittinen luku. FLINV-toiminto - käänteinen FL:lle

F-toiminto 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-toiminto var x1, x2 32-bittisenä etumerkittömänä kokonaislukuna; var k1, k2 32-bittisenä etumerkittömänä kokonaislukuna; 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-toiminto var y1, y2 32-bittisenä etumerkittömänä kokonaislukuna; var k1, k2 32-bittisenä etumerkittömänä kokonaislukuna; 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-lohkot

SBOX1-funktion arvo määritetään seuraavasta taulukosta:

	0	yksi	2	3	neljä	5	6	7	kahdeksan	9	a	b	c	d	e	f
0	112	130	44	236	179	39	192	229	228	133	87	53	234	12	174	65
yksi	35	239	107	147	69	25	165	33	237	neljätoista	79	78	29	101	146	189
2	134	184	175	143	124	235	31	206	62	48	220	95	94	197	yksitoista	26
3	166	225	57	202	213	71	93	61	217	yksi	90	214	81	86	108	77
neljä	139	13	154	102	251	204	176	45	116	kahdeksantoista	43	32	240	177	132	153
5	223	76	203	194	52	126	118	5	109	183	169	49	209	23	neljä	215
6	kaksikymmentä	88	58	97	222	27	17	28	viisikymmentä	viisitoista	156	22	83	24	242	34
7	254	68	207	178	195	181	122	145	36	kahdeksan	232	168	96	252	105	80
kahdeksan	170	208	160	125	161	137	98	151	84	91	kolmekymmentä	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	kymmenen	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

Esimerkki: SBOX1(0x7a)=232.
SBOX2, SBOX3 ja SBOX4 määritellään SBOX1:stä seuraavasti:

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

Salauksen purku

Salauksen purkualgoritmi on identtinen salauksen kanssa sillä ainoalla erolla, että apuavaimet vaihdetaan seuraavan kaavan mukaan alkuperäisen avaimen pituudesta riippuen:

Avaimen koko
128 bittinen	192 tai 256 bittiä
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

Salausesimerkki

Avain: 0123456789abcdeffedcba9876543210

Salattu viesti: 0123456789abcdefeffedcba9876543210

Salattu viesti: 67673138549669730857065648eabe43

Avaimet 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

Turvallisuus

Algoritmin tekijöiden mukaan:

Olemme osoittaneet, että differentiaalisen [2] ja lineaarisen [3] kryptaanalyysin onnistuminen on lähes mahdotonta täyttä 18-kierrosta Camellia-sykliä vastaan. Lisäksi Camellia on suunniteltu kestämään kehittyneempiä kryptografisia hyökkäyksiä, kuten korkealuokkaisia ​​differentiaalihyökkäyksiä [4] [5] , interpolaatiohyökkäyksiä [6] [7] , "linked-key" -hyökkäyksiä [8] [9] , lyhennettyjä differentiaalihyökkäyksiä. [10] [11] ja muut

Alkuperäinen teksti  (englanniksi)[ näytäpiilottaa] Vahvistimme, että on erittäin epätodennäköistä, että differentiaaliset ja lineaariset hyökkäykset onnistuvat täyttä 18-kierrosta Camelliaa vastaan. Lisäksi Camellia on suunniteltu tarjoamaan suojaus muita edistyneitä kryptanalyyttisiä hyökkäyksiä vastaan, mukaan lukien korkeamman asteen differentiaalihyökkäykset, interpolaatiohyökkäykset, toisiinsa liittyvien avainten hyökkäykset, katkaistu differentiaalihyökkäykset ja niin edelleen.

Sovellus

Camellia-tuki lisättiin Mozilla Firefox 3:n lopulliseen versioon vuonna 2008 [12] . Myöhemmin samana vuonna FreeBSD:n kehitystiimi ilmoitti, että myös FreeBSD 6.4-RELEASE sisältää tuen tälle salaukselle. Syyskuussa 2009 GNU Privacy Guard lisäsi tuen Camellialle versioon 1.4.10. Lisäksi monet suositut tietoturvakirjastot, kuten Crypto++, GnuTLS, PolarSSL ja OpenSSL [13] , sisältävät myös tuen Camellialle.

Vertailu vertaisiin

Algoritmi	Logiikkaelementtien lukumäärä			Avaimen laskentaaika, ns	Salaus/salauksen purkuaika, ns	Kaistanleveys, Mb/s
	Salaus/salauksen purku	Avaimet	Kokonaismäärä
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
Käärme	298,533	205.096	503,770	114.07	137,40	931,58
Kaksi kalaa	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

[neljätoista]

Kehittäjät

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

Katso myös

• Feistelin verkko
• Modulo 2 lisäys

Muistiinpanot

1. ↑ Virhe 1036765 - Poista käytöstä salaussarjat, jotka eivät ole "Browser Cipher Suite" -ehdotuksessa ja jotka ovat edelleen käytössä . Haettu 18. syyskuuta 2015. Arkistoitu alkuperäisestä 3. helmikuuta 2018. (määrätön)
2. ↑ M. Matsui , Linear Cryptanalysis Method for DES Cipher - Lecture Notes in Computer Science, s. 386–397, Springer-Verlag, 1994
3. ↑ E. Biham ja 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 - Toinen kansainvälinen työpaja, Lecture Notes in ComputerScience 1008, s. 196–211, Springer-Verlag, 1995.
5. ↑ T. Jakobsen ja 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 ja 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 , "Practical Evaluation of Security against Generalised Interpolation Attack", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Japani), Vol. E83-A, No.1, s.33–38, 2000.
8. ↑ E. Biham , Uudet kryptaanalyyttisten hyökkäysten tyypit käyttämällä vastaavia avaimia, Journal of Cryptology, Vol.7, No.4, s. 229–246, Springer-Verlag, 1994.
9. ↑ J.Kelsey, B.Schneier ja D.Wagner , "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER ja Triple-DES", Advances in Cryptology - CRYPTO'96, Lecture Notes in Computer Science 1109, s. 237–251, Springer-Verlag, 1996.
10. ↑ LRKnudsen , Typistetyt ja korkeamman asteen erot, nopea ohjelmiston salaus - toinen kansainvälinen työpaja, tietotekniikan luentomuistiinpanot 1008, s. 196–211, Springer-Verlag, 1995.
11. ↑ M. Matsui ja T. Tokita, lohkosalaus E2:n supistetun version kryptaanalyysi, nopea ohjelmiston salaus - 6. kansainvälinen työpaja, FSE'99, Tietojenkäsittelytieteen luentomuistiinpanot 1636, s. 71–80, Springer-Verlag, 1999 .
12. ↑ Camellia-salaus lisätty Firefoxiin (downlink) . Mozilla Aasia . Mozilla (30. heinäkuuta 2009). Arkistoitu alkuperäisestä 29. helmikuuta 2012. (määrätön) 
13. ↑ NTT (2006-11-08). Open Source Community OpenSSL-projekti ottaa käyttöön Japanissa kehitetyn seuraavan sukupolven kansainvälisen vakiosalauksen "Camellia" . Lehdistötiedote . Arkistoitu alkuperäisestä 8. maaliskuuta 2008. Haettu 2008-02-29 .
14. ↑ Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko Nakajima ja Toshio Tokita Camellia : 128-bittinen lohkosalaus, joka sopii useille alustoille – suunnittelu ja analyysi

Linkit

• Camellian virallinen  sivu
• RFC 3713 Camellia   - algoritmin kuvaus
• RFC 3657 Camellia-algoritmin käyttäminen sisällönhallintajärjestelmässä
• RFC 4312 Camellia-algoritmin käyttäminen IPsecissä
•  Ohjelmointiesimerkki _
• Eri algoritmien salausnopeuksien  vertailu

Symmetriset salausjärjestelmät
Suoratoista salauksia	A3 A5 A8 Desim F-FCSR Vilja HC-256 KCipher-2 MIKKI MUGI HAUKI Phelix RC4 Kani TIIVISTE LUMI SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistelin verkko	GOST 28147-89 (Magma) blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra SOPIMUS DES DESX DFC E2 enRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 UusiDES NDS RC5 RC6 SIEMEN Simon Sinopoli jätkä SM4 Speck TEE XTEA XXTEA Raiden RTEA Kolminkertainen DES Kaksi kalaa
SP verkko	Heinäsirkka 3 tapaa ABC AARIA AES (Rijndael) Akelarre Anubis BaseKing Basso Omatic Vyö CRYPTON Timantti 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer esittää Sateenkaari TURVALLISTA HAI NELIÖ Käärme kolme kalaa
Muut	SAMMAKKO NUSH REDOC SC2000 SHACAL CS-Cipher