ブロック暗号のソースを表示

'''ブロック暗号'''（ブロックあんごう、{{lang-en|Block cipher}}）とは、[[共通鍵暗号]]の一種で、固定長のデータ（ブロックと呼ぶ）を単位として処理する暗号の総称である。これに対して、ビット単位やバイト単位で処理を行う暗号は[[ストリーム暗号]]と呼ばれる。

== 概要 ==
ブロック暗号は、<math>b</math> ビットのブロックと <math>n</math> ビットの鍵を入力として、<math>b</math> ビットのブロックを出力する。暗号化 (encryption) <math>E</math> と復号 (decryption) <math>E^{-1}</math> の2つの[[アルゴリズム]]からなる。任意の鍵 <math>k</math> について、復号アルゴリズムは暗号化アルゴリズムの逆関数になっていて、

:<math>E_k^{-1}(E_k(m))=m</math>

を満たす（<math>m</math> は任意のブロック）ようになっている<ref>ただし、[[KASUMI]]のように復号が定義されていないブロック暗号もある。</ref>。暗号化アルゴリズムの入力ブロックおよび復号アルゴリズムの出力ブロックは通信文、暗号化アルゴリズムの出力ブロックおよび復号アルゴリズムの入力ブロックは暗号文という。任意の長さの通信文を扱うために、[[暗号利用モード]]が用意されている。ブロック暗号は確定的暗号であり、鍵を一つ固定すると、同じ平文は必ず同じ暗号文に暗号化される。すなわち、同じ暗号文があった場合、そのブロックの平文は同じであるという情報が漏れてしまう。暗号利用モードでは、このような問題を解決する機能ももつ。

換字と転置を組み合わせた共通鍵暗号でも、複数の法に基づく大きなブロックの換字式[[ストリーム暗号]]と[[転置式暗号]]を組み合わせることで解読の著しく難しい暗号が構成できる。

代表的なブロック暗号として、米[[NIST]]が制定した[[Data Encryption Standard|DES]] (Data Encryption Standard)や[[トリプルDES]]、[[Advanced Encryption Standard|AES]] (Advanced Encryption Standard) がある。日本製のブロック暗号として、[[MISTY1]]や[[Camellia]]などが知られている。

== 構造 ==
ブロック暗号は、メインのスクランブラと拡大鍵を生成する鍵スケジューラから構成されているものが多い。さらに、鍵スケジューラは鍵を入力として複数個の拡大鍵を出力し、スクランブラは複数のラウンドからなり、個々のラウンドで拡大鍵を使って入力の置換・転置等を行う構成になっているものが多い。この構成の暗号をProduct cipher（積暗号）という。また、ラウンドが同じ関数の繰り返しになっている場合にはIterated cipher（繰返し暗号）という。

ラウンド関数は置換や転置、論理演算、算術演算などのシンプルな部品で構成されていて、ラウンド関数を複数段、重ねることで十分な強度のスクランブルを行うものである。ラウンド段数は、通常、アルゴリズムの仕様によって指定されているが、セキュリティパラメータとして利用者が選択するものもある。

ラウンド関数の主な構成法には[[Feistel構造]]と[[SPN構造]]の2つがある。DES, MISTY1, CamelliaはFeistel構造で、AESはSPN構造の暗号である。

== 用途 ==
ブロック暗号は公開鍵暗号に比して高速であるため、公開鍵暗号と組み合わせたハイブリッド暗号では公開鍵暗号で暗号化されたセッション鍵を用いた本文の暗号化・復号に用いられる。

また、パスワードの保存のための一方向性関数として用いられたり (UNIXの/etc/passwd等) 、[[メッセージ認証コード]] (MAC) に用いられる。

擬似乱数列の生成にも用いられる (see [http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf NIST SP800-90]) 。

== 標準 ==
暗号標準として採用（もしくは推奨）されているブロック暗号には次のものがある。

* 64bit
** TDEA - [[ISO/IEC_18033]], [[CRYPTREC]]
** MISTY1 -ISO/IEC_18033, CRYPTREC, [[NESSIE]]
** [[CAST-128]] -ISO/IEC_18033
** CIPHERUNICORN-E - CRYPTREC
** Hierocrypt-L1 -CRYPTREC
** [[MULTI2]] - ARIB限定受信方式
** [[KASUMI]] - [[3GPP]] [[W-CDMA]]および[[GSM]]用の暗号
* 128bit
** [[Advanced Encryption Standard|AES]] -ISO/IEC_18033, CRYPTREC, NESSIE
** [[Camellia]] -ISO/IEC_18033, CRYPTREC, NESSIE
** [[SEED_(暗号)|SEED]] -ISO/IEC_18033
** [[CIPHERUNICORN-A]] - CRYPTREC
** [[Hierocrypt-3]] -CRYPTREC
** [[SC2000]] -CRYPTREC
* 256bit
** SHACAL-2 -NESSIE

== 安全性 ==
=== 計算量的安全性 ===
ブロック暗号は、もとより鍵長<math>n</math>ビットに対して<math>2^n</math>の[[計算量的安全性]]以上の安全性をもたない。すなわち、鍵の[[全数探索]]で必ず解読可能である（平均解読計算量は半分の<math>2^{n-1}</math>となる）。
これは、ブロック暗号の鍵長を定める際に最も重要な要素の一つであり、現在DES（56ビット）が推奨されないのもその鍵長の短さが原因の一つである。

ただし、ブロック長<math>b</math>が<math>b<n</math>である場合、ある通信文と暗号文の対（ペア）に対して、平均して<math>2^{n-b}</math>の鍵候補が存在する。一つの通信文暗号文対では、鍵候補の中に真の暗号化鍵は存在するが、どの鍵候補が真の暗号化鍵であるかは判定できない。<math>p</math>個の通信文暗号文対が存在して、<math>bp>n</math>ならば、真の暗号化鍵が得られることが期待できる。

=== ショートカット法 ===
ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵（の一部）を求める手法を総称してショートカット法と呼ぶ。ショートカット法には多くの種類があるが、ここでは代表的なものを列挙する。
* [[差分解読法]]（差分暗号解読） [[:en:Differential cryptanalysis]] (Biham, 1989)
** 不能差分解読法 [[:en:Impossible differential cryptanalysis]]
** [[切詰差分解読法]] Truncated Differential Cryptanalysis
** [[高階差分解読法]] Higher Order Differential Cryptanalysis
*** Square攻撃 [[:en:Square attack]]
*** 飽和攻撃 Saturation Attack
** ブーメラン攻撃 [[:en:Boomerang attack]]
** 補間攻撃 [[:en:Interpolation attack]] (Jakobsen, Knudsen, 1997) 
*** 線形和攻撃 Linear Sum Attack (Aoki, 1999)
* [[線形解読法]]（線形暗号解読） [[:en:Linear cryptanalysis]] ([[松井充|Matsui]], 1993)
** 差分線形攻撃 [[:en:Differential-linear attack]]
** 切詰線形攻撃 Truncated Linear Attack
* スライド攻撃 [[:en:Slide attack]] (David Wagner, Alex Biryukov, 1999)
* カイ2乗攻撃 <math>\chi^2</math> Attack
* mod n攻撃 [[:en:Mod n cryptanalysis]]
* XSL攻撃 [[:en:XSL attack]]
ショートカット法が存在するアルゴリズムは学術的には「解読可能」と呼ばれるが、その必要な計算量が現実的であるかどうかは考慮されない。学術的に解読可能であることは、必ずしもその暗号を利用したシステムの破綻につながるわけではない。しかしながら、設計者が想定した強度を有していないという事実は、その暗号アルゴリズムが[[信頼性の低い暗号アルゴリズム]]であることを意味する。

=== サイドチャネル攻撃 ===
ハードウェアやソフトウェアに実装された暗号を、アルゴリズムではなく消費電力や実行時間等の情報を用いて攻撃する手法を[[サイドチャネル攻撃]]と呼ぶ。サイドチャネル攻撃は実装とアルゴリズムの両方に影響される。
* [[単純電力解析]] Simple Power Analysis
* 電力差分攻撃 [[:en:Power analysis#Differential_power_analysis|en:Differential power analysis]]
* タイミング攻撃 [[:en:Timing attack]]

== 歴史 ==
;1971年 - 1976年
:1971年頃に[[IBM]]でHorst Feistelにより開発された[[Lucifer (暗号)|Lucifer]]が（民生用としての）最初のブロック暗号とされている。Luciferは、[[換字式暗号]]と[[転字式暗号]]を組み合わせた、換字-転字暗号 (Substitution-permutation cipher) である。1977年にLuciferをベースにして、[[Data Encryption Standard|DES]]が制定された。
;1987年 - 1991年
:1987年に[[日本電信電話|NTT]]の清水明宏<!--（現:[[高知工科大学]]）-->と宮口庄司<!--（現:[[芝浦工業大学]]）-->により [[FEAL]] が発表された。FEALは8ビットCPU上のソフトウェアで高速に実行することを意図して、算術加算およびシフトを非線形関数として採用していた。1991年にEli Bihamと[[アディ・シャミア]]により[[差分解読法]]が発表され、FEALは差分解読法によって効率的に解読できることが判明した（DESの開発者は設計時には既に差分解読法を知っていて、設計する際に[[Sボックス]]を変更し差分解読法に対処していたことが後に明かされた<ref name="coppersmith">
{{cite journal |last = Coppersmith |first = Don |year = 1994 |month = May |title = The Data Encryption Standard (DES) and its strength against attacks |journal = IBM Journal of Research and Development |volume = 38 |issue = 3 |pages = 243 |url = http://www.research.ibm.com/journal/rd/383/coppersmith.pdf |format = PDF }}</ref>）。
;1992年 - 1995年
:1992年に[[三菱電機]]の[[松井充]]により[[線形解読法]]が発表され、1993年 - 1994年にかけてDESの解読と実験が行われた。1995年に線形攻撃法と差分攻撃法に対して[[証明可能安全性を持つ暗号|証明可能安全性]]を有する暗号として MISTY1およびMISTY2 が発表された。その後、様々な攻撃方法の開発と線形差分特性などを指標とする安全性評価の研究が進んだ。
;1997年 - 2001年
:計算機とネットワークの進化を背景に、全数探索によるDESの解読可能性を示すために、1997年に[[RSAセキュリティ|RSAセキュリティ社]]がDESチャレンジを企画、96日後に鍵が発見された。1998年にはハードウェアによる鍵探索専用機 DES cracker が開発され、DESの鍵を56時間で探索した。1997年に次世代暗号 ([[Advanced Encryption Standard|AES]]) の制定準備（公募）が始められると共に、1999年にはAESができるまでの中継ぎとして[[トリプルDES|TripleDES]]が制定された (FIPS PUB 46-3) 。2001年11月にAESが制定された。また、ヨーロッパでは[[NESSIE]]、日本では[[CRYPTREC]]といった標準化プロジェクトが実施された。
;2002年 -
:AESや、CRYPTREC, NESSIEの標準暗号とは別に、ある種の特殊用途に特化したブロック暗号の設計が研究されている。[[FPGA]]や[[ICチップ]]で実装した際に回路規模や実行速度が最適化されることを意図して設計された[[CLEFIA]]等があげられる。また、実装された[[ハードウェア]]や[[ソフトウェア]]に対する攻撃（[[サイドチャネル攻撃]]）も活発になった。

== 脚注 ==
{{脚注ヘルプ}}
<references/>

== 関連項目==
* [[ストリーム暗号]]
* [[共通鍵暗号]]
* [[暗号理論]]
* [[Feistel構造]]
* [[SPN構造]]

{{cryptography navbox|block}}

{{DEFAULTSORT:ふろつくあんこう}}
[[Category:暗号プリミティブ]]
[[Category:ブロック暗号|*]]