|
'''ブロック暗号'''（- ブロックあんごう、{{lang-en|Block cipher）cipher}}）とは、[[共通鍵暗号]]の一種で、固定長のデータ（ブロックと呼ぶ）を単位として処理する暗号の総称である。これに対して、ビット単位やバイト単位で処理を行う暗号は[[ストリーム暗号]]と呼ばれる。
== 概要 ==
ブロック暗号は、N<submath>b</submath> ビットのブロックとN <submath>kn</submath> ビットの鍵を入力として、N<submath>b</submath> ビットのブロックを出力する、。暗号化 (encryption) ''<math>E''</math> と復号 (decryption) ''E<supmath>E^{-1}</supmath>'' の２2つの[[アルゴリズム]]からなる。任意の鍵'' <math>k''</math> について、復号アルゴリズムは暗号化アルゴリズムの逆関数になっていて、
:<math>E_k^{-1}(E_k(m))=m</math>
を満たす（''<math>m''</math> は任意のブロック）ようになっている(<ref>ただし、[[KASUMI]]のように復号が定義されていないブロック暗号もある。)</ref>。暗号化アルゴリズムの入力ブロックおよび復号アルゴリズムの出力ブロックは通信文、暗号化アルゴリズムの出力ブロックおよび復号アルゴリズムの入力ブロックは暗号文という。任意の長さの通信文を扱うために、[[暗号利用モード]]が用意されている。ブロック暗号は確定的暗号であり、鍵を一つ固定すると、同じ平文は必ず同じ暗号文に暗号化される。すなわち、同じ暗号文があった場合、そのブロックの平文は同じであるという情報が漏れてしまう。暗号利用モードでは、このような問題を解決する機能ももつ。
換字と転置を組み合わせた共通鍵暗号でも、複数の法に基づく大きなブロックの換字式[[ストリーム暗号]]と[[転置式暗号]]を組み合わせることで解読の著しく難しい暗号が構成できる。
ブロック長N<sub>b</sub>は64ビットや128ビットが代表的である。暗号アルゴリズムによっては、ブロック長をパラメータで指定でき、ブロック長を変えられるものもある。
代表的なブロック暗号として、米[[NIST]]が制定した[[Data Encryption Standard|DES]] (Data Encryption Standard)や[[トリプルDES]]、[[Advanced Encryption Standard|AES]] (Advanced Encryption Standard) がある。日本製のブロック暗号として、[[MISTY1]]や[[Camellia]]などが知られている。
鍵長N<sub>k</sub>は 40, 56, 64, 80, 128, 192, 256 ビットなどがある。
代表的なブロック暗号として、米[[NIST]]が制定した<!--[[DES (暗号)|DES]] (Data Encryption Standard)や-->[[AES暗号|AES]] (Advanced Encryption Standard)がある。日本製のブロック暗号として、[[MISTY1]]や[[Camellia]]などが知られている。
== 構造 ==
ラウンド関数は置換や転置、論理演算、算術演算などのシンプルな部品で構成されていて、ラウンド関数を複数段、重ねることで十分な強度のスクランブルを行うものである。ラウンド段数は、通常、アルゴリズムの仕様によって指定されているが、セキュリティパラメータとして利用者が選択するものもある。
ラウンド関数の主な構成法に、は[[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]) 。
== 標準 ==
** [[KASUMI]] - [[3GPP]] [[W-CDMA]]および[[GSM]]用の暗号
* 128bit
** [[AES暗号Advanced Encryption Standard|AES]] -ISO/IEC_18033, CRYPTREC, NESSIE
** [[Camellia]] -ISO/IEC_18033, CRYPTREC, NESSIE
** [[SEED_(暗号)|SEED]] -ISO/IEC_18033
== 安全性 ==
=== 計算量的安全性 ===
ブロック暗号は、もとより鍵長<math>n</math>ビットに対して<math>2^n</math>の[[計算量的安全性]]以上の安全性を有しもたない。すなわち、鍵の[[全数探索]]で必ず解読可能である(（平均解読計算量は半分の<math>2^{n-1}</math>となる)）。
これは、ブロック暗号の鍵長を定める際に最も重要な要素の一つであり、現在DES (56DES（56ビット) ）が推奨されないのもその鍵長の短さが原因のひと一つである。
ただし、ブロック長<math>b</math>が<math>b<n</math>である場合、ある平通信文と暗号文の対（ペア）に対して、平均して<math>2^{n-b}</math>の鍵候補が存在する。1一つの平通信文暗号文対では、鍵候補の中に真の暗号化鍵は存在するが、どの鍵候補が真の暗号化鍵であるかは判定できない。<math>kp</math>個の平通信文暗号文対が存在して、<math>bkbp>n</math>ならば、真の暗号化鍵が得られることが期待できる。
=== ショートカット法 ===
ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵(（の一部)）を求める手法を総称してショートカット法と呼ぶ。ショートカット法には多くの種類があるが、ここでは代表的なものを列挙する。
* [[差分解読法]]（差分暗号解読） [[:en:Differential cryptanalysis]] (Biham, 1989)
** 不能差分暗号解読法 [[:en:Impossible Differentialdifferential Attackcryptanalysis]]
** [[切詰差分解読法]] Truncated Differential AttackCryptanalysis
** [[高階差分解読法]] Higher Order Differential AttackCryptanalysis
*** Square攻撃 [[:en:Square Attackattack]]
*** 飽和攻撃 Saturation Attack
** ブーメラン攻撃 [[:en:Boomerang attack]]
** 補間攻撃Interporation 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]]
ショートカット法が存在するアルゴリズムは学術的には「解読可能」と呼ばれるが、その必要な計算量が現実的であるかどうかは考慮されない。すなわち、学術的に解読可能であることが、即は、必ずしもその暗号を利用したシステムの破綻につながるわけではない。しかしながら、設計者が想定した強度を有していないという事実は、その暗号アルゴリズムが[[信頼性の低い暗号アルゴリズム]]であることを意味する。
<!--
=== 計算量的でない安全性 ===
暗号化鍵と暗号化文が一対一対応するすべての暗号は時間さえあれば全鍵探索で解読可能です。
全鍵探索しても秘密鍵を解読できないブロック暗号があります。
３ビットのブロック暗号による擬似乱数発生器の例を３つの入出力対応表で示します。
列見出しは暗号攻撃者が入力する任意の数であり、乱数の種は秘密で行見出しの２進数です。
乱数発生のアルゴリズムは公開されていて、攻撃者は表を全て事前に用意できます。
=== サイドチャネル攻撃 ===
{|class="wikitable" style="text-align:center"
ハードウェアやソフトウェアに実装された暗号を、アルゴリズムではなく消費電力や実行時間等の情報を用いて攻撃する手法を[[サイドチャネル攻撃]]と呼ぶ。サイドチャネル攻撃は実装とアルゴリズムの両方に影響される。
|+ 対応表０
* [[単純電力解析]] Simple Power Analysis
! !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
* 電力差分攻撃 [[:en:Power analysis#Differential_power_analysis|en:Differential power analysis]]
|-
* タイミング攻撃 [[:en:Timing attack]]
!0 0 0
|style="width:2em"|0||style="width:2em"|7||style="width:2em"|7||style="width:2em"|0||style="width:2em"|7||style="width:2em"|0||style="width:2em"|0||style="width:2em"|7
|-
!0 0 1
|5||2||1||6||1||6||5||2
|-
!0 1 0
|5||2||1||0||7||6||5||2
|-
!0 1 1
|6||4||2||3||4||5||3||1
|-
!1 0 0
|6||4||2||3||4||5||3||1
|-
!1 0 1
|5||2||1||0||7||6||5||2
|-
!1 1 0
|5||2||1||6||1||6||5||2
|-
!1 1 1
|0||7||7||0||7||0||0||7
|-
|}
攻撃者は表０の出力の値から乱数の種の値を決定できません。
乱数の種の値は出力の値と２対１対応しています。
<ref name="cited">参考文献 PCT/JP2005/008646, personally identificapable sieved confidential information sign-up</ref>
<references/>
乱数の種を増分して、その出力を下に表示します。見出しは元の種の値です。
{|class="wikitable" style="text-align:center"
|+ 対応表１
! !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
!0 0 0
|style="width:2em"|3||style="width:2em"|4||style="width:2em"|7||style="width:2em"|0||style="width:2em"|7||style="width:2em"|0||style="width:2em"|3||style="width:2em"|4
|-
!0 0 1
|3||7||2||6||1||5||0||4
|-
!0 1 0
|3||7||2||6||1||5||0||4
|-
!0 1 1
|3||4||7||0||7||0||3||4
|-
!1 0 0
|3||2||7||6||1||0||5||4
|-
!1 0 1
|0||1||4||0||7||3||6||7
|-
!1 1 0
|0||1||4||0||7||3||6||7
|-
!1 1 1
|3||2||7||6||1||0||5||4
|-
|}
表０と表１を用いて攻撃者が最初と２度目の出力の値から乱数の種の値を決定できるのは、入力の値が１か３か４、又は６でそのうち１６の場合だけです。
たとえば攻撃者の入力が１・１であり出力が７・４のとき、乱数の種の値は０００です。
乱数の種の値が１１１のときの出力は７・２であり、差異があります。
再び乱数の種を増分して、その出力を下に表示します。
{|class="wikitable" style="text-align:center"
|+ 対応表２
! !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
!0 0 0
|style="width:2em"|7||style="width:2em"|6||style="width:2em"|5||style="width:2em"|2||style="width:2em"|5||style="width:2em"|2||style="width:2em"|1||style="width:2em"|0
|-
!0 0 1
|1||6||5||2||5||2||1||6
|-
!0 1 0
|7||0||0||7||0||7||7||0
|-
!0 1 1
|7||0||0||7||0||7||7||0
|-
!1 0 0
|1||6||5||2||5||2||1||6
|-
!1 0 1
|7||6||5||2||5||2||1||0
|-
!1 1 0
|4||5||3||1||6||4||2||3
|-
!1 1 1
|4||5||3||1||6||4||2||3
|-
|}
攻撃者は今までの結果と表２の出力の値から乱数の種の値を決定できます。
ただし乱数の種の値が０００か１０１で攻撃者の入力が４・４・４のとき、０００か１０１かを決定できません。
この擬似乱数発生器は２．８１２５回とプラスαだけ攻撃者の予測できない情報を発信します。
表０と表１は出力の値と乱数の種の値から入力の値を決定できないことも示しています。
この擬似乱数発生器は一方向性関数でもあります。
{{節stub}}
-->
== 歴史 ==
;1971年～1976 - 1976年
:1971年頃に[[IBM]]でHorst Feistelにより開発された[[Lucifer (暗号)|Lucifer]]が(（民生用として)の）最初のブロック暗号とされている。Luciferは、[[換字式暗号]]と[[転字式暗号]]を組み合わせた、換字-転字暗号 (Substitution-permutation cipher) である。1977年にLuciferをベースにして、[[DESData (暗号)Encryption Standard|DES]]が制定された。
;1987年 - 1991年
;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]]等があげられる。また、実装された[[ハードウェア]]や[[ソフトウェア]]に対する攻撃（[[サイドチャネル攻撃]]）も活発になった。
== 脚注 ==
;1992年～1995年
{{脚注ヘルプ}}
:1992年に[[三菱電機]]の[[松井充]]により[[線形解読法]]が発表され、1993年～1994年にかけてDESの解読と実験が行われた。1995年に線形攻撃法と差分攻撃法に対して[[証明可能安全性を持つ暗号|証明可能安全性]]を有する暗号として MISTY1およびMISTY2 が発表された。その後、様々な攻撃方法の開発と線形差分特性などを指標とする安全性評価の研究が進んだ。
<references/>
;1997年～2001年
:計算機とネットワークの進化を背景に、全数探索によるDESの解読可能性を示すために、1997年に[[RSAセキュリティ|RSAセキュリティ社]]がDESチャレンジを企画、96日後に鍵が発見された。1998年にはハードウェアによる鍵探索専用機 DES cracker が開発され、DESの鍵を56時間で探索した。1997年に次世代暗号([[AES暗号|AES]])の制定準備(公募)が始められると共に、1999年にはAESができるまでの中継ぎとして[[トリプルDES|TripleDES]]が制定された(FIPS PUB 46-3)。2001年11月にAESが制定された。また、ヨーロッパでは[[NESSIE]]、日本では[[CRYPTREC]]といった標準化プロジェクトが実施された。
;2002～
:AESや、CRYPTREC, NESSIEの標準暗号とは別に、ある種の特殊用途に特化したブロック暗号の設計が研究されている。[[FPGA]]や[[ICチップ]]で実装した際に回路規模や実行速度が最適化されることを意図して設計された[[CLEFIA]]等があげられる。また、実装された[[ハードウェア]]や[[ソフトウェア]]に対する攻撃([[サイドチャネル攻撃]])も活発になった。
== 参考文献 ==
<references/>
== 関連項目==
* [[ストリーム暗号]]
* [[SPN構造]]
{{cryptography navbox|block}}
{{DEFAULTSORT:ふろつくあんこう}}
[[Category:暗号技術]]
{{DEFAULTSORT:ふろつくあんこう}}
[[ca:Xifratge per blocs]]
[[Category:暗号プリミティブ]]
[[cs:Bloková šifra]]
[[Category:ブロック暗号|*]]
[[de:Blockverschlüsselung]]
[[en:Block cipher]]
[[es:Cifrado por bloques]]
[[fr:Chiffrement par bloc]]
[[he:צופן בלוקים]]
[[it:Cifratura a blocchi]]
[[ko:블록 암호]]
[[nl:Blokvercijfering]]
[[no:Blokkchiffer]]
[[pl:Szyfr blokowy]]
[[ro:Cifru pe blocuri]]
[[ru:Блочный шифр]]
[[simple:Block cipher]]
[[uk:Блочний шифр]]
[[vi:Mã hóa khối]]
| 