Feistel構造

ファイステル構造（ファイステルこうぞう、）は、ブロック暗号の構成法の一種である。ほとんどのブロック暗号は、実装コストを効率化するために同一のラウンド関数を繰り返す繰り返し暗号になっており、ファイステル構造は繰り返し暗号の代表的な構成法である。他の構成としてはSPN構造がある。
概要.
1977年にIBMのホルスト・ファイステルが開発したDESの構造から、ファイステル構造と呼ばれる。暗号に求められる性質の1つに暗号文から平文を復号できること（復号可能性）があるが、ファイステル構造は逆変換が自分自身と同じ形になる性質がある（インボルーション）ため、ラウンド関数に任意の関数を用いても復号可能性が保証できるという特徴がある。
DES以降、FEAL、MISTY1、Camelliaなど、多くのブロック暗号でファイステル構造は採用されている。
構造.
基本的な構造.
DESで採用された構造は、2つのラウンド変数formula_1, formula_2（初期入力をformula_3, formula_4とする）とラウンド鍵formula_5およびラウンド関数formula_6から以下の計算を繰り返し施す。
暗号化
 formula_7
 formula_8
復号
 formula_9
 formula_10
暗号化と復号で使用するラウンド関数formula_6は、暗号化の出力を復号の入力に代入して式変形すれば容易に確認できるが、任意の関数を用いても復号可能性が保証される。暗号化と復号の違いは、ラウンド鍵formula_5の順番が逆になるだけである。
言うまでもないが、安全なブロック暗号を任意の関数で保障できるわけではない。
入れ子型構造.
MISTYでは、ラウンド関数formula_6の内部にさらにファイステル構造を組み込んでいる。これを入れ子型構造と呼ぶ。MISTYでは3段階の入れ子構造をとっている。入れ子構造は差分攻撃および線形攻撃に対する証明可能安全性を実現するとともに、回路規模の削減に効果がある。
変形ファイステル構造.
MARSでは、入力を4つに分割しそれぞれの間で計算を行うような構造で構成されている。一般にformula_14分割する場合を変形ファイステル構造と呼ぶ。ブロック暗号全体のブロック長が大きい場合にラウンド関数のビット幅を小さくすることができる。
利点・欠点.
ファイステル構造以外に広く知られている構造にSPN構造がある。SPN構造と比較した場合の利点および欠点を述べる。