English

Camellia暗号アルゴリズムの説明
(A Description of the Camellia Encryption Algorithm)

本書の位置づけ

本書は、インターネット・コミュニティに対して情報を提供するものである。 本書は、いかなる種類のインターネット標準を定義するものではない。 本書の配布は、制限されていない。

著作権表記

Copyright (C) The Internet Society (2004). All Rights Reserved.

要旨

本書は、Camellia暗号化アルゴリズムを説明する。 Camelliaは、128bitのブロック・サイズ、および、128、 192および256bitキーでのブロック暗号である。 このアルゴリズムに関する説明は、 キー・スケジューリング部分とデータ・ランダム化部分と共に提示されている。

1. はじめに English

1.1. Camellia English

Camelliaは、2000年、NTTと三菱電機により共同で開発された [CamelliaSpec]。 Camelliaは、128bitのブロック・サイズと 128、 192および256bitキー・サイズを定義する。 これは、AES(Advanced Encryption Standard)と同じインターフェースである。 Camelliaは、ソフトウェアとハードウェアの両方のインプリメンテーションに対する適性、 そして、高度なレベルのセキュリティが特徴である。 実用面からの観点から見ると、Camelliaは、 インターネットや多くのアプリケーションで広く使われている32bitプロセッサ、 スマート・カードで使われる8bitプロセッサ、暗号ハードウェア、 組み込みシステムなどでのソフトウェアおよびハードウェアのインプリメンテーションにおける柔軟性を確保するよう設計されている [CamelliaTech]。 さらに、キーセットアップ時間は特に優れており、 そのキーの「軽快さ」は、AESのものよりずっと優れている。

Camelliaは、暗号アルゴリズムを検証するためのいくつかのプロジェクトで、 広範囲な暗号コミュニティにより精査されている。 特に、Camelliaは、EU NESSIE (New European Schemes for Signatures, Integrity and Encryption)プロジェクト [NESSIE] により「推薦される暗号プリミティブ」として選択されており、また、 日本の電子政府システム(e-Government systems)に対する暗号技術のリストに含まれている。 (これらの技術は、Japan CRYPTREC (Cryptography Research and Evaluation Committees) [CRYPTREC])によって選択されているものである)。

2. アルゴリズムの説明 English

Camelliaは、「キー・スケジューリング部分」と「データ・ランダム化部分」に分割される。

2.1. 用語 English

アルゴリズムを説明するために、本書においては以下の演算子が使われている。

注意： 論理左シフト演算は、無限データ幅で行われる。

MASK8、MASK32、MASK64およびMASK128の定数値は、以下のように定義されている。

MASK8   = 0xff;
MASK32  = 0xffffffff;
MASK64  = 0xffffffffffffffff;
MASK128 = 0xffffffffffffffffffffffffffffffff;
    

2.2. キー・スケジューリング部分 English

Camelliaのキー・スケジューリング部分では、 KLとKRの128bit変数が以下のように定義されている。 128bitキーに関しては、128bitキーであるKがKLとして使われ、 そして、KRは、0となっている。 192bitキーに関しては、キーKの左端128bitがKLとして使われ、 Kの右端64bitと、Kの右端64bitの補数の連結がKRとして使われる。 256bitのキーに関しては、キーKの左端128bitがKLとして使われ、 そして、Kの右端128bitがKRとして使われる。

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;
    

128bit変数であるKAとKBは、以下のようにKLとKRから生成される。 注意：KBは、シークレット・キーの長さが192または256の場合にのみ使われる。 D1とD2は、64bitの仮変数である。 F-関数は、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;
    

64bit定数であるSigma1, Sigma2, ..., Sigma6は、F-関数で「キー」として使われる。 これらの定数値は、以下のようにHEX表記で示される。

Sigma1 = 0xA09E667F3BCC908B;
Sigma2 = 0xB67AE8584CAA73B2;
Sigma3 = 0xC6EF372FE94F82BE;
Sigma4 = 0x54FF53A5F1D36F1C;
Sigma5 = 0x10E527FADE682D1D;
Sigma6 = 0xB05688C2B3E6C1FD;
    

64bitのサブキーは、KL、KR、KAおよびKBを回転(ローテーション)させ、 それらの左端半分または右端半分を取り込むことにより生成される。

128bitキーに対しては、64bitサブキーkw1, ..., kw4, k1, ..., k18,ke1, ..., ke4 が以下のように生成される。

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;
    

192bitおよび256bitキーに対しては、 64bitサブキーkw1, ..., kw4, k1, ..., k24, ke1, ..., ke6が以下のように生成される。

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;
    

2.3. データ・ランダム化部分 English

2.3.1. 128bitキーに対する暗号化 English

128bitのプレーンテキストMは、左側64bitのD1と右側64bit D2に分割される。

D1 = M >> 64;
D2 = M & MASK64;
    

暗号化は、6 round毎に挿入されるFL-およびFLINV-関数で、 18 round Feistel構造を使って行われる。 F-関数、FL-関数およびFLINV-関数は、 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
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;
    

128bit暗号テキスト(ciphertext) Cは、以下のようにD1とD2から成る。

C = (D2 << 64) | D1;
    

2.3.2. 192bitおよび256bitキーに対する暗号化 English

128bitのプレーンテキストMは、 左側64bit D1と右側64bit D2に分割される。

D1 = M >> 64;
D2 = M & MASK64;
    

暗号化は、6 round毎に挿入されるFL-およびFLINV-関数で、 24 round Feistel構造を使って行われる。 F-関数、FL-関数およびFLINV-関数は、 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
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;
    

128bit暗号テキスト(ciphertext) Cは、以下のようにD1とD2から成る。

C = (D2 << 64) | D1;
    

2.3.3. 解読 English

Camelliaの解読プロシージャは、サブキーの順序を逆にするだけで、 暗号化プロシジャと同じ方法で行うことができる。

つまり以下のようになる。

128bitキー：

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
    

192bitまたは256bitキー：

kw1 <-> kw3
kw2 <-> kw4
k1 <-> k24
k2 <-> k23
k3 <-> k22
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. Camelliaのコンポーネント English

2.4.1. F-関数 English

F-関数は、2つのパラメータを取る。 ひとつは、64bitのインプット・データF_INで、他方は、 64bitのサブキーKEである。 F-関数は、64bitのデータ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;
    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およびSBOX4は、 8bitインプット／アウトプット・データを持つルックアップ・テーブルである。 SBOX2、SBOX3およびSBOX4は、SBOX1を使って以下のように定義されている。

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

SBOX1は、以下のテーブルによって定義されている。 例えば、SBOX1[0x3d]は、86となる。

2.4.2. FL-関数およびFLINV-関数 English

FL-関数は、2つのパラメータを取る。 ひとつは、64bitインプット・データFL_INであり、他方は、 64bitサブキーKEである。 FL-関数は、64bitデータFL_OUTを返す。

FL(FL_IN, KE)
begin
    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;
end.
    

FLINV-関数は、FL-関数の逆の関数である。

FLINV(FLINV_IN, KE)
begin
    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;
end.
    

3. オブジェクト識別子 English

Camelliaに対してCBC (Cipher Block Chaining)モードで128bitキーを持つオブジェクト識別子(Object Identifier)は以下となっている。

id-camellia128-cbc OBJECT IDENTIFIER ::=
    { iso(1) member-body(2) 392 200011 61 security(1)
      algorithm(1) symmetric-encryption-algorithm(1) camellia128-cbc(2) }
    

Camelliaに対してCBC (Cipher Block Chaining)モードで192bitキーを持つオブジェクト識別子(Object Identifier)は以下となっている。

id-camellia192-cbc OBJECT IDENTIFIER ::=
    { iso(1) member-body(2) 392 200011 61 security(1)
      algorithm(1) symmetric-encryption-algorithm(1) camellia192-cbc(3) }
    

Camelliaに対してCBC (Cipher Block Chaining)モードで256bitキーを持つオブジェクト識別子(Object Identifier)は以下となっている。

id-camellia256-cbc OBJECT IDENTIFIER ::=
    { iso(1) member-body(2) 392 200011 61 security(1)
      algorithm(1) symmetric-encryption-algorithm(1) camellia256-cbc(4) }
    

上記のアルゴリズムは、初期化ベクター(Initialization Vector (IV))を必要とする。 IVの値を決定するために、 上記のアルゴリズムは以下のようにパラメータを読み込む。

CamelliaCBCParameter ::= CamelliaIV -- Initialization Vector
CamelliaIV ::= OCTET STRING (SIZE(16))
    

これらのオブジェクト・識別子が使われる場合、 プレーンテキストは、RFC2315 [RFC2315] に準じて暗号化の前にパディングされる。

4. セキュリティについての考慮事項 English

暗号解析における技術分野での最近の進歩は目をみはるものがある。 強力な暗号解析テクニック(差分解読法や線形解読法など)に対するセキュリティの定量的評価は、 どのような新しいブロック暗号を設計する場合でも必要不可欠であると考えられている。 Camelliaのセキュリティについては、 我々は最新の暗号解析テクニックを使って評価した。 それにより、我々は、 Camelliaが2^-128以上の確率の差分及び線形特性を持っていないと確認した。 つまり、このことは、差分攻撃や線形攻撃が、 フルの18ラウンドのCamelliaに対して成功するということはまったくといっていいほど不可能であることを意味する。 さらに、Camelliaは、高階差分攻撃、補間攻撃、関連鍵攻撃、 丸め差分攻撃などの高度な暗号解析攻撃に対してもセキュリティを提供するよう設計されている [Camellia]。

5. 参考文献

付録A. Camelliaのサンプル・データ

以下は、Camelliaのテスト・データをHEXで示したものである。

128 bit key Key :
    01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10
    Plaintext : 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10
    Ciphertext: 67 67 31 38 54 96 69 73 08 57 06 56 48 ea be 43

192 bit key Key :
    01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 : 00 11 22 33 44 55 66 77
    Plaintext : 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10
    Ciphertext: b4 99 34 01 b3 e9 96 f8 4e e5 ce e7 d7 9b 09 b9

256 bit key Key :
    01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10 : 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
    Plaintext : 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10
    Ciphertext: 9a cc 23 7d ff 16 d7 6c 20 ef 7c 91 9e 3a 75 09
    

謝辞

本書が作成された時、盛合 志帆は、NTT に勤務していた。

著者のアドレス

Mitsuru Matsui
三菱電機株式会社
Information Technology R&D Center
電話： +81-467-41-2190
Fax： +81-467-41-2185
EMail： matsui＠iss.isl.melco.co.jp

Junko Nakajima
三菱電機株式会社
電話： +81-467-41-2190
Fax： +81-467-41-2185
EMail： june15＠iss.isl.melco.co.jp

盛合 志帆
株式会社ソニー・コンピュータエンタテインメント
電話： +81-3-6438-7523
Fax： +81-3-6438-8629
EMail： shiho＠rd.scei.sony.co.jp
　　　　camellia＠isl.ntt.co.jp (Camellia team)

著作権表記全文

Copyright (C) The Internet Society (2004).

本書は、BCP 78に含まれている権利、 ライセンスおよび制限の対象となっており、 本書で明記されている場合を除いて、 著者がそれらのすべての権利を有するものとする。

本書および本書に含まれている情報は、 「そのまま」の状態で提供されるものとし、寄稿者、 その寄稿者が代表する、または、 それにより後援されている組織(ある場合)、 インターネット・ソサエティ(INTERNET SOCIETY)およびインターネット・エンジニアリング・タスク・フォースは、 明示的にも暗黙のうちにも、そうとは限定されないが、 本書での情報が、いかなる権利をも侵害しないとか、 特定の目的に対して商品性や適性を意図した保証を含むすべての保証を拒否するものである。

知的財産権

IETFは、実装の特許申請、あるいは、 本書に記述された以外の技術の利用、もしくは、 そのような権利のもとで利用可能／利用不可なライセンスの程度について主張される可能性があるいかなる知的財産権もしくは他の権利の正当性もしくは範囲について中立である。； また、そのような権利を識別するためのあらゆる努力をしてきたと表現するものではない。 RFC文書での権利に関してのプロシジャに関する情報は、 BCP 78およびBCP 79で見つけることができる。

IETF事務局に公開されたIPRのコピー、および、 ライセンスが提供されるとするいかなる保証、あるいは、 本仕様の実施者またはユーザによりそのような所有権の汎用ライセンスの使用に対する許可を取得しようとした結果のコピーは、 IETFのオンライン・レポジトリー(http://www.ietf.org/ipr)から得ることができる。

IETFは、 この基準を確立するのに必要であろうテクノロジーに対応する著作権、 特許あるいは特許申請や他の所有権に関して、 関心のある関係者の注意を喚起するものである。 もしそれに関する情報がある場合、IETF(ietf-ipr@ietf.org)に連絡すること。

謝辞

RFCエディター機能に対する資金提供は、現在、 インターネット・ソサエティ(Internet Society)により提供されている。