Network Working Group R. Rivest Request for Comments: 2268 MIT Laboratory for Computer Science Category: Informational and RSA Data Security, Inc. March 1998 RC2(r)暗号化アルゴリズム このメモの位置付け このメモは、インターネット・コミュニティに情報を提供するものである。 インターネット標準を規定するものではない。このメモの配布は無制限である。 著作権表示 Copyright (C) The Internet Society (1998). All Rights Reserved. 1. はじめに このメモは、RSA研究所のテクニカルノートである。すなわち、インターネット コミュニティへの情報提供である。 このメモでは、RC2と呼ばれる、慣用の(秘密鍵方式の)ブロック暗号化アルゴ リズムを記述する。これは、DESに代わる暗号として提案されているものと考え てよい。入出力ブロックサイズは、それぞれ64ビットである。鍵のサイズは 1バイトから最大128バイトまで可変であるが、現在の実装では8バイトを使用 している。 アルゴリズムは、16ビットのマイクロプロセッサ上で実装するのが簡単なように 設計されている。IBM AT上では、(鍵の拡張が完了していたとしたとき、)暗号化 処理はDESのおよそ2倍の速さで実行される。 1.1 アルゴリズムの詳細 ここでは、「ワード」は16ビットを表す。記号'+'は、2の補数表現での加算を 表す。記号'&'は、ビットごとの"and"演算を表す。用語"XOR"は、ビットごと の"排他的論理和"演算を表す。記号'~'は、ビットごとの補数演算を表す。記号 '^'は、指数演算を表す。用語"MOD"は、法演算を表す。 本アルゴリズムには、次の3つのアルゴリズムが含まれている。 鍵拡張。これは(可変長の)鍵を受け取り、64ワードからなる拡張鍵 K[0],...,K[63] を出力する。 暗号化。これはワード R[0], ..., R[3] に格納された64ビットのデータを受け 取り、「その場で」暗号化する(演算結果はR[0], ..., R[3]に格納されたまま である)。 復号。暗号化演算の逆演算。 2. 鍵拡張 ここでは、16ビットから構成されるワード演算と同時に、8ビットから構成され るバイト演算も行うため、鍵バッファを表すための次の2つの表記法を使用する。 ワード演算においては、鍵バッファを K[0], ..., K[63] とする。それぞれの K[i]は、16ビットのワードである。 バイト演算においては、鍵バッファを L[0], ..., L[127] とする。それぞれの L[i]は、8ビットのバイトである。 これらは同じデータバッファの見方の違いである。常に以下のことが成立する。 K[i] = L[2*i] + 256*L[2*i+1] (それぞれのKワードの下位バイトは、高位バイトより前に現れることに注意。) まず、Tバイトの鍵が提供されたとする。Tは、1 <= T <= 128 の範囲にあるもの とする(現在の実装では、T=8を使用している)。しかしTに関わらず、アルゴリ ズムは最大の有効鍵長として、T1ビットの長さを持つものとする。すなわち、 鍵の検索空間は2^(8*T)、または2^T1、の小さい方の値となる。 鍵拡張アルゴリズムの目的は、鍵バッファを変更することにより、拡張された 鍵の各ビットの値が、入力された鍵のすべてのビットの値に影響を受けるように させることである。 鍵拡張アルゴリズムではまず、提供されたTバイトの鍵を鍵バッファ L[0], ..., L[T-1] に格納する。 そしてビットを単位とする有効鍵長T1に基づいて、バイトを単位とする有効鍵長T8 とマスクTMを計算する。この計算は以下のように行う。 T8 = (T1+7)/8; TM = 255 MOD 2^(8 + T1 - 8*T8); これによりTM は、最下位ビットから 8 - (8*T8 - T1) 個のビット列となる。 例えば、有効鍵長が64ビットであるときは、T1 = 64、T8 = 8、TM = 0xffと なる。有効鍵長が63ビットのときは、T1 = 63、T8 = 8、TM = 0x7fとなる。 ここで、PITABLE[0], ..., PITABLE[255]を、PI = 3.14159...の列に基づく 「ランダムな」バイト配列とする。正確には、配列PITABLEは、0, ..., 255 の値を取る、ランダム順列である。16進数で表したPITABLEを以下に示す。 0 1 2 3 4 5 6 7 8 9 a b c d e f 00: d9 78 f9 c4 19 dd b5 ed 28 e9 fd 79 4a a0 d8 9d 10: c6 7e 37 83 2b 76 53 8e 62 4c 64 88 44 8b fb a2 20: 17 9a 59 f5 87 b3 4f 13 61 45 6d 8d 09 81 7d 32 30: bd 8f 40 eb 86 b7 7b 0b f0 95 21 22 5c 6b 4e 82 40: 54 d6 65 93 ce 60 b2 1c 73 56 c0 14 a7 8c f1 dc 50: 12 75 ca 1f 3b be e4 d1 42 3d d4 30 a3 3c b6 26 60: 6f bf 0e da 46 69 07 57 27 f2 1d 9b bc 94 43 03 70: f8 11 c7 f6 90 ef 3e e7 06 c3 d5 2f c8 66 1e d7 80: 08 e8 ea de 80 52 ee f7 84 aa 72 ac 35 4d 6a 2a 90: 96 1a d2 71 5a 15 49 74 4b 9f d0 5e 04 18 a4 ec a0: c2 e0 41 6e 0f 51 cb cc 24 91 af 50 a1 f4 70 39 b0: 99 7c 3a 85 23 b8 b4 7a fc 02 36 5b 25 55 97 31 c0: 2d 5d fa 98 e3 8a 92 ae 05 df 29 10 67 6c ba c9 d0: d3 00 e6 cf e1 9e a8 2c 63 16 01 3f 58 e2 89 a9 e0: 0d 38 34 1b ab 33 ff b0 bb 48 0c 5f b9 b1 cd 2e f0: c5 f3 db 47 e5 a5 9c 77 0a a6 20 68 fe 7f c1 ad 鍵拡張演算は、以下の2つのループと中間ステップから構成されている。 for i = T, T+1, ..., 127 do L[i] = PITABLE[L[i-1] + L[i-T]]; L[128-T8] = PITABLE[L[128-T8] & TM]; for i = 127-T8, ..., 0 do L[i] = PITABLE[L[i+1] XOR L[i+T8]]; (最初のループでは、L[i-1]とL[i-T]の加算は、法256で実行される。) 「有効鍵」は、L[128-T8],..., L[127]の値で構成される。中間ステップに おけるビットごとの“and"演算により、L[128-T8]分の検索空間が減少するため、 鍵ビットの有効数はT1である。拡張された鍵は、提供された鍵 K に関わらず、 有効鍵のビット数のみに依存する。拡張された鍵自体は、暗号化または復号 の処理の際に修正されることはない。そのため実装において、大きなブロックを 暗号化または復号するときには、鍵の拡張は1度だけでよい。 3. 暗号化アルゴリズム 暗号化処理は、基本となる「ミックス」と「マッシュ」演算から定義される。 ここで、"x rol k"は、kビットだけ左に回転した16ビットワードxを表す。 シフトによりはみ出した最上位ビットは、最下位ビットに入れられる。 3.1 R[i]のミックス 基本となる「R[i]のミックス」処理は、次のように定義される。ここで、s[0] は1、s[1]は2、s[2]は3、s[3]は5であり、配列Rのインデックスは、常に"法4" であると考える。そのため、もしiが0であるときには、R[i-1]はR[3]を意味 する(これらの値は「ラップラウンド」されるため、Rは常に、0から3までの インデックス値を取る)。 R[i] = R[i] + K[j] + (R[i-1] & R[i-2]) + ((~R[i-1]) & R[i-3]); j = j + 1; R[i] = R[i] rol s[i]; すなわち、鍵ワードK[j]の値はR[i]に加算され、jが1つ進められる。そして R[i-1]は「合成」ワードを作成するのに使用され、そしてR[i]に加算される。 合成ワードは、R[i-1]が 1 の場合R[i-2]に等しく、R[i-1]が 0 の場合R[i-3]に 等しい。そしてR[i]はs[i]ビットだけ左に回転される(左回転によりはみ出した 左端ビットは右から詰められる)。ここで、jは「グローバル」変数であるので、 K[j]は常に、「ミックス」処理においてはまだ使用されていない拡張鍵部分の、 最初のワードとなる。 3.2 ミキシングラウンド ミキシングラウンドは、次の処理から構成される。 R[0] のミックス R[1] のミックス R[2] のミックス R[3] のミックス 3.3 R[i]のマッシュ 基本となる「R[i]のマッシュ」処理は、次のように定義される(ここでは、Rの インデックスとして、先の表記を使用する)。 R[i] = R[i] + K[R[i-1] & 63]; すなわち、R[i]は拡張鍵の中の1つのワードと加算されることにより「マッシュ」 される。使用される鍵ワードは、R[i-1]の下位6ビットの値を鍵配列Kのイン デックスとして使用することにより決定される。 3.4 マッシングラウンド マッシングラウンドは、次の処理から構成される。 R[0] のマッシュ R[1] のマッシュ R[2] のマッシュ R[3] のマッシュ 3.5 暗号化処理 すべての暗号化処理は、以下のように表すことが出来る。ここでjはグローバルな 整数変数で、ミキシング処理において使用されている。 1. 64ビットの入力値を格納するために、ワードR[0], ..., R[3]を 初期化する。 2. 鍵の拡張を行い、ワードK[0], ..., K[63]の定義を行う。 3. jを0に初期化する。 4. ミキシングラウンドを5回実行する。 5. マッシングラウンドを1回実行する。 6. ミキシングラウンドを6回実行する。 7. マッシングラウンドを1回実行する。 8. ミキシングラウンドを5回実行する。 それぞれのミキシングラウンドでは、4つの鍵ワードを使用する。また、全部で 16のミキシングラウンドがある。そのため、それぞれの鍵ワードはミキシング ラウンドにおいて1度しか使用されない。マッシングラウンドでは、データに依存 した方法で、8つの鍵ワードを参照する(これらは繰り返し使用され、また実際 に参照されるワードは、それぞれの暗号化処理ごとに異なる)。 4. 復号アルゴリズム 復号処理は、暗号化処理における「ミックス」と「マッシュ」処理を元に戻す 基本的な処理で定義される。それらを、「R-ミックス」と「R-マッシュ」と呼ぶ ことにする(R-は、reverseすなわち逆演算を示す)。 ここで、"x ror k"は、16ビットのワード x を右に k ビット回転することを 示す。シフトによりはみ出した最下位ビットは、最上位ビットに入れられる。 4.1 R[i]の R-ミックス 基本となる「R[i]のR-ミックス」処理は、次のように定義される。ここで、s[0] は1、s[1]は2、s[2]は3、s[3]は5であり、配列Rのインデックスは、常に"法4" であると考える。そのため、もしiが0であるときには、R[i-1]はR[3]を意味 する(これらの値は「ラップラウンド」されるため、Rは常に、0から3までの インデックス値を取る)。 R[i] = R[i] ror s[i]; R[i] = R[i] - K[j] - (R[i-1] & R[i-2]) - ((~R[i-1]) & R[i-3]); j = j - 1; すなわち、R[i]はs[i]ビットだけ右に回転される(右回転によりはみ出したR[i] の右端ビットは左端から詰められる)。ここで、jは「グローバル」変数である ので、K[j]は常に、「R-ミックス」処理においてはまだ使用されていない拡張鍵 部分の、最も大きなインデックスを持つワードとなる。鍵ワードK[j]の値はR[i] から減算され、jが1つ減らされる。そして、R[i-1]は「合成」ワードを作成する のに使用され、そしてR[i]から減算される。合成ワードは、R[i-1]が 1 の場合 R[i-2]に等しく、R[i-1]が 0 の場合R[i-3]に等しい。 4.2 R-ミキシングラウンド R-ミキシングラウンドは、次の処理から構成される。 R[3] のR-ミックス R[2] のR-ミックス R[1] のR-ミックス R[0] のR-ミックス 4.3 R[i]のR-マッシュ 基本となる「R[i]のR-マッシュ」処理は、次のように定義される(ここでは、 Rのインデックスとして、先の表記を使用する)。 R[i] = R[i] - K[R[i-1] & 63]; すなわち、R[i]は拡張鍵の中の1つのワード値を減算することにより「R-マッシュ」 される。使用される鍵ワードは、R[i-1]の下位6ビットの値を鍵配列Kのイン デックスとして使用することにより決定される。 4.4 R-マッシングラウンド R-マッシングラウンドは、次の処理から構成される。 R[3] のR-マッシュ R[2] のR-マッシュ R[1] のR-マッシュ R[0] のR-マッシュ 4.5 復号処理 すべての復号処理は、以下のように表すことが出来る。ここでjは、R-ミキシング 処理において使用されている、グローバルな整数変数である。 1. 64ビットの暗号文を格納するために、ワードR[0], ..., R[3]を 初期化する。 2. 鍵の拡張を行い、ワードK[0], ..., K[63]の定義を行う。 3. jを63に初期化する。 4. R-ミキシングラウンドを5回実行する。 5. R-マッシングラウンドを1回実行する。 6. R-ミキシングラウンドを6回実行する。 7. R-マッシングラウンドを1回実行する。 8. R-ミキシングラウンドを5回実行する。 5. テストベクトル RC2を使用した暗号化におけるテストベクトルは以下に示される。 すべてのデータは16進法で表されている。 鍵長(バイト) = 8 有効鍵長(ビット) = 63 鍵 = 00000000 00000000 平文 = 00000000 00000000 暗号文 = ebb773f9 93278eff 鍵長(バイト) = 8 有効鍵長(ビット) = 64 鍵 = ffffffff ffffffff 平文 = ffffffff ffffffff 暗号文 = 278b27e4 2e2f0d49 鍵長(バイト) = 8 有効鍵長(ビット) = 64 鍵 = 30000000 00000000 平文 = 10000000 00000001 暗号文 = 30649edf 9be7d2c2 鍵長(バイト) = 1 有効鍵長(ビット) = 64 鍵 = 88 平文 = 00000000 00000000 暗号文 = 61a8a244 adacccf0 鍵長(バイト) = 7 有効鍵長(ビット) = 64 鍵 = 88bca90e 90875a 平文 = 00000000 00000000 暗号文 = 6ccf4308 974c267f 鍵長(バイト) = 16 有効鍵長(ビット) = 64 鍵 = 88bca90e 90875a7f 0f79c384 627bafb2 平文 = 00000000 00000000 暗号文 = 1a807d27 2bbe5db1 鍵長(バイト) = 16 有効鍵長(ビット) = 128 鍵 = 88bca90e 90875a7f 0f79c384 627bafb2 平文 = 00000000 00000000 暗号文 = 2269552a b0f85ca6 鍵長(バイト) = 33 有効鍵長(ビット) = 129 鍵 = 88bca90e 90875a7f 0f79c384 627bafb2 16f80a6f 85920584 c42fceb0 be255daf 1e 平文 = 00000000 00000000 暗号文 = 5b78d3a4 3dfff1f1 6. RC2 アルゴリズムのオブジェクト識別子 暗号ブロックチェーン(CBC)モードでのRC2のオブジェクト識別子は、 以下のようなものである。 rc2CBC OBJECT IDENTIFIER ::= {iso(1) member-body(2) US(840) rsadsi(113549) encryptionAlgorithm(3) 2} RC2-CBC は、以下のパラメータを取る。 RC2-CBCParameter ::= CHOICE { iv IV, params SEQUENCE { version RC2Version, iv IV } } ここで、 IV ::= OCTET STRING -- 8 オクテット RC2Version ::= INTEGER -- 1-1024の範囲 CBCモードでのRC2には、2つのパラメータがある。8バイトの初期ベクトル(IV)と、 RC2の暗号化/復号に使用される有効鍵ビットの数から間接的に指定される、 1-1024の範囲の値を持つバージョン番号である。 有効鍵ビットとバージョン番号の関係は以下のようなものである。 1. 有効鍵ビットEKBの数が1-255の範囲にある時には、バージョン番号は Table[EKB]で与えられる。256バイトの変換テーブルTable[]は以下で 定義される。Table[]では、0-255の間の数字の並びを定義している。 RC2の鍵拡張フェーズにおいてのテーブルとは異なるものであること に注意。 2. 有効鍵ビットEKBの数が256-1024の範囲にある時には、バージョン番号 は単純にEKBである。 RC2の有効鍵ビットのデフォルト値は32である。RC2-CBCが32ビットの有効 鍵で実行される場合には、パラメータは、versionとIVを含んだSEQUENCE ではなく、単にIVのみを提供すべきである。 0 1 2 3 4 5 6 7 8 9 a b c d e f 00: bd 56 ea f2 a2 f1 ac 2a b0 93 d1 9c 1b 33 fd d0 10: 30 04 b6 dc 7d df 32 4b f7 cb 45 9b 31 bb 21 5a 20: 41 9f e1 d9 4a 4d 9e da a0 68 2c c3 27 5f 80 36 30: 3e ee fb 95 1a fe ce a8 34 a9 13 f0 a6 3f d8 0c 40: 78 24 af 23 52 c1 67 17 f5 66 90 e7 e8 07 b8 60 50: 48 e6 1e 53 f3 92 a4 72 8c 08 15 6e 86 00 84 fa 60: f4 7f 8a 42 19 f6 db cd 14 8d 50 12 ba 3c 06 4e 70: ec b3 35 11 a1 88 8e 2b 94 99 b7 71 74 d3 e4 bf 80: 3a de 96 0e bc 0a ed 77 fc 37 6b 03 79 89 62 c6 90: d7 c0 d2 7c 6a 8b 22 a3 5b 05 5d 02 75 d5 61 e3 a0: 18 8f 55 51 ad 1f 0b 5e 85 e5 c2 57 63 ca 3d 6c b0: b4 c5 cc 70 b2 91 59 0d 47 20 c8 4f 58 e0 01 e2 c0: 16 38 c4 6f 3b 0f 65 46 be 7e 2d 7b 82 f9 40 b5 d0: 1d 73 f8 eb 26 c7 87 97 25 54 b1 28 aa 98 9d a5 e0: 64 6d 7a d4 10 81 44 ef 49 d6 ae 2e dd 76 5c 2f f0: a7 1c c9 09 69 9a 83 cf 29 39 b9 e9 4c ff 43 ab A. 知的所有権表示 RC2は、RSA Data Security,Inc.の登録商標である。RSAが著作権を持つRC2 ソフトウエアは、RSA Data Security,Inc.のライセンスの元で利用可能で ある。 B. 著者のアドレス Ron Rivest RSA Laboratories 100 Marine Parkway, #500 Redwood City, CA 94065 USA Phone: (650) 595-7703 EMail: rsa-labs@rsa.com C. 著作権表示 Copyright (C) The Internet Society (1998). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 日本語訳 西原 啓輔 2001年5月 訳者は、訳出した文書を利用することにより発生したいかなる損害に対しても 責任を負いません。 本文書には、技術的あるいは翻訳上の誤りがある可能性があります。技術的に 正しい知識を獲得しなければならない場合は、InterNIC/IETFから発行されて いる原文を参照してください。