ブロック暗号
ブロック暗号（- あんごう、Block cipher）とは、共通鍵暗号の一種で、ブロックと呼ばれる固定長のデータを単位として暗号化復号を行う暗号である。これに対して、ビット単位やバイト単位で暗号化を行う暗号はストリーム暗号と呼ばれる。
概要
ブロック暗号は、NbビットのブロックとNkビットの鍵を入力として、Nbビットのブロックを出力する、暗号化(encryption) E と復号(decryption) E-1 の２つのアルゴリズムからなる。任意の鍵kについて、復号アルゴリズムは暗号化アルゴリズムの逆関数になっていて、
を満たす（mは任意のブロック）ようになっている。暗号化アルゴリズムの入力ブロック、復号アルゴリズムの出力ブロックは平文、暗号化アルゴリズムの出力ブロック、復号アルゴリズムの入力ブロックは暗号文という。任意サイズの平文を扱うために、暗号利用モードが用意されている。ブロック暗号は確定的暗号であり、鍵を一つ固定すると、同じ平文は必ず同じ暗号文に暗号化される。すなわち、同じ暗号文があった場合、そのブロックの平文は同じであるという情報が漏れてしまう。暗号利用モードでは、このような問題を解決する機能も持つ。
ブロック長Nbは64bitや128bitが代表的である。暗号アルゴリズムによっては、ブロック長をパラメータで指定でき、ブロック長を変えられるものもある。
鍵長Nkは 40/56/64/80/128/192/256bit などがある。
代表的なブロック暗号として、米NISTが制定したDES (Data Encryption Standard, FIPS PUB 46)やAES (Advanced Encryption Standard, FIPS PUB 197)がある。日本産のブロック暗号として、MISTY1やCamelliaなどが知られている。
構造
ブロック暗号は、メインのスクランブラと拡大鍵を生成する鍵スケジューラから構成されているものが多い。さらに、鍵スケジューラは鍵を入力として複数個の拡大鍵を出力し、スクランブラは複数のラウンドからなり、個々のラウンドで拡大鍵を使って入力の置換・転置等を行う構成になっているものが多い。この構成の暗号をProduct cipher（積暗号）という。また、ラウンドが同じ関数の繰り返しになっている場合にはIterated cipher（繰返し暗号）という。
ラウンド関数は置換や転置、論理演算、算術演算などのシンプルな部品で構成されていて、ラウンド関数を複数段、重ねることで十分な強度のスクランブルを行うものである。ラウンド段数は、通常、アルゴリズムの仕様によって指定されているが、セキュリティパラメータとして利用者が選択するものもある。
ラウンド関数の主な構成法に、Feistel構造とSPN構造の２つがある。DES, MISTY1, CamelliaはFeistelで、AESはSPNの暗号である。
用途
ブロック暗号は公開鍵暗号に比して高速であるため、公開鍵暗号と組み合わせたハイブリッド暗号では公開鍵暗号で暗号化されたセッション鍵を用いた本文の暗号化・復号に用いられる。
また、パスワードの保存のための一方向性関数として用いられたり (UNIXの/etc/passwd等) 、メッセージ認証コード (MAC) に用いられる。
擬似乱数列の生成にも用いられる(see 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限定受信方式
- 128bit
- AES -ISO/IEC_18033, CRYPTREC, NESSIE
- Camellia -ISO/IEC_18033, CRYPTREC, NESSIE
- SEED -ISO/IEC_18033
- CIPHERUNICORN-A - CRYPTREC
- Hierocrypt-3 -CRYPTREC
- SC2000 -CRYPTREC
- 256bit
- SHACAL-2 -NESSIE
安全性
計算量的安全性
ブロック暗号はもとより鍵長 ビットに対して の計算量的安全性以上の安全性を有しない。すなわち、鍵の全数探索で必ず解読可能である。 これは、ブロック暗号の鍵長を定める際に最も重要な要素の一つであり、現在DES (56ビット) が推奨されないのもその鍵長の短さが原因のひとつである。
ショートカット法
ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵(の一部)を求める手法を総称してショートカット法と呼ぶ。ショートカット法には多くの種類があるが、ここでは代表的なものを列挙する。
- 差分解読法（差分暗号解読） en:Differential cryptanalysis (Biham,1989)
- 不能差分暗号解読
- 切詰差分解読法 Truncated Differential Attack
- 高階差分解読法
- Square攻撃
- ブーメラン攻撃 en:Boomerang attack
- 補間攻撃 (Jakobsen, Knudsen, 1997)
- 線形和攻撃
- 線形解読法（線形暗号解読） en:Linear cryptanalysis (Matsui,1993)
- 差分線形攻撃 en:Differential-linear attack
- 切詰線形攻撃
- スライド攻撃 en:Slide attack (David Wagner,Alex Biryukov,1999)
- カイ2乗攻撃
- mod n攻撃 en:Mod n cryptanalysis
- XSL攻撃 en:XSL attack
ショートカット法が存在するアルゴリズムは学術的には「解読可能」と呼ばれるが、その必要な計算量が現実的であるかどうかは考慮されない。すなわち、学術的に解読可能であることが、即、その暗号を利用したシステムの破綻につながるわけではない。しかしながら、設計者が想定した強度を有していないという事実はその暗号アルゴリズムが信頼性の低い暗号アルゴリズムであることを意味する。
計算量的でない安全性
暗号化鍵と暗号化文が一対一対応するすべての暗号は時間さえあれば全鍵探索で解読可能です。 全鍵探索しても秘密鍵を解読できないブロック暗号があります。 ３ビットのブロック暗号による擬似乱数発生器の例を３つの入出力対応表で示します。 列見出しは暗号攻撃者が入力する任意の数であり、乱数の種は秘密で行見出しの２進数です。 乱数発生のアルゴリズムは公開されていて、攻撃者は表を全て事前に用意できます。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 0 0 | 0 | 7 | 7 | 0 | 7 | 0 | 0 | 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 |
攻撃者は表０の出力の値から乱数の種の値を決定できません。 乱数の種の値は出力の値と２対１対応しています。 [1]
- ^ 参考文献 PCT/JP2005/008646, personally identificapable sieved confidential information sign-up
乱数の種を増分して、その出力を下に表示します。見出しは元の種の値です。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 0 0 | 3 | 4 | 7 | 0 | 7 | 0 | 3 | 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 |
表０と表１を用いて攻撃者が最初と２度目の出力の値から乱数の種の値を決定できるのは、入力の値が１か３か４、又は６でそのうち１６の場合だけです。 たとえば攻撃者の入力が１・１であり出力が７・４のとき、乱数の種の値は０００です。 乱数の種の値が１１１のときの出力は７・２であり、差異があります。 再び乱数の種を増分して、その出力を下に表示します。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 0 0 | 7 | 6 | 5 | 2 | 5 | 2 | 1 | 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 |
攻撃者は今までの結果と表２の出力の値から乱数の種の値を決定できます。 ただし乱数の種の値が０００か１０１で攻撃者の入力が４・４・４のとき、０００か１０１かを決定できません。 この擬似乱数発生器は２．８１２５回とプラスαだけ攻撃者の予測できない情報を発信します。 表０と表１は出力の値と乱数の種の値から入力の値を決定できないことも示しています。 この擬似乱数発生器は一方向性関数でもあります。
この節の加筆が望まれています。 |
歴史
- 1971年～1976年
- 1971年頃にIBMでHorst Feistelにより開発されたLuciferが(民生用として)最初のブロック暗号とされている。Luciferは、換字式暗号と転字式暗号を組み合わせた、換字-転字暗号(Substitution-permutation cipher)である。1977年にLuciferをベースにして、DESが制定された。
- 1987年～1991年
- 1987年にNTTの清水明宏と宮口庄司により FEAL が発表された。1991年にEli Bihamとアディ・シャミアにより差分解読法が発表され、FEALは差分解読法によって効率的に解読できることが判明した（DESの開発者は設計時には既に差分解読法を知っていて、設計する際にSボックスを変更し差分解読法に対処していたことが後に明かされた）。
- 1992年～1995年
- 1992年に三菱電機の松井充により線形解読法が発表され、1993年～1994年にかけてDESの解読と実験が行われた。1995年に線形攻撃法と差分攻撃法に対して証明可能な安全性を有する暗号として MISTY1 が発表された。その後、様々な攻撃方法の開発と線形差分特性などを指標とする安全性評価の研究が進んだ。
- 1997年～2001年
- 計算機とネットワークの進化を背景に、全数探索によるDESの解読可能性を示すために、1997年にRSAセキュリティ社がDESチャレンジを企画、96日後に鍵が発見された。1998年にはハードウェアによる鍵探索専用機 DES cracker が開発され、DESの鍵を56時間で探索した。1997年に次世代暗号(AES)の制定準備(公募)が始められると共に、1999年にはAESができるまでの中継ぎとしてTripleDESが制定された(FIPS PUB 46-3)。2001年11月にAESが制定された。
関連項目
 | この項目は、書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。 このテンプレートは分野別のスタブテンプレート（Wikipedia:スタブカテゴリ参照）に変更することが望まれています。 |