Feistel構造とは？ブロック暗号の仕組みと特徴をわかりやすく解説

Feistel構造とは何かを初心者向けにわかりやすく解説。ブロック暗号の仕組み、暗号化/復号の特徴や利点、ラウンド設計やS/Pボックスの役割まで詳述。

暗号学における Feistel 暗号 は、対称鍵型のブロック暗号の設計に広く用いられる構造で、ホルスト・フェイステル（IBM の暗号研究者）にちなんで名付けられました。代表的な実装例としては、古典的な標準暗号である データ暗号化標準規格（DES）があり、Feistel 構造を基盤にしています。

Feistel 構造の大きな利点の一つは、暗号化と復号化の処理が非常に似通っている点です。多くの場合、復号化は暗号化と同じ回路（または同じコード）を用い、鍵のスケジュールを反転させるだけで実現できます。このため、実装に必要な回路やプログラムの量が削減され、ハードウェア実装や組み込み処理に向いています。

Feistel 構造の基本的な動作

Feistel ネットワークはブロックを左右二つの半分に分割し、複数のラウンドを反復して適用します。各ラウンドでは右側の半分に対して非線形関数（ラウンド関数）を適用し、その結果を左側の半分と組み合わせ（通常は XOR）、その後左右を入れ替えます。ラウンド i の処理を簡潔に書くと次のようになります。

• L_i = R_{i-1}
• R_i = L_{i-1} XOR F(R_{i-1}, K_i)

ここで F が仮に可逆でなくても、Feistel 構造全体は可逆（＝一意な復号が可能）になります。復号化ではラウンドキー K_i の順序を逆にして同じ手順を繰り返します。

構成要素とその役割

Feistel 系暗号の各ラウンドで用いられる基本的な要素は次の通りです。

• ビットの並べ替え（しばしば 順列ボックス や P-ボックスと呼ばれる） — 拡散（diffusion）を促進する。
• 非線形変換（一般に 置換ボックス、S-ボックスと呼ばれる） — 混乱（confusion）を与え、線形解析を困難にする。
• 線形結合（例えば XOR や モジュラー代数 的操作） — S-ボックスやP-ボックスと組み合わせて、クロード・シャノンの言う「混乱と拡散」を実現する関数を生成する。

利点と実装上の特徴

• 暗号化と復号化で同じ回路やコードを使えるため、実装コストが低い。
• 反復（ラウンド）構造はハードウェアに適しており、パイプライン化やリソースの節約がしやすい。
• ラウンド関数 F が必ずしも可逆でなくてもネットワーク全体は可逆であるため、設計上の柔軟性が高い。

安全性と設計上の注意点

Feistel 構造の安全性は、ラウンド数、ラウンド関数 F（特に S-ボックスの非線形性）、そして鍵スケジュールの強度に大きく依存します。少ないラウンドでは差分攻撃や線形攻撃などの解析に弱くなるため、十分なラウンド数の確保と堅牢な鍵スケジュールが重要です。

理論的には、適切に設計されたラウンド関数を用い十分なラウンド数を確保すれば、Feistel ネットワークは強い擬似乱関数的性質（擬似ランダム置換）を示すことが証明されています（例えば Luby–Rackoff の結果など）。しかし実際の実装では S-ボックス設計や鍵スケジュールの不備により脆弱になる例が存在します。

派生と応用

Feistel 構造にはいくつかの変種があります。左右の半分のサイズが等しくない「アンバランスド・Feistel」や、ラウンド関数を複数段で構成するもの、さらにはハイブリッドな構造などが考案されています。実際のブロック暗号（例：DES）は S-ボックスや P-ボックス を組み合わせて、上記のような混乱と拡散を達成しています。

まとめ（ポイント）

• Feistel 構造はブロックを半分に分け、ラウンド関数と XOR、入れ替えを繰り返すことで全体を可逆にする設計手法。
• 暗号化と復号化が同じ手順で実装できる場合が多く、実装コストが低い。
• S-ボックス（置換）は混乱、P-ボックス（順列）は拡散を担い、XOR 等の線形結合と合わせて安全性を高める。
• 設計ミス（不十分なラウンド数、弱い鍵スケジュール等）により攻撃に対して脆弱になるため、慎重な設計が不可欠。

最後に、ビットシャッフルは拡散効果を高め、置換（S-ボックス）は混乱を生み出すために用いられる、という点はFeistelに限らず多くの積暗号設計で共通する基本的な考え方です。

建設

Let F {F {\displaystyle {F}}} is the round function and let K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}} be sub-keys for the round 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n} } are respective respective.

そうすると、基本的な動作は以下のようになります。

平文ブロックを2等分に分割して ( L 1 {\displaystyle L_{1}} , R 1 {\displaystyle R_{1}} )

For each round i = 1 , 2 , ... , n {For each round i = 1 , 2 , ... ... , n} {\displaystyle i=1,2,を計算する

L i + 1 = R i {displaystyle L_{i+1}=R_{i},｝。}

R i + 1 = L i ⊕ F ( R i , K i ) {\displaystyle R_{i+1}=L_{i}oplus {\rm {F}}}(R_{i},K_{i})} .

とすると、暗号文は ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} となる。(共通して、R n {\displaystyle R_{n}}とL n {\displaystyle L_{n}}の２つは、最後のラウンドでは入れ替わらない)

暗号文( R n , L n )の復号化は、i = n , n - 1 , ... , 1 {displaystyle i=n,n-1,忘却の日 ,1}を計算することで達成される。

R i = L i + 1 {displaystyle R_{i}=L_{i+1},｝。}

L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\displaystyle L_{i}=R_{i+1}oplus {\rm {F}}}(L_{i+1},K_{i})} .

とすると、( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})}が再び平文となる。

このモデルの利点の一つは、円形関数F {\displaystyle {\rm {F}}}は反転可能である必要がなく、非常に複雑になり得ることである。

この図は、暗号化処理を示している。復号化は、サブキー K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}}の順序を逆にするだけで、同じ処理を行う。

不均衡Feistel暗号は、L 1 {\displaystyle L_{1}}とR 1 {\displaystyle R_{1}}の長さが等しくないように修正した構造を用いている。マックガフィン暗号はそのような暗号の実験的な例である。

このFeistel構造は、ブロック暗号以外の暗号アルゴリズムにも利用されている。例えば、Optimal Asymmetric Encryption Padding (OAEP) スキームは、ある種の非対称鍵暗号化スキームにおいて、単純なFeistelネットワークを使用して暗号文をランダム化します。

ブロック暗号におけるファイステルネットワーク演算、ここでPは平文、Cは暗号文である。

質問と回答

Q:ファイステル暗号とは何ですか?

Q:Feistel構造を使用する利点は何ですか?

Q:クロード・シャノンは「混乱と拡散」をどのように表現したのですか?

Q:混乱と拡散を起こすには、どのような技術が必要ですか?

Q: Feistel Networkとはどのような暗号ですか?

Q: 誰がこの暗号を開発したのですか?

Q: Data Encryption Standardはこの暗号をベースにしているのですか?

文字で検索