多くのブロック暗号が用いる、Feistel構造とは・・・

Team TripleFalcon. http://www.triplefalcon.com/

概要

 ブロック暗号(block cipher) の最も代表的な構造です。(参照→ブロック暗号) ブロック暗号のデータランダム化部の構造の双璧といえば、 Feistel構造(Feistel structure) SPN構造(substitution permutation network) でしょう。(参照→SPN構造)

  Feistel構造をもつブロック暗号では、入力されたブロックデータを左右2個のサブブロックに分けます。片方のサブブロックに鍵の値を混ぜ込んだ後 F関数により変換を行い 、他方のサブブロックに XOR 処理によって重ね合わせます。処理後は、左右のサブブロックを置き換えて同じように処理を繰り返します。下図は type-1 Feistel 構造です。以下は、外枠がちょうど 1 Round のラウンド関数ですから、例えば 16段Feistel構造をもつ DES の場合は、下記処理を 16 回行うわけです。(参照→DES)

 外部から与えられる KEY-VALUE は、ラウンド鍵(round key) です。

 この Feistel 構造で最初に実装された暗号は、IBM製の暗号 Lucifer であり、発明者 Feistel の名をとって付けられました。Lucifer を改良して製作されたといわれるデータ暗号化規格 DES も Feistel 構造をもっています。 1ラウンドの処理で、データの半分しか暗号化されないため、SPN構造など他の構造に比べると、多くのラウンド数を必要とするようです。 type-2 type-3 等、多くの変種を生み出す母体となりました。

Team TripleFalcon. http://www.triplefalcon.com/

特徴

 Feistel構造の特徴は、以下の通りです。


 (1) 解析実績が多い。
 (2) 決定的な攻撃法が見つかっていない。
 (3) 暗号化と復号化が同一処理。
 (4) F関数の選択自由度が広い。(F関数が全単射である必要もない。)
 (5) ラウンド処理数に比べて攪拌が遅い。

 上記、(1)を少し詳しく言うと、例えば安全性評価用の公式が充実していて、製作者にとって便利であるということが挙げられます。 F関数の性能関して、ある特性値を計算できると、暗号の段数とその値を公式に代入するだけで安全性の指標が求められたりします。(参照→最大線形特性確率)

 (3) に関しては、少しでも安価なハードウェアを作るのに適しています。暗号化復号化の処理では、ラウンド鍵を与える順番だけが逆になるだけです。

 (4) は、面白い性質で、例えば F関数として簡単な f(x)=x2 (mod n) 等を適当に定めて手計算などでシミュレーションすると、ちゃんと復号されることが確かめられます。

 (5) は、特に欠点とも利点ともいえません。

 注意)(1)(2)(3)(4) の性質は、変形Feistel構造では当てはまらない場合があります。

Team TripleFalcon. http://www.triplefalcon.com/

type-1 Feistel

 概要に書いたとおりの構造です。通常、単に Feistel構造と呼んだ場合、この type-1 Feistel 構造を指します。それ以外は、変形 Feistel構造としてまとめて呼ばれることがあります。

 例) x(入力)=x1x2 , y(出力)=y1y2

 y2=x1ÅF(x2) , y1=x2

 概念図は概要に示しました。(参照→概要)

Team TripleFalcon. http://www.triplefalcon.com/

type-2 Feistel

 データを type-1 Feistel のような 2分割ではなく n 分割にします。例えば 4 個のサブブロックを x1,x2,x3,x4 としたとき、F(x2,x3,x4) の値を x1 に重ね合わせます。出力は、1個ずつずらします。

 例) x(入力)=x1x2x3x4 , y(出力)=y1y2y3y4

  y4=x1ÅF(x2,x3,x4) , y1=x2 , y2=x3 , y3=x4

 以下はその概念図です。

Team TripleFalcon. http://www.triplefalcon.com/

type-3 Feistel

 データを type-1 Feistel のような 2分割ではなく n 分割にします。例えば、4 個のサブブロックを x1,x2,x3,x4 としたとき、F(x4) の値を x1,x2,x3 に重ね合わせます。出力は、1個ずつずらします。

 例) x(入力)=x1x2x3x4 , y(出力)=y1y2y3y4

  y1=x4 , y2=x1ÅF(x4) , y3=x2ÅF(x4) , y4=x3ÅF(x4)

 以下はその概念図です。

Team TripleFalcon. http://www.triplefalcon.com/

一般形 Feistel

 データを type-1 Feistel のような 2分割ではなく n 分割にします。例えば、4 個のサブブロックを x1,x2,x3,x4 としたとき、出力は、以下の様に計算します。

 例) x(入力)=x1x2x3x4 , y(出力)=y1y2y3y4

  y3=x3ÅF(x4) , y2=x2ÅF(y3) , y1=x1ÅF(y2) , y4=x4ÅF(y1)

 以下はその概念図です。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

Feistel 構造 (Feistel structure)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール