ファイステル暗号

暗号学において、フェイステル暗号（ルビー・ラックオフブロック暗号とも呼ばれる）は、ブロック暗号の構築に使用される対称構造であり、IBM在籍時に先駆的な研究を行ったドイツ生まれの物理学者で暗号学者のホルスト・フェイステルにちなんで名付けられました。フェイステルネットワークとも呼ばれています。米国データ暗号化規格、ソビエト/ロシアのGOST、最近のBlowfish 暗号やTwofish暗号など、多数のブロック暗号でこの方式が使用されています。フェイステル暗号では、暗号化と復号化は非常によく似た操作であり、どちらも「ラウンド関数」と呼ばれる関数を固定回数繰り返し実行することで構成されます。

歴史

現代の対称ブロック暗号の多くは、Feistel ネットワークに基づいています。Feistel ネットワークが初めて商業的に利用されたのは、1973 年にHorst FeistelとDon Coppersmithが設計したIBM のLucifer暗号です。Feistelネットワークは、1976 年に米国連邦政府がDES (Lucifer をベースにNSAが変更を加えた暗号) を採用したときに評価されました。DES の他のコンポーネントと同様に、Feistel 構造の反復的な性質により、ハードウェアでの暗号システムの実装が容易になります (特に DES の設計時に利用可能だったハードウェアでは)。

デザイン

Feistel ネットワークはラウンド関数を使用する。ラウンド関数は、2 つの入力 (データブロックとサブキー) を受け取り、データブロックと同じサイズの出力を 1 つ返す。^[1]各ラウンドでは、ラウンド関数は暗号化されるデータの半分に対して実行され、その出力はデータの残り半分と XOR される。これが一定回数繰り返され、最終的な出力が暗号化されたデータである。置換–置換ネットワークなどの他の暗号設計と比較した Feistel ネットワークの重要な利点は、ラウンド関数自体が可逆でなくても、操作全体が可逆であることが保証される (つまり、暗号化されたデータを復号化できる) ことである。ラウンド関数は、可逆になるように設計する必要がないため、任意に複雑にすることができる。^[2]^{: 465} ^[3]^{: 347}さらに、暗号化と復号化の操作は非常に似ており、場合によっては同一であり、キースケジュールを逆にするだけで済む。したがって、このような暗号を実装するために必要なコードまたは回路のサイズはほぼ半分になります。また、置換順列ネットワークとは異なり、Feistel ネットワークは、ソフトウェア実装でタイミングサイドチャネルを引き起こす可能性のある置換ボックスに依存しません。

理論的な研究

Feistel 暗号の構造と特性は、暗号学者によって広範囲に分析されてきました。

マイケル・ルビーとチャールズ・ラックオフはフェイステル暗号の構造を分析し、ラウンド関数が暗号的に安全な疑似乱数関数で、シードとしてK _{i が}使用されている場合、ブロック暗号を疑似乱数順列にするには3ラウンドで十分であり、4ラウンドで「強力な」疑似乱数順列にするには十分であることを証明しました（これは、逆順列へのオラクルアクセスを獲得した敵に対しても疑似乱数のままであることを意味します）。^[4]ルビーとラックオフのこの非常に重要な結果により、フェイステル暗号はルビー–ラックオフブロック暗号と呼ばれることもあります。

さらなる理論的研究により、この構成はある程度一般化され、セキュリティのより正確な境界が与えられました。^[5]^[6]

建設の詳細

をラウンド関数とし、をそれぞれラウンドのサブキーとします。 $\mathrm {F}$ $K_{0},K_{1},\ldots ,K_{n}$ $0,1,\ldots ,n$

基本的な操作は次のようになります。

プレーンテキストブロックを 2 つの等しい部分に分割します: ( 、)。 $L_{0}$ $R_{0}$

各ラウンドごとに計算する $i=0,1,\dots ,n$

L_{i+1}=R_{i},

R_{i+1}=L_{i}\oplus \mathrm {F} (R_{i},K_{i}),

ここで、はXORを意味します。暗号文はです。 $\oplus$ $(R_{n+1},L_{n+1})$

暗号文の復号は、 $(R_{n+1},L_{n+1})$ $i=n,n-1,\ldots ,0$

R_{i}=L_{i+1},

L_{i}=R_{i+1}\oplus \operatorname {F} (L_{i+1},K_{i}).

すると再び平文になります。 $(L_{0},R_{0})$

この図は暗号化と復号化の両方を示しています。復号化のサブキーの順序が逆になっていることに注意してください。これが暗号化と復号化の唯一の違いです。

不均衡ファイステル暗号

不平衡型フェイステル暗号は、との長さが等しくない修正構造を使用します。 ^[7]スキップジャック暗号はそのような暗号の一例です。テキサスインスツルメンツのデジタル署名トランスポンダは、独自の不平衡型フェイステル暗号を使用してチャレンジレスポンス認証を実行します。^[8] $L_{0}$ $R_{0}$

ソープシャッフルは、片側が1ビットである不均衡フェイステル暗号の極端な例である。これは均衡フェイステル暗号よりも証明可能なセキュリティが高いが、より多くのラウンドを必要とする。^[9]

その他の用途

Feistel 構造は、ブロック暗号以外の暗号化アルゴリズムでも使用されます。たとえば、最適非対称暗号化パディング(OAEP) 方式では、単純な Feistel ネットワークを使用して、特定の非対称キー暗号化方式で暗号文をランダム化します。

一般化されたFeistelアルゴリズムは、2の累乗ではない小さな領域上で強力な順列を作成するために使用できます（フォーマット保持暗号化を参照）。^[9]

設計コンポーネントとしての Feistel ネットワーク

暗号全体が Feistel 暗号であるかどうかに関わらず、暗号の設計のコンポーネントとして Feistel のようなネットワークを使用できます。たとえば、MISTY1はラウンド関数に 3 ラウンドの Feistel ネットワークを使用する Feistel 暗号であり、Skipjack はG 順列に Feistel ネットワークを使用する修正された Feistel 暗号であり、Threefish ( Skeinの一部) は Feistel のような MIX 関数を使用する非 Feistel ブロック暗号です。

フェイステル暗号の一覧

Feistel または修正 Feistel:

一般化された Feistel:

参照

参考文献

^ Menezes, Alfred J.; Oorschot, Paul C. van; Vanstone, Scott A. (2001). Handbook of Applied Cryptography (第 5 版). Taylor & Francis. p. 251. ISBN 978-0849385230。
^ シュナイアー、ブルース (1996)。応用暗号学。ニューヨーク：ジョン・ワイリー・アンド・サンズ。ISBN 0-471-12845-7。
^ スティンソン、ダグラス R. (1995)。暗号：理論と実践。ボカラトン：CRC プレス。ISBN 0-8493-8521-0。
^ ルビー、マイケル、ラックオフ、チャールズ（1988年4月）「擬似ランダム関数から擬似ランダム順列を構築する方法」、SIAM Journal on Computing、17（2）：373–386、doi：10.1137/0217022、ISSN 0097-5397。
^ パタリン、ジャック（2003年10月）、ボネ、ダン（編）、暗号学の進歩 - CRYPTO 2003 （PDF）、コンピュータサイエンスの講義ノート、第2729巻、pp. 513-529、doi：10.1007/b11817、ISBN 978-3-540-40674-7, S2CID 20273458 , 2009-07-27取得
^ 鄭玉亮; 松本勉; 今井秀樹 (1989-08-20)。「証明可能な安全性を持ち、証明されていない仮説に頼らないブロック暗号の構築について」。暗号学の進歩 - CRYPTO' 89 議事録。コンピュータサイエンスの講義ノート。第 435 巻。pp. 461–480。doi : 10.1007 / 0-387-34805-0_42。ISBN 978-0-387-97317-3。
^ Schneier, Bruce; Kelsey, John (1996-02-21). 「不均衡な Feistel ネットワークとブロック暗号の設計」. 高速ソフトウェア暗号化. コンピュータサイエンスの講義ノート. 第 1039 巻. pp. 121–144. doi :10.1007/3-540-60865-6_49. ISBN 978-3-540-60865-3. 2017年11月21日閲覧。
^ Bono, Stephen; Green, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel; Szydlo, Michael (2005-08-05). 「暗号化対応 RFID デバイスのセキュリティ分析」(PDF)。USENIX セキュリティシンポジウムの議事録。 2017-11-21に取得。
^ ab Morris, Ben; Rogaway, Phillip; Stegers, Till (2009). 「小さなドメインでメッセージを暗号化する方法」。Advances in Cryptology - CRYPTO 2009 (PDF)。Lecture Notes in Computer Science。Vol. 5677。pp. 286–302。doi : 10.1007 /978-3-642-03356-8_17。ISBN 978-3-642-03355-1. 2017年11月21日閲覧。

[1] Menezes, Alfred J.; Oorschot, Paul C. van; Vanstone, Scott A. (2001). Handbook of Applied Cryptography (第 5 版). Taylor & Francis. p. 251. ISBN 978-0849385230。

[2] シュナイアー、ブルース (1996)。応用暗号学。ニューヨーク：ジョン・ワイリー・アンド・サンズ。ISBN 0-471-12845-7。

[stinson-3] スティンソン、ダグラス R. (1995)。暗号：理論と実践。ボカラトン：CRC プレス。ISBN 0-8493-8521-0。

[pseudorandom-4] ルビー、マイケル、ラックオフ、チャールズ（1988年4月）「擬似ランダム関数から擬似ランダム順列を構築する方法」、SIAM Journal on Computing、17（2）：373–386、doi：10.1137/0217022、ISSN 0097-5397。

[7-rounds-5] パタリン、ジャック（2003年10月）、ボネ、ダン（編）、暗号学の進歩 - CRYPTO 2003 （PDF）、コンピュータサイエンスの講義ノート、第2729巻、pp. 513-529、doi：10.1007/b11817、ISBN 978-3-540-40674-7, S2CID 20273458 , 2009-07-27取得

[6] 鄭玉亮; 松本勉; 今井秀樹 (1989-08-20)。「証明可能な安全性を持ち、証明されていない仮説に頼らないブロック暗号の構築について」。暗号学の進歩 - CRYPTO' 89 議事録。コンピュータサイエンスの講義ノート。第 435 巻。pp. 461–480。doi : 10.1007 / 0-387-34805-0_42。ISBN 978-0-387-97317-3。

[7] Schneier, Bruce; Kelsey, John (1996-02-21). 「不均衡な Feistel ネットワークとブロック暗号の設計」. 高速ソフトウェア暗号化. コンピュータサイエンスの講義ノート. 第 1039 巻. pp. 121–144. doi :10.1007/3-540-60865-6_49. ISBN 978-3-540-60865-3. 2017年11月21日閲覧。

[crypto-rfid-8] Bono, Stephen; Green, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel; Szydlo, Michael (2005-08-05). 「暗号化対応 RFID デバイスのセキュリティ分析」(PDF)。USENIX セキュリティシンポジウムの議事録。 2017-11-21に取得。

[thorp-9] Morris, Ben; Rogaway, Phillip; Stegers, Till (2009). 「小さなドメインでメッセージを暗号化する方法」。Advances in Cryptology - CRYPTO 2009 (PDF)。Lecture Notes in Computer Science。Vol. 5677。pp. 286–302。doi : 10.1007 /978-3-642-03356-8_17。ISBN 978-3-642-03355-1. 2017年11月21日閲覧。