Nicola氏のCPS2解説、昨日の続きです：
相補的な特性が重要なのは、テーブルサイズが半分になるからというだけではありません。とはいうものの、この特徴を十分に活用しているわけではないのですが。
ここで、CPS2の暗号化についておさらいしておきましょう。
入力：
- ROMに保存された16ビットの値
- 16ビットのアドレス値 (1～17ビットの物理アドレス)
- ゲーム毎に変わるサイズ不定のキー
出力：
- 16ビットの復号化された値
ここでは、アドレスAにある値XをキーKとして、関数D(X,A,K)とします。相補的な特徴とは、どんなAについても必ず対応するA1が存在することです。つまり、
D(X,A,K) = D'(X',A1,K)
ということになります。
この発見が重要なのは、暗号化においてAがアルゴリズム的な影響を与えているからです。SegaのFD1094 CPUでは、各アドレスのキーは巨大なテーブルで保持されています。もしCPS2が同じ動作なら、相補的な特性は現われません。
これは特に驚くことではなく、Segaが巨大なキー＋シンプルなアルゴリズムを好むのに対し、Capcomは小さなキー＋複雑なアルゴリズムを好むことをKabuki CPUで見てきています。
残念ながら、AからA1を導く方法はまだわかっていません。ゲームによって変わるので、キーの関数であるのは間違いありません。
相補特性というのは、強力な暗号でも特別珍しいものではありません。ですから、アルゴリズムの欠点であるとは必ずしも言えません。たとえばDES暗号でも見られ、D(X,K) = D'(X',K') となります。
一般的に、相補特性はXOR演算が起きている兆候ともいわれます。相殺のために補数演算が起こるからです。例を見てみます。代理関数をfとして、次のようなアルゴリズムがある場合、
d = e XOR f(e XOR k)
補集合は
e' XOR f(e' XOR k') = e' XOR f(e XOR k) = (e XOR f(e XOR k))' = d'
とになります。もちろんこれはとてもシンプルな例ですが、この場合はx'が補集合でなくてもよいことに注意してください。たとえば、x' = x XOR 1と定義しても成立します。ですから、CPS2のアルゴリズムはこんなにシンプルでないのは確かです。
もっと現実的な例としてフェイステル構造（DES暗号はフェイステル構造を使っています）を挙げましょう。フェイステル構造を以下のように定義すると、
Li = R i-1
Ri = L i-1 XOR f(Ri-1 XOR Ki-1)
相補性がどのように出てくるかよく簡単にわかるはずです。
CPS2の暗号化がフェイステル構造を使っているという考えは確かに魅力的ではありますが、個人的には違うと思います。なぜならば、前回説明したデータの拡散がもっとよくなるはずだからです。