Feistel構造

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

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

 

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

暗号化

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

復号

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

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

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

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

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

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

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

• 1ラウンドあたり攪拌されるのはブロックのうち一部のみである
• SPN構造と同様の攪拌性を得るためにはラウンド数を増やす必要がある

• SPN構造
• ブロック暗号
• 共通鍵暗号
• 暗号理論
• ホルスト・ファイステル