「ブロック暗号」の版間の差分
m 表現の小修正、リンク追加、-stub |
編集の要約なし |
||
6行目: | 6行目: | ||
:<math>E_k^{-1}(E_k(m))=m</math> |
:<math>E_k^{-1}(E_k(m))=m</math> |
||
を満たす(''m''は任意のブロック)ようになっている。暗号化アルゴリズムの入力ブロック、復号アルゴリズムの出力ブロックは平文、暗号化アルゴリズムの出力ブロック、復号アルゴリズムの入力ブロックは暗号文という。任意サイズの平文を扱うために、[[暗号利用モード]]が用意されている。ブロック暗号は確定的暗号であり、鍵を一つ固定すると、同じ平文は必ず同じ暗号文に暗号化される。すなわち、同じ暗号文があった場合、そのブロックの平文は同じであるという情報が漏れてしまう。暗号利用モードでは、このような問題を解決する機能も持つ。 |
を満たす(''m''は任意のブロック)ようになっている(ただし、KASUMIのように復号が定義されていないブロック暗号もある。)。暗号化アルゴリズムの入力ブロック、復号アルゴリズムの出力ブロックは平文、暗号化アルゴリズムの出力ブロック、復号アルゴリズムの入力ブロックは暗号文という。任意サイズの平文を扱うために、[[暗号利用モード]]が用意されている。ブロック暗号は確定的暗号であり、鍵を一つ固定すると、同じ平文は必ず同じ暗号文に暗号化される。すなわち、同じ暗号文があった場合、そのブロックの平文は同じであるという情報が漏れてしまう。暗号利用モードでは、このような問題を解決する機能も持つ。 |
||
ブロック長Nbは64bitや128bitが代表的である。暗号アルゴリズムによっては、ブロック長をパラメータで指定でき、ブロック長を変えられるものもある。 |
ブロック長Nbは64bitや128bitが代表的である。暗号アルゴリズムによっては、ブロック長をパラメータで指定でき、ブロック長を変えられるものもある。 |
||
38行目: | 38行目: | ||
** Hierocrypt-L1 -CRYPTREC |
** Hierocrypt-L1 -CRYPTREC |
||
** [[MULTI2]] - ARIB限定受信方式 |
** [[MULTI2]] - ARIB限定受信方式 |
||
** [[KASUMI]] - [[3GPP]] [[W-CDMA]]および[[GSM]]用の暗号 |
|||
* 128bit |
* 128bit |
||
** [[AES暗号|AES]] -ISO/IEC_18033, CRYPTREC, NESSIE |
** [[AES暗号|AES]] -ISO/IEC_18033, CRYPTREC, NESSIE |
||
50行目: | 51行目: | ||
== 安全性 == |
== 安全性 == |
||
=== 計算量的安全性 === |
=== 計算量的安全性 === |
||
ブロック暗号はもとより鍵長<math>n</math>ビットに対して<math>2^n</math>の[[計算量的安全性]]以上の安全性を有しない。すなわち、鍵の[[全数探索]]で必ず解読可能である。 |
ブロック暗号はもとより鍵長<math>n</math>ビットに対して<math>2^n</math>の[[計算量的安全性]]以上の安全性を有しない。すなわち、鍵の[[全数探索]]で必ず解読可能である(平均解読計算量は半分の<math>2^{n-1}</math>となる)。 |
||
これは、ブロック暗号の鍵長を定める際に最も重要な要素の一つであり、現在DES (56ビット) が推奨されないのもその鍵長の短さが原因のひとつである。 |
これは、ブロック暗号の鍵長を定める際に最も重要な要素の一つであり、現在DES (56ビット) が推奨されないのもその鍵長の短さが原因のひとつである。 |
||
58行目: | 59行目: | ||
ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵(の一部)を求める手法を総称してショートカット法と呼ぶ。ショートカット法には多くの種類があるが、ここでは代表的なものを列挙する。 |
ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵(の一部)を求める手法を総称してショートカット法と呼ぶ。ショートカット法には多くの種類があるが、ここでは代表的なものを列挙する。 |
||
* [[差分解読法]](差分暗号解読) [[:en:Differential cryptanalysis]] (Biham,1989) |
* [[差分解読法]](差分暗号解読) [[:en:Differential cryptanalysis]] (Biham,1989) |
||
** 不能差分暗号解読 |
** 不能差分暗号解読 Impossible Differential Attack |
||
** [[切詰差分解読法]] Truncated Differential Attack |
** [[切詰差分解読法]] Truncated Differential Attack |
||
** [[高階差分解読法]] |
** [[高階差分解読法]] Higher Order Differential Attack |
||
*** Square攻撃 |
*** Square攻撃 Square Attack |
||
** ブーメラン攻撃 [[:en:Boomerang attack]] |
** ブーメラン攻撃 [[:en:Boomerang attack]] |
||
** 補間攻撃 (Jakobsen, Knudsen, 1997) |
** 補間攻撃Interporation Attack (Jakobsen, Knudsen, 1997) |
||
*** 線形和攻撃 |
*** 線形和攻撃 Linear Sum Attack (Aoki, 1999) |
||
* [[線形解読法]](線形暗号解読) [[:en:Linear cryptanalysis]] ([[松井充|Matsui]],1993) |
* [[線形解読法]](線形暗号解読) [[:en:Linear cryptanalysis]] ([[松井充|Matsui]],1993) |
||
** 差分線形攻撃 [[:en:Differential-linear attack]] |
** 差分線形攻撃 [[:en:Differential-linear attack]] |
||
** 切詰線形攻撃 |
** 切詰線形攻撃 Truncated Linear Attack |
||
* スライド攻撃 [[:en:Slide attack]] (David Wagner,Alex Biryukov,1999) |
* スライド攻撃 [[:en:Slide attack]] (David Wagner,Alex Biryukov,1999) |
||
* カイ2乗攻撃 |
* カイ2乗攻撃 <math>\chi^2</math> Attack |
||
* mod n攻撃 [[:en:Mod n cryptanalysis]] |
* mod n攻撃 [[:en:Mod n cryptanalysis]] |
||
* XSL攻撃 [[:en:XSL attack]] |
* XSL攻撃 [[:en:XSL attack]] |
||
195行目: | 196行目: | ||
;1987年~1991年 |
;1987年~1991年 |
||
:1987年に[[日本電信電話|NTT]]の清水明宏<!--(現:[[高知工科大学]])-->と宮口庄司<!--(現:[[芝浦工業大学]])-->により [[FEAL]] が発表された。1991年にEli Bihamと[[アディ・シャミア]]により[[差分解読法]]が発表され、FEALは差分解読法によって効率的に解読できることが判明した(DESの開発者は設計時には既に差分解読法を知っていて、設計する際に[[Sボックス]]を変更し差分解読法に対処していたことが後に明かされた |
: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年~1995年 |
||
:1992年に[[三菱電機]]の[[松井充]]により[[線形解読法]]が発表され、1993年~1994年にかけてDESの解読と実験が行われた。1995年に線形攻撃法と差分攻撃法に対して証明可能 |
:1992年に[[三菱電機]]の[[松井充]]により[[線形解読法]]が発表され、1993年~1994年にかけてDESの解読と実験が行われた。1995年に線形攻撃法と差分攻撃法に対して[[証明可能安全性|証明可能安全性を持つ暗号]]を有する暗号として MISTY1およびMISTY2 が発表された。その後、様々な攻撃方法の開発と線形差分特性などを指標とする安全性評価の研究が進んだ。 |
||
;1997年~2001年 |
;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が制定された。 |
:計算機とネットワークの進化を背景に、全数探索による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/> |
|||
== 関連項目== |
== 関連項目== |
||
* [[ストリーム暗号]] |
* [[ストリーム暗号]] |
2009年6月6日 (土) 02:20時点における版
ブロック暗号(- あんごう、Block cipher)とは、共通鍵暗号の一種で、固定長のデータ(ブロックと呼ぶ)を単位として処理する暗号の総称である。これに対して、ビット単位やバイト単位で処理を行う暗号はストリーム暗号と呼ばれる。
概要
ブロック暗号は、NbビットのブロックとNkビットの鍵を入力として、Nbビットのブロックを出力する、暗号化(encryption) E と復号(decryption) E-1 の2つのアルゴリズムからなる。任意の鍵kについて、復号アルゴリズムは暗号化アルゴリズムの逆関数になっていて、
を満たす(mは任意のブロック)ようになっている(ただし、KASUMIのように復号が定義されていないブロック暗号もある。)。暗号化アルゴリズムの入力ブロック、復号アルゴリズムの出力ブロックは平文、暗号化アルゴリズムの出力ブロック、復号アルゴリズムの入力ブロックは暗号文という。任意サイズの平文を扱うために、暗号利用モードが用意されている。ブロック暗号は確定的暗号であり、鍵を一つ固定すると、同じ平文は必ず同じ暗号文に暗号化される。すなわち、同じ暗号文があった場合、そのブロックの平文は同じであるという情報が漏れてしまう。暗号利用モードでは、このような問題を解決する機能も持つ。
ブロック長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構造の2つがある。DES, MISTY1, CamelliaはFeistelで、AESはSPNの暗号である。
用途
ブロック暗号は公開鍵暗号に比して高速であるため、公開鍵暗号と組み合わせたハイブリッド暗号では公開鍵暗号で暗号化されたセッション鍵を用いた本文の暗号化・復号に用いられる。
また、パスワードの保存のための一方向性関数として用いられたり (UNIXの/etc/passwd等) 、メッセージ認証コード (MAC) に用いられる。
擬似乱数列の生成にも用いられる(see NIST SP800-90) 。
標準
暗号標準として採用(もしくは推奨)されているブロック暗号には次のものがある。
- 64bit
- 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ビット) が推奨されないのもその鍵長の短さが原因のひとつである。
ただし、ブロック長がである場合、ある平文暗号文対に対して、平均しての鍵候補が存在する。1つの平文暗号文対では、鍵候補の中に真の暗号化鍵は存在するが、どの鍵候補が真の暗号化鍵であるかは判定できない。個の平文暗号文対が存在して、ならば、真の暗号化鍵が得られることが期待できる。
ショートカット法
ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵(の一部)を求める手法を総称してショートカット法と呼ぶ。ショートカット法には多くの種類があるが、ここでは代表的なものを列挙する。
- 差分解読法(差分暗号解読) en:Differential cryptanalysis (Biham,1989)
- 不能差分暗号解読 Impossible Differential Attack
- 切詰差分解読法 Truncated Differential Attack
- 高階差分解読法 Higher Order Differential Attack
- Square攻撃 Square Attack
- ブーメラン攻撃 en:Boomerang attack
- 補間攻撃Interporation 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乗攻撃 Attack
- mod n攻撃 en:Mod n cryptanalysis
- XSL攻撃 en:XSL attack
ショートカット法が存在するアルゴリズムは学術的には「解読可能」と呼ばれるが、その必要な計算量が現実的であるかどうかは考慮されない。すなわち、学術的に解読可能であることが、即、その暗号を利用したシステムの破綻につながるわけではない。しかしながら、設計者が想定した強度を有していないという事実はその暗号アルゴリズムが信頼性の低い暗号アルゴリズムであることを意味する。
歴史
- 1971年~1976年
- 1971年頃にIBMでHorst Feistelにより開発されたLuciferが(民生用として)最初のブロック暗号とされている。Luciferは、換字式暗号と転字式暗号を組み合わせた、換字-転字暗号(Substitution-permutation cipher)である。1977年にLuciferをベースにして、DESが制定された。
- 1987年~1991年
- 1987年にNTTの清水明宏と宮口庄司により FEAL が発表された。FEALは8ビットCPU上のソフトウェアで高速に実行することを意図して、算術加算およびシフトを非線形関数として採用していた。1991年にEli Bihamとアディ・シャミアにより差分解読法が発表され、FEALは差分解読法によって効率的に解読できることが判明した(DESの開発者は設計時には既に差分解読法を知っていて、設計する際にSボックスを変更し差分解読法に対処していたことが後に明かされた[1])。
- 1992年~1995年
- 1992年に三菱電機の松井充により線形解読法が発表され、1993年~1994年にかけてDESの解読と実験が行われた。1995年に線形攻撃法と差分攻撃法に対して証明可能安全性を持つ暗号を有する暗号として MISTY1およびMISTY2 が発表された。その後、様々な攻撃方法の開発と線形差分特性などを指標とする安全性評価の研究が進んだ。
- 1997年~2001年
- 計算機とネットワークの進化を背景に、全数探索によるDESの解読可能性を示すために、1997年にRSAセキュリティ社がDESチャレンジを企画、96日後に鍵が発見された。1998年にはハードウェアによる鍵探索専用機 DES cracker が開発され、DESの鍵を56時間で探索した。1997年に次世代暗号(AES)の制定準備(公募)が始められると共に、1999年にはAESができるまでの中継ぎとしてTripleDESが制定された(FIPS PUB 46-3)。2001年11月にAESが制定された。また、ヨーロッパではNESSIE、日本ではCRYPTRECといった標準化プロジェクトが実施された。
- 2002~
- AESや、CRYPTREC, NESSIEの標準暗号とは別に、ある種の特殊用途に特化したブロック暗号の設計が研究されている。FPGAやICチップで実装した際に回路規模や実行速度が最適化されることを意図して設計されたCLEFIA等があげられる。また、実装されたハードウェアやソフトウェアに対する攻撃(サイドチャネル攻撃)も活発になった。
参考文献
- ^ Coppersmith, Don (May 1994). “The Data Encryption Standard (DES) and its strength against attacks” (PDF). IBM Journal of Research and Development 38 (3): 243 .