Network Working Group M. Matsui
Request for Comments: 3713 J. Nakajima
Category: Informational Mitsubishi Electric Corporation
S. Moriai
Sony Computer Entertainment Inc.
April 2004
A Description of the Camellia Encryption Algorithm
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2004). All Rights Reserved.
Abstract
This document describes the Camellia encryption algorithm. Camellia
is a block cipher with 128-bit block size and 128-, 192-, and 256-bit
keys. The algorithm description is presented together with key
scheduling part and data randomizing part.
1. Introduction
1.1. Camellia
Camellia was jointly developed by Nippon Telegraph and Telephone
Corporation and Mitsubishi Electric Corporation in 2000
[CamelliaSpec]. Camellia specifies the 128-bit block size and 128-,
192-, and 256-bit key sizes, the same interface as the Advanced
Encryption Standard (AES). Camellia is characterized by its
suitability for both software and hardware implementations as well as
its high level of security. From a practical viewpoint, it is
designed to enable flexibility in software and hardware
implementations on 32-bit processors widely used over the Internet
and many applications, 8-bit processors used in smart cards,
cryptographic hardware, embedded systems, and so on [CamelliaTech].
Moreover, its key setup time is excellent, and its key agility is
superior to that of AES.
Matsui, et al. Informational [Page 1]
RFC 3713 Camellia Encryption Algorithm April 2004
Camellia has been scrutinized by the wide cryptographic community
during several projects for evaluating crypto algorithms. In
particular, Camellia was selected as a recommended cryptographic
primitive by the EU NESSIE (New European Schemes for Signatures,
Integrity and Encryption) project [NESSIE] and also included in the
list of cryptographic techniques for Japanese e-Government systems
which were selected by the Japan CRYPTREC (Cryptography Research and
Evaluation Committees) [CRYPTREC].
2. Algorithm Description
Camellia can be divided into "key scheduling part" and "data
randomizing part".
2.1. Terminology
The following operators are used in this document to describe the
algorithm.
& bitwise AND operation.
| bitwise OR operation.
^ bitwise exclusive-OR operation.
<< logical left shift operation.
>> logical right shift operation.
<<< left rotation operation.
~y bitwise complement of y.
0x hexadecimal representation.
Note that the logical left shift operation is done with the infinite
data width.
The constant values of MASK8, MASK32, MASK64, and MASK128 are defined
as follows.
MASK8 = 0xff;
MASK32 = 0xffffffff;
MASK64 = 0xffffffffffffffff;
MASK128 = 0xffffffffffffffffffffffffffffffff;
2.2. Key Scheduling Part
In the key schedule part of Camellia, the 128-bit variables of KL and
KR are defined as follows. For 128-bit keys, the 128-bit key K is
used as KL and KR is 0. For 192-bit keys, the leftmost 128-bits of
key K are used as KL and the concatenation of the rightmost 64-bits
of K and the complement of the rightmost 64-bits of K are used as KR.
For 256-bit keys, the leftmost 128-bits of key K are used as KL and
the rightmost 128-bits of K are used as KR.
Matsui, et al. Informational [Page 2]
RFC 3713 Camellia Encryption Algorithm April 2004
128-bit key K:
KL = K; KR = 0;
192-bit key K:
KL = K >> 64;
KR = ((K & MASK64) << 64) | (~(K & MASK64));
256-bit key K:
KL = K >> 128;
KR = K & MASK128;
The 128-bit variables KA and KB are generated from KL and KR as
follows. Note that KB is used only if the length of the secret key
is 192 or 256 bits. D1 and D2 are 64-bit temporary variables. F-
function is described in Section 2.4.
D1 = (KL ^ KR) >> 64;
D2 = (KL ^ KR) & MASK64;
D2 = D2 ^ F(D1, Sigma1);
D1 = D1 ^ F(D2, Sigma2);
D1 = D1 ^ (KL >> 64);
D2 = D2 ^ (KL & MASK64);
D2 = D2 ^ F(D1, Sigma3);
D1 = D1 ^ F(D2, Sigma4);
KA = (D1 << 64) | D2;
D1 = (KA ^ KR) >> 64;
D2 = (KA ^ KR) & MASK64;
D2 = D2 ^ F(D1, Sigma5);
D1 = D1 ^ F(D2, Sigma6);
KB = (D1 << 64) | D2;
The 64-bit constants Sigma1, Sigma2, ..., Sigma6 are used as "keys"
in the F-function. These constant values are, in hexadecimal
notation, as follows.
Sigma1 = 0xA09E667F3BCC908B;
Sigma2 = 0xB67AE8584CAA73B2;
Sigma3 = 0xC6EF372FE94F82BE;
Sigma4 = 0x54FF53A5F1D36F1C;
Sigma5 = 0x10E527FADE682D1D;
Sigma6 = 0xB05688C2B3E6C1FD;
64-bit subkeys are generated by rotating KL, KR, KA, and KB and
taking the left- or right-half of them.
Matsui, et al. Informational [Page 3]
RFC 3713 Camellia Encryption Algorithm April 2004
For 128-bit keys, 64-bit subkeys kw1, ..., kw4, k1, ..., k18,
ke1, ..., ke4 are generated as follows.
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;
For 192- and 256-bit keys, 64-bit subkeys kw1, ..., kw4, k1, ...,
k24, ke1, ..., ke6 are generated as follows.
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;
Matsui, et al. Informational [Page 4]
RFC 3713 Camellia Encryption Algorithm April 2004
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;
2.3. Data Randomizing Part
2.3.1. Encryption for 128-bit keys
128-bit plaintext M is divided into the left 64-bit D1 and the right
64-bit D2.
D1 = M >> 64;
D2 = M & MASK64;
Encryption is performed using an 18-round Feistel structure with FL-
and FLINV-functions inserted every 6 rounds. F-function, FL-function,
and FLINV-function are described in Section 2.4.
D1 = D1 ^ kw1; // Prewhitening
D2 = D2 ^ kw2;
D2 = D2 ^ F(D1, k1); // Round 1
D1 = D1 ^ F(D2, k2); // Round 2
D2 = D2 ^ F(D1, k3); // Round 3
D1 = D1 ^ F(D2, k4); // Round 4
D2 = D2 ^ F(D1, k5); // Round 5
D1 = D1 ^ F(D2, k6); // Round 6
D1 = FL (D1, ke1); // FL
D2 = FLINV(D2, ke2); // FLINV
D2 = D2 ^ F(D1, k7); // Round 7
D1 = D1 ^ F(D2, k8); // Round 8
D2 = D2 ^ F(D1, k9); // Round 9
D1 = D1 ^ F(D2, k10); // Round 10
Matsui, et al. Informational [Page 5]
RFC 3713 Camellia Encryption Algorithm April 2004
D2 = D2 ^ F(D1, k11); // Round 11
D1 = D1 ^ F(D2, k12); // Round 12
D1 = FL (D1, ke3); // FL
D2 = FLINV(D2, ke4); // FLINV
D2 = D2 ^ F(D1, k13); // Round 13
D1 = D1 ^ F(D2, k14); // Round 14
D2 = D2 ^ F(D1, k15); // Round 15
D1 = D1 ^ F(D2, k16); // Round 16
D2 = D2 ^ F(D1, k17); // Round 17
D1 = D1 ^ F(D2, k18); // Round 18
D2 = D2 ^ kw3; // Postwhitening
D1 = D1 ^ kw4;
128-bit ciphertext C is constructed from D1 and D2 as follows.
C = (D2 << 64) | D1;
2.3.2. Encryption for 192- and 256-bit keys
128-bit plaintext M is divided into the left 64-bit D1 and the right
64-bit D2.
D1 = M >> 64;
D2 = M & MASK64;
Encryption is performed using a 24-round Feistel structure with FL-
and FLINV-functions inserted every 6 rounds. F-function, FL-function,
and FLINV-function are described in Section 2.4.
D1 = D1 ^ kw1; // Prewhitening
D2 = D2 ^ kw2;
D2 = D2 ^ F(D1, k1); // Round 1
D1 = D1 ^ F(D2, k2); // Round 2
D2 = D2 ^ F(D1, k3); // Round 3
D1 = D1 ^ F(D2, k4); // Round 4
D2 = D2 ^ F(D1, k5); // Round 5
D1 = D1 ^ F(D2, k6); // Round 6
D1 = FL (D1, ke1); // FL
D2 = FLINV(D2, ke2); // FLINV
D2 = D2 ^ F(D1, k7); // Round 7
D1 = D1 ^ F(D2, k8); // Round 8
D2 = D2 ^ F(D1, k9); // Round 9
D1 = D1 ^ F(D2, k10); // Round 10
D2 = D2 ^ F(D1, k11); // Round 11
D1 = D1 ^ F(D2, k12); // Round 12
D1 = FL (D1, ke3); // FL
D2 = FLINV(D2, ke4); // FLINV
D2 = D2 ^ F(D1, k13); // Round 13
Matsui, et al. Informational [Page 6]
RFC 3713 Camellia Encryption Algorithm April 2004
D1 = D1 ^ F(D2, k14); // Round 14
D2 = D2 ^ F(D1, k15); // Round 15
D1 = D1 ^ F(D2, k16); // Round 16
D2 = D2 ^ F(D1, k17); // Round 17
D1 = D1 ^ F(D2, k18); // Round 18
D1 = FL (D1, ke5); // FL
D2 = FLINV(D2, ke6); // FLINV
D2 = D2 ^ F(D1, k19); // Round 19
D1 = D1 ^ F(D2, k20); // Round 20
D2 = D2 ^ F(D1, k21); // Round 21
D1 = D1 ^ F(D2, k22); // Round 22
D2 = D2 ^ F(D1, k23); // Round 23
D1 = D1 ^ F(D2, k24); // Round 24
D2 = D2 ^ kw3; // Postwhitening
D1 = D1 ^ kw4;
128-bit ciphertext C is constructed from D1 and D2 as follows.
C = (D2 << 64) | D1;
2.3.3. Decryption
The decryption procedure of Camellia can be done in the same way as
the encryption procedure by reversing the order of the subkeys.
That is to say:
128-bit key:
kw1 <-> kw3
kw2 <-> kw4
k1 <-> k18
k2 <-> k17
k3 <-> k16
k4 <-> k15
k5 <-> k14
k6 <-> k13
k7 <-> k12
k8 <-> k11
k9 <-> k10
ke1 <-> ke4
ke2 <-> ke3
192- or 256-bit key:
kw1 <-> kw3
kw2 <-> kw4
k1 <-> k24
k2 <-> k23
k3 <-> k22
Matsui, et al. Informational [Page 7]
RFC 3713 Camellia Encryption Algorithm April 2004
k4 <-> k21
k5 <-> k20
k6 <-> k19
k7 <-> k18
k8 <-> k17
k9 <-> k16
k10 <-> k15
k11 <-> k14
k12 <-> k13
ke1 <-> ke6
ke2 <-> ke5
ke3 <-> ke4
2.4. Components of Camellia
2.4.1. F-function
F-function takes two parameters. One is 64-bit input data F_IN. The
other is 64-bit subkey KE. F-function returns 64-bit data F_OUT.
F(F_IN, KE)
begin
var x as 64-bit unsigned integer;
var t1, t2, t3, t4, t5, t6, t7, t8 as 8-bit unsigned integer;
var y1, y2, y3, y4, y5, y6, y7, y8 as 8-bit unsigned integer;
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;
Matsui, et al. Informational [Page 8]
RFC 3713 Camellia Encryption Algorithm April 2004
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;
return FO_OUT;
end.
SBOX1, SBOX2, SBOX3, and SBOX4 are lookup tables with 8-bit input/
output data. SBOX2, SBOX3, and SBOX4 are defined using SBOX1 as
follows:
SBOX2[x] = SBOX1[x] <<< 1;
SBOX3[x] = SBOX1[x] <<< 7;
SBOX4[x] = SBOX1[x <<< 1];
SBOX1 is defined by the following table. For example, SBOX1[0x3d]
equals 86.
SBOX1:
0 1 2 3 4 5 6 7 8 9 a b c d e f
00: 112 130 44 236 179 39 192 229 228 133 87 53 234 12 174 65
10: 35 239 107 147 69 25 165 33 237 14 79 78 29 101 146 189
20: 134 184 175 143 124 235 31 206 62 48 220 95 94 197 11 26
30: 166 225 57 202 213 71 93 61 217 1 90 214 81 86