「ブロック暗号」の版間の差分

削除された内容追加された内容

インライン

2023年6月13日 (火) 02:14時点における最新版

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

概要

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

E_{k}^{-1}(E_{k}(m))=m

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

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

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

構造

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

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

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

用途

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

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

擬似乱数列の生成にも用いられる (see 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
- 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

安全性

計算量的安全性

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

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

ショートカット法

ブロック暗号アルゴリズムの弱点を用いて鍵の全数探索以下の計算量で鍵（の一部）を求める手法を総称してショートカット法と呼ぶ。ショートカット法には多くの種類があるが、ここでは代表的なものを列挙する。

差分解読法（差分暗号解読） 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乗攻撃 $\chi ^{2}$ Attack
mod n攻撃 en:Mod n cryptanalysis
XSL攻撃 en:XSL attack

ショートカット法が存在するアルゴリズムは学術的には「解読可能」と呼ばれるが、その必要な計算量が現実的であるかどうかは考慮されない。学術的に解読可能であることは、必ずしもその暗号を利用したシステムの破綻につながるわけではない。しかしながら、設計者が想定した強度を有していないという事実は、その暗号アルゴリズムが信頼性の低い暗号アルゴリズムであることを意味する。

サイドチャネル攻撃

ハードウェアやソフトウェアに実装された暗号を、アルゴリズムではなく消費電力や実行時間等の情報を用いて攻撃する手法をサイドチャネル攻撃と呼ぶ。サイドチャネル攻撃は実装とアルゴリズムの両方に影響される。

単純電力解析 Simple Power Analysis
電力差分攻撃 en:Differential power analysis
タイミング攻撃 en:Timing 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ボックスを変更し差分解読法に対処していたことが後に明かされた^[2]）。
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等があげられる。また、実装されたハードウェアやソフトウェアに対する攻撃（サイドチャネル攻撃）も活発になった。

脚注

[脚注の使い方]

^ ただし、KASUMIのように復号が定義されていないブロック暗号もある。
^ Coppersmith, Don (May 1994). “The Data Encryption Standard (DES) and its strength against attacks” (PDF). IBM Journal of Research and Development 38 (3): 243.

@@ 1行目: / 1行目: @@
-'''ブロック暗号'''（- あんごう、Block cipher）とは、[[共通鍵暗号]]の一種で、ブロックと呼ばれる固定長のデータを単位として暗号化復号を行う暗号である。これに対して、ビット単位やバイト単位で暗号化を行う暗号は[[ストリーム暗号]]と呼ばれる。
+'''ブロック暗号'''（ブロックあんごう、{{lang-en|Block cipher}}）とは、[[共通鍵暗号]]の一種で、固定長のデータ（ブロックと呼ぶ）を単位として処理する暗号の総称である。これに対して、ビット単位やバイト単位で処理を行う暗号は[[ストリーム暗号]]と呼ばれる。
 == 概要 ==
-ブロック暗号は、NbビットのブロックとNkビットの鍵を入力として、Nbビットのブロックを出力する、暗号化(encryption) ''E'' と復号(decryption) ''E<sup>-1</sup>'' の２つのアルゴリズムからなる。任意の鍵''k''について、復号アルゴリズムは暗号化アルゴリズムの逆関数になっていて、
+ブロック暗号は、<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>
-を満たす（''m''は任意のブロック）ようになっている。暗号化アルゴリズムの入力ブロック、復号アルゴリズムの出力ブロックは平文、暗号化アルゴリズムの出力ブロック、復号アルゴリズムの入力ブロックは暗号文という。任意サイズの平文を扱うために、[[暗号利用モード]]が用意されている。
+を満たす（<math>m</math> は任意のブロック）ようになっている<ref>ただし、[[KASUMI]]のように復号が定義されていないブロック暗号もある。</ref>。暗号化アルゴリズムの入力ブロックおよび復号アルゴリズムの出力ブロックは通信文、暗号化アルゴリズムの出力ブロックおよび復号アルゴリズムの入力ブロックは暗号文という。任意の長さの通信文を扱うために、[[暗号利用モード]]が用意されている。ブロック暗号は確定的暗号であり、鍵を一つ固定すると、同じ平文は必ず同じ暗号文に暗号化される。すなわち、同じ暗号文があった場合、そのブロックの平文は同じであるという情報が漏れてしまう。暗号利用モードでは、このような問題を解決する機能ももつ。
+換字と転置を組み合わせた共通鍵暗号でも、複数の法に基づく大きなブロックの換字式[[ストリーム暗号]]と[[転置式暗号]]を組み合わせることで解読の著しく難しい暗号が構成できる。
-ブロック長Nbは64bitや128bitが代表的である。暗号アルゴリズムによっては、ブロック長をパラメータで指定でき、ブロック長を変えられるものもある。
+代表的なブロック暗号として、米[[NIST]]が制定した[[Data Encryption Standard|DES]] (Data Encryption Standard)や[[トリプルDES]]、[[Advanced Encryption Standard|AES]] (Advanced Encryption Standard) がある。日本製のブロック暗号として、[[MISTY1]]や[[Camellia]]などが知られている。
-鍵長Nkは 40/56/64/80/128/192/256bit などがある。
-代表的なブロック暗号として、米NISTが制定した[[DES]] (Data Encryption Standard, FIPS PUB 46)や[[AES暗号|AES]] (Advanced Encryption Standard, FIPS PUB 197)がある。日本産のブロック暗号として、[[MISTY1]]や[[Camellia]]などが知られている。
 == 構造 ==
@@ 19行目: / 17行目: @@
 ラウンド関数は置換や転置、論理演算、算術演算などのシンプルな部品で構成されていて、ラウンド関数を複数段、重ねることで十分な強度のスクランブルを行うものである。ラウンド段数は、通常、アルゴリズムの仕様によって指定されているが、セキュリティパラメータとして利用者が選択するものもある。
-ラウンド関数の主な構成法に、Feistel NetworkとSubstitution-Permutation Network(SPN)の２つがある。DES, MISTY1, CamelliaはFeistelで、AESはSPNの暗号である。
+ラウンド関数の主な構成法には[[Feistel構造]]と[[SPN構造]]の2つがある。DES, MISTY1, CamelliaはFeistel構造で、AESはSPN構造の暗号である。
-== 歴史 ==
+== 用途 ==
+ブロック暗号は公開鍵暗号に比して高速であるため、公開鍵暗号と組み合わせたハイブリッド暗号では公開鍵暗号で暗号化されたセッション鍵を用いた本文の暗号化・復号に用いられる。
-(1971～1976) 1971年頃にIBMでHorst Feistelにより開発されたLuciferが(民生用として)最初のブロック暗号とされている。1977年にLuciferをベースにして、DESが制定された。
+また、パスワードの保存のための一方向性関数として用いられたり (UNIXの/etc/passwd等) 、[[メッセージ認証コード]] (MAC) に用いられる。
-(1987～1991) 1987年にNTTのAkihiro ShimizuとShoji Miyaguchiにより [[FEAL]] が発表された。1991年にEli BihamとAdi Shamirにより差分解読が発表され、FEALは差分解読によって効率的に解読できることが判明した（DESは設計時に差分解読に対処していたことが後に明かされた）。
+擬似乱数列の生成にも用いられる (see [http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf NIST SP800-90]) 。
-(1992～1995) 1992年にMitsuru Matsuiにより線形解読が発表され、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が制定された。
+暗号標準として採用（もしくは推奨）されているブロック暗号には次のものがある。
+* 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/>
 == 関連項目==
@@ 34行目: / 101行目: @@
 * [[共通鍵暗号]]
 * [[暗号理論]]
+* [[Feistel構造]]
+* [[SPN構造]]
+{{cryptography navbox|block}}
-[[category:暗号技術|ふろつくあんこう]]
+{{DEFAULTSORT:ふろつくあんこう}}
+[[Category:暗号プリミティブ]]
-[[en:Block cipher]]
+[[Category:ブロック暗号|*]]