Feistel構造

ファイステル構造（ファイステルこうぞう、英語: Feistel structure）は、ブロック暗号の構成法の一種である。ほとんどのブロック暗号は、実装コストを効率化するために同一のラウンド関数を繰り返す繰り返し暗号になっており、ファイステル構造は繰り返し暗号の代表的な構成法である。他の構成としてはSPN構造がある。

概要

1977年にIBMのホルスト・ファイステルが開発したDESの構造から、ファイステル構造と呼ばれる。暗号に求められる性質の1つに暗号文から平文を復号できること（復号可能性）があるが、ファイステル構造は逆変換が自分自身と同じ形になる性質がある（インボルーション）ため、ラウンド関数に任意の関数を用いても復号可能性が保証できるという特徴がある。

DES以降、FEAL、MISTY1、Camelliaなど、多くのブロック暗号でファイステル構造は採用されている。

構造

基本的な構造

DESで採用された構造は、2つのラウンド変数 $L_{r}$ , $R_{r}$ （初期入力を $L_{0}$ , $R_{0}$ とする）とラウンド鍵 $k_{r}$ およびラウンド関数 $F$ から以下の計算を繰り返し施す。

暗号化

 $R_{r+1}=L_{r}\oplus {}F(R_{r},k_{r})$ 
 $L_{r+1}=R_{r}$

復号

 $L_{r}=R_{r+1}\oplus {}F(L_{r+1},k_{r})$ 
 $R_{r}=L_{r+1}$

暗号化と復号で使用するラウンド関数 $F$ は、暗号化の出力を復号の入力に代入して式変形すれば容易に確認できるが、任意の関数を用いても復号可能性が保証される。暗号化と復号の違いは、ラウンド鍵 $k_{r}$ の順番が逆になるだけである。

言うまでもないが、安全なブロック暗号を任意の関数で保障できるわけではない。

入れ子型構造

MISTYでは、ラウンド関数 $F$ の内部にさらにファイステル構造を組み込んでいる。これを入れ子型構造と呼ぶ。MISTYでは3段階の入れ子構造をとっている。入れ子構造は差分攻撃および線形攻撃に対する証明可能安全性を実現するとともに、回路規模の削減に効果がある。

変形ファイステル構造

MARSでは、入力を4つに分割しそれぞれの間で計算を行うような構造で構成されている。一般に $n(n>2)$ 分割する場合を変形ファイステル構造と呼ぶ。ブロック暗号全体のブロック長が大きい場合にラウンド関数のビット幅を小さくすることができる。

利点・欠点

ファイステル構造以外に広く知られている構造にSPN構造がある。SPN構造と比較した場合の利点および欠点を述べる。

利点

解析実績が多い
ラウンド関数の選択の自由度が大きい
暗号化と復号のルーチンを共通化でき（ラウンド鍵の順番だけを入れ替えればよい）、コードサイズ・回路規模などの点で、ソフトウェアおよびハードウェアでの実装性に優れる
一度に処理するデータ長がブロック長の半分（変形ファイステル構造の場合は半分以下）になるため、ラウンド関数のビット幅を小さくすることができる。これはSボックスの個数を少なく出来る等を意味し、回路規模や消費電力など点で、ハードウェアでの実装性に優れる