混乱と拡散

暗号学において、混乱と拡散は、 1945年の機密報告書「暗号の数学的理論」でクロード・シャノンが特定した安全な暗号の2つの特性です。^{[1]これらの特性が存在すると、}統計やその他の暗号解読方法 の適用を妨害する働きをします。

対称暗号における混乱は、データへのキーの適用を変化させることによって、入力（平文）と出力（暗号文）の間の局所的な相関関係を不明瞭にすることであり、拡散は、暗号文のより広い領域に平文の統計を拡散することによって平文の統計を隠すことである。 ^[2]暗号は混乱のみ（置換暗号、ワンタイムパッド）または拡散のみ（転置暗号）にすることができるが、あらゆる「合理的な」ブロック暗号は混乱と拡散の両方を使用する。^[2]これらの概念は、生成された値の相関関係の除去が主な特徴である暗号ハッシュ関数および疑似乱数生成器の設計においても重要である。拡散（およびその雪崩効果）は、非暗号ハッシュ関数にも適用できる。

混乱とは、暗号文の各2進数（ビット）が鍵の複数の部分に依存し、両者の関係が不明瞭になることを意味します。^[3]

混乱の特性により、暗号文と鍵の関係が隠されます。

この特性により、暗号文からキーを見つけることが困難になり、キーの 1 ビットが変更されると、暗号文のほとんどまたはすべてのビットの計算に影響が及びます。

混乱は暗号文の曖昧さを増大させ、ブロック暗号とストリーム暗号の両方で使用されます。

置換順列ネットワークでは、置換ボックスによって混乱が生じる。^[4]

拡散とは、平文の1ビットを変更すると暗号文の約半分のビットが変更され、同様に暗号文の1ビットを変更すると平文の約半分のビットが変更されることを意味します。^{[5]これは、暗号化方式が}雪崩効果を示すという期待に相当します。

拡散の目的は、暗号文と平文の間の統計的関係を隠すことです。たとえば、拡散により、冗長ビットなどの平文のパターンが暗号文に現れないことが保証されます。^[3]ブロック暗号は、平文の構造に関する情報を暗号の行と列全体に「拡散」することでこれを実現します。

置換-順列ネットワークでは、拡散は順列ボックス（別名順列層^[4] ）によって提供されます。21世紀の初めには、設計者は順列層を線形ブール関数で構成することを好むというコンセンサスが形成されましたが、非線形関数も使用できます。^[4]

シャノンの元の定義では、混乱とは暗号文と対称鍵の関係を可能な限り複雑で入り組んだものにすることを指し、拡散とは平文の統計的構造を暗号文の大部分に拡散させることを指します。この複雑さは一般に、明確に定義され反復可能な一連の置換と順列によって実装されます。置換とは、特定のルールに従って、特定のコンポーネント (通常はビット) を他のコンポーネントに置き換えることを指します。順列とは、何らかのアルゴリズムに従ってビットの順序を操作することです。効果を上げるには、平文ビットの不均一性を暗号文のより大きな構造全体に再分配する必要があり、その不均一性を検出するのがはるかに難しくなります。

特に、ランダムに選択された入力に対して、i番目のビットを反転すると、任意のiとjに対して、 j番目の出力ビットが変化する確率は半分になるはずです。これは厳密なアバランシェ基準と呼ばれます。より一般的には、固定されたビットセットを反転すると、各出力ビットが確率 1/2 で変化することが要求される場合があります。

混乱の目的の 1 つは、同じキーで生成された平文と暗号文のペアが多数ある場合でも、キーを見つけるのが非常に困難になるようにすることです。したがって、暗号文の各ビットはキー全体に依存し、キーの異なるビットにさまざまな方法で依存する必要があります。特に、キーの 1 ビットを変更すると、暗号文が完全に変更される必要があります。

現代のブロック暗号の設計では、混乱と拡散の両方が利用されており^[2]、 混乱では、キーに依存する非線形変換を適用することで、入力と出力の間でデータが変更されます（線形計算は逆計算が容易であるため、解読が容易です）。

混乱には必然的に拡散が伴うため^{[6]、非常に広い入力の}S ボックスを備えた設計は必要な拡散特性を提供することができますが^[要出典]、実装には非常にコストがかかります。したがって、実用的な暗号では、比較的小さな S ボックスを使用し、小さなビット グループ (「バンドル」^[7] ) で操作します。たとえば、AES の設計には、8 ビットの S ボックス、Serpent - 4 ビット、BaseKing、3-way - 3 ビットがあります^[8] 。小さな S ボックスではほとんど拡散が提供されないため、リソースはより単純な拡散変換に費やされます^{[6] 。たとえば、} Rijndael設計によって普及したワイド トレイル戦略では、高い拡散を提供する線形混合変換が行われます^[9]。ただし、セキュリティ証明は拡散層が線形であることに依存しません^{[10] 。}

最も研究されている暗号構造の1つは、各ラウンドに混乱のための局所非線形置換（Sボックス）の層と線形拡散変換（通常は有限体上の行列による乗算）が含まれる置換順列ネットワーク（SPN）を使用する。^[11]現代のブロック暗号は主に混乱層/拡散層モデルに従っており、拡散層の効率は、完全な拡散変換のためのs入力バンドルの値に到達できる数値パラメータである、いわゆる分岐数を使用して推定される。^[12]分岐数が多い変換（したがって入力として多くのバンドルを必要とする）は実装コストが高いため、拡散層は（たとえばAESでは）2つのサブレイヤー、バンドルのサブセットをブリックレイヤー方式で処理する「ローカル拡散」（各サブセットは独立して変換される）と「分散」（バンドルの1つのサブセット内で「近い」ビットを「遠い」ビットにする（異なるサブセットに広がり、次のラウンドでこれらの新しいサブセット内でローカルに拡散する））で構成されることがあります。^[13]${\displaystyle s+1}$

高度暗号化規格( AES) は、優れた混乱と拡散の両方を備えています。その混乱ルックアップテーブルは非常に非線形であり、パターンを破壊するのに優れています。^[14]拡散段階では、入力のすべての部分が出力のすべての部分に広がります。入力の 1 ビットを変更すると、平均して出力ビットの半分が変更されます。混乱と拡散の両方が各入力に対して複数回繰り返され、スクランブルの量が増加します。秘密鍵は各段階で混合されるため、攻撃者は暗号の内容を事前に計算することはできません。

単純な 1 段階のスクランブルがキーに基づいている場合、このようなことは起こりません。入力パターンはそのまま出力に流れます。見た目にはランダムに見えますが、分析すると明らかなパターンが見つかり、暗号を解読できます。

• アルゴリズム情報理論
• 雪崩効果
• 置換順列ネットワーク

• クロード・E・シャノン、「暗号の数学的理論」、ベルシステム技術メモ MM 45-110-02、1945 年 9 月 1 日。
• クロード・E・シャノン、「秘密システムの通信理論」、ベルシステム技術ジャーナル、第28～4巻、656～715ページ、1949年。[1] 2007年6月5日にWayback Machineでアーカイブ
• Wade Trappe および Lawrence C. Washington、「暗号理論による暗号入門」。第 2 版。Pearson Prentice Hall、2006 年。
• Li, Chaoyun; Wang, Qingju (2017). 「近似MDS行列からの軽量線形拡散層の設計」(PDF) . IACR Transactions on Symmetric Cryptology . 1 : 129–155. doi :10.13154/tosc.v2017.i1.129-155.
• Sajadieh, Mahdi; Dakhilalian, Mohammad; Mala, Hamid; Sepehrdad, Pouyan (2012). 「ブロック暗号とハッシュ関数の再帰拡散層」。高速ソフトウェア暗号化 ( PDF)。Springer Berlin Heidelberg。pp. 385–401。doi :10.1007/ 978-3-642-34047-5_22。eISSN 1611-3349。ISSN 0302-9743  。
• Daemen, Joan; Rijmen, Vincent (2013 年 3 月 9 日)。Rijndael の設計: AES - 高度暗号化標準( PDF)。Springer Science & Business Media。ISBN 978-3-662-04722-4. OCLC  1259405449.
• マーク・スタンプ、リチャード・M・ロー（2007年6月15日）。応用暗号解読：現実世界での暗号解読。ジョン・ワイリー・アンド・サンズ。ISBN 978-0-470-14876-1. OCLC  1044324461.
• Liu, Yunwen; Rijmen, Vincent; Leander, Gregor (2018 年 1 月 20 日). 「非線形拡散層」(PDF) . Designs, Codes and Cryptography . 86 (11): 2469–2484. doi :10.1007/s10623-018-0458-5. eISSN  1573-7586. ISSN  0925-1022.