「ブロック暗号」の版間の差分
削除された内容 追加された内容
ノート参照 |
Sabakansaba (会話 | 投稿記録) m編集の要約なし |
||
(29人の利用者による、間の48版が非表示) | |||
1行目:
'''ブロック暗号'''(
== 概要 ==
ブロック暗号は、
:<math>E_k^{-1}(E_k(m))=m</math>
を満たす(
換字と転置を組み合わせた共通鍵暗号でも、複数の法に基づく大きなブロックの換字式[[ストリーム暗号]]と[[転置式暗号]]を組み合わせることで解読の著しく難しい暗号が構成できる。
代表的なブロック暗号として、米[[NIST]]が制定した[[
▲代表的なブロック暗号として、米NISTが制定した[[DES (暗号)|DES]] (Data Encryption Standard, FIPS PUB 46)や[[AES暗号|AES]] (Advanced Encryption Standard, FIPS PUB 197)がある。日本産のブロック暗号として、[[MISTY1]]や[[Camellia]]などが知られている。
== 構造 ==
19 ⟶ 17行目:
ラウンド関数は置換や転置、論理演算、算術演算などのシンプルな部品で構成されていて、ラウンド関数を複数段、重ねることで十分な強度のスクランブルを行うものである。ラウンド段数は、通常、アルゴリズムの仕様によって指定されているが、セキュリティパラメータとして利用者が選択するものもある。
ラウンド関数の主な構成法に
== 用途 ==
26 ⟶ 24行目:
また、パスワードの保存のための一方向性関数として用いられたり (UNIXの/etc/passwd等) 、[[メッセージ認証コード]] (MAC) に用いられる。
擬似乱数列の生成にも用いられる (see [http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf
== 標準 ==
暗号標準として採用
** 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]]用の暗号
** [[Camellia]] -ISO/IEC_18033, CRYPTREC, NESSIE▼
** [[SEED_(暗号)|SEED]] -ISO/IEC_18033▼
** [[CIPHERUNICORN-A]] - CRYPTREC▼
** [[Hierocrypt-3]] -CRYPTREC▼
** [[SC2000]] -CRYPTREC▼
** SHACAL-2 -NESSIE▼
== 安全性 ==▼
▲;128bit
=== 計算量的安全性 ===▼
▲* [[AES暗号|AES]] -ISO/IEC_18033, CRYPTREC, NESSIE
ブロック暗号は、もとより鍵長<math>n</math>ビットに対して<math>2^n</math>の[[計算量的安全性]]以上の安全性を
▲* [[Camellia]] -ISO/IEC_18033, CRYPTREC, NESSIE
▲* [[SEED_(暗号)|SEED]] -ISO/IEC_18033
▲* [[CIPHERUNICORN-A]] - CRYPTREC
▲* [[Hierocrypt-3]] -CRYPTREC
▲* [[SC2000]] -CRYPTREC
ただし、ブロック長<math>b</math>が<math>b<n</math>である場合、ある通信文と暗号文の対(ペア)に対して、平均して<math>2^{n-b}</math>の鍵候補が存在する。一つの通信文暗号文対では、鍵候補の中に真の暗号化鍵は存在するが、どの鍵候補が真の暗号化鍵であるかは判定できない。<math>p</math>個の通信文暗号文対が存在して、<math>bp>n</math>ならば、真の暗号化鍵が得られることが期待できる。
▲;256bit
▲* SHACAL-2 -NESSIE
▲== 安全性 ==
▲=== 計算量的安全性 ===
▲ブロック暗号はもとより鍵長<math>n</math>ビットに対して<math>2^n</math>の[[計算量的安全性]]以上の安全性を有しない。すなわち、鍵の[[全数探索]]で必ず解読可能である。
▲これは、ブロック暗号の鍵長を定める際に最も重要な要素の一つであり、現在DES (56ビット) が推奨されないのもその鍵長の短さが原因のひとつである。
=== ショートカット法 ===
ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵
* [[差分解読法]](差分暗号解読) [[:en:Differential cryptanalysis]] (Biham, 1989)
** 不能差分
** [[切詰差分解読法]] Truncated Differential
** [[高階差分解読法]] 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年
:1971年頃に[[IBM]]でHorst Feistelにより開発された[[Lucifer (暗号)|Lucifer]]が
:1987年に[[日本電信電話|NTT]]の清水明宏<!--(現:[[高知工科大学]])-->と宮口庄司<!--(現:[[芝浦工業大学]])-->により [[FEAL]] が発表された。FEALは8ビットCPU上のソフトウェアで高速に実行することを意図して、算術加算およびシフトを非線形関数として採用していた。1991年にEli Bihamと[[アディ・シャミア]]により[[差分解読法]]が発表され、FEALは差分解読法によって効率的に解読できることが判明した(DESの開発者は設計時には既に差分解読法を知っていて、設計する際に[[Sボックス]]を変更し差分解読法に対処していたことが後に明かされた
{{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年に[[三菱電機]]の[[松井充]]により[[線形解読法]]が発表され、1993年
:計算機とネットワークの進化を背景に、全数探索によるDESの解読可能性を示すために、1997年に[[RSAセキュリティ|RSAセキュリティ社]]がDESチャレンジを企画、96日後に鍵が発見された。1998年にはハードウェアによる鍵探索専用機 DES cracker が開発され、DESの鍵を56時間で探索した。1997年に次世代暗号 ([[
;2002年 -
:AESや、CRYPTREC, NESSIEの標準暗号とは別に、ある種の特殊用途に特化したブロック暗号の設計が研究されている。[[FPGA]]や[[ICチップ]]で実装した際に回路規模や実行速度が最適化されることを意図して設計された[[CLEFIA]]等があげられる。また、実装された[[ハードウェア]]や[[ソフトウェア]]に対する攻撃([[サイドチャネル攻撃]])も活発になった。
== 脚注 ==
▲;1987年~1991年
{{脚注ヘルプ}}
▲:1987年に[[日本電信電話|NTT]]の清水明宏<!--(現:[[高知工科大学]])-->と宮口庄司<!--(現:[[芝浦工業大学]])-->により [[FEAL]] が発表された。1991年にEli Bihamと[[アディ・シャミア]]により[[差分解読法]]が発表され、FEALは差分解読法によって効率的に解読できることが判明した(DESの開発者は設計時には既に差分解読法を知っていて、設計する際に[[Sボックス]]を変更し差分解読法に対処していたことが後に明かされた)。
<references/>
▲;1992年~1995年
▲:1992年に[[三菱電機]]の[[松井充]]により[[線形解読法]]が発表され、1993年~1994年にかけてDESの解読と実験が行われた。1995年に線形攻撃法と差分攻撃法に対して証明可能な安全性を有する暗号として MISTY1 が発表された。その後、様々な攻撃方法の開発と線形差分特性などを指標とする安全性評価の研究が進んだ。
▲;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が制定された。
== 関連項目==
94 ⟶ 104行目:
* [[SPN構造]]
{{cryptography navbox|block}}
[[category:暗号技術|ふろつくあんこう]]▼
[[Category:暗号プリミティブ]]
[[Category:ブロック暗号|*]]
|