暗号の安全性
暗号の強度
暗号を使う際には，鍵を知らない第三者によって解読される可能性はないかどうか調べることが重要になる．ここでいう「解読」とは，傍受した平文や暗号文のデータから暗号化に使われた鍵(あるいは等価な情報)を得ることも，別の暗号文に対する元の平文のどんな情報も得ることもできないという意味である．
暗号の安全性の観点からは，暗号の強度は次のように分類される．
- 秘匿性
- 完全解読困難
暗号文より平文を求めることが困難なこと． - 部分解読困難
暗号文より平文の部分情報を求めることが困難なこと． - 強秘匿
どのような部分情報も部分解読困難なこと．
- 完全解読困難
- 頑強性
どのような関係 F に対しても，攻撃者がC = E(m) から m' = F(m) を満足するような C' = E(m') を作成 (C を盗聴し， C --> C', m --> m' )できない．
すなわち，暗号文から平文の内容を知ることはできず，かつ暗号文を操作することにより対応する平文に意図的な変更を加えることもできない．
最も安全な暗号は，攻撃者に適応的選択暗号文攻撃を許したとしても，強秘匿でありかつ頑強性を保持した方式である．
暗号の安全性評価には暗号文のランダム性や暗号の構造を調べるほか，これまでに知られている攻撃法に対する強度を調べる必要がある．
総当り攻撃に対する安全性
- 情報理論的安全性(無条件安全性)
たとえ攻撃者が無限大の計算機資源を所持していたとしても，暗号を破ることができないことが保証される（完全秘匿）．
鍵使い捨て方式のバーナム暗号(ワンタイムパッド)は，情報理論的安全性を持つ暗号方式である．
- 情報理論的に安全の定義
平文 m，鍵 k に対して，暗号文 c が暗号化アルゴリズムである E により，c = E (k, m)
と表される共通鍵暗号系を考える．
平文 m は集合 M から，ある確率分布によって生起すると仮定する(確率変数 ~M)．鍵 k は集合 K から，ある確率分布によって生起すると仮定する(確率変数 ~K)．暗号文 c は暗号化アルゴリズム E によって定まる集合 C 上のある確率分布によって生起すると仮定する(確率変数 ~C)．
このとき，∀c∈C, ∀m∈M; Pr(~M = m|~C = c) = Pr(~M = m)
が成り立つとき，暗号系（~K,~M,~C）は情報理論的に安全（完全秘匿）であると言う． これは，暗号文を入手したとき，その中に平文を解読するための情報が一切含まれていないことを意味している．すなわち，暗号文を見る前と後で情報量が同じである． - 情報理論的に安全な暗号系の鍵長と平文長の関係に関する定理
情報理論的に安全 ⇔ |K|≧|M|
ここで，|K| は鍵の長さ，|M| は平文の長さある．
■背理法による証明：
|K|≧|M| でない，すなわち |K|＜|M|と仮定する． このとき，鍵空間 K から平文空間 M への完全なるマッピングは存在し得ない． すなわち，ある平文 m∈M と暗号文 c∈C が存在して復号アルゴリズムを D としてD(c) ≠ m （∀k∈K）
となる． これは、Pr(~ C=c|~M=m)=0 であることを意味するが，これは定義 Pr(~M=m|~C=c) = Pr(~M=m) に矛盾する．ゆえに，|K|≧|M| となる．
- 情報理論的に安全の定義
- 計算量的安全性
攻撃者が所持する計算機資源を全て費やしたとしても、暗号が破られるまでに十分な時間がかかることが保証される．現在の多くの暗号方式は，計算量的安全性に基づいている．
共通鍵暗号の安全性
共通鍵暗号の安全性は，以下を前提に考えられている．
- 暗号アルゴリズムは公開されている．
- 秘密鍵を攻撃者から守る．
共通鍵暗号の安全性を確保するための対処には次の2つの観点がある．
- たとえ攻撃者が無限大の計算機資源を所持していたとしても，暗号を破ることができないことが保証される場合，完全秘匿(無条件安全性)という． 真の乱数を前提としたバーナム暗号は無条件安全性がある． しかし，一般的な共通鍵暗号方式にはこのような無条件安全性は保証できないため，現状の計算機能力を考慮しても，解読に非常に時間がかかるようなアルゴリズムおよび鍵長を選択することにより安全性を確保する．これを計算量的安全性という．
一般的には，この計算量的安全性が保てるように暗号方式や鍵長などの暗号パラメータを選択することが重要になる． - 鍵の運用で対処する．すなわち，同じ秘密鍵を長く使用しないようにする． 例えば，情報通信用の鍵はセッション鍵として毎回変更する． これ により，鍵を解読される危険を減少させることができる(鍵を解読されたとしても，その時点には鍵が変更されている)．
共通鍵ブロック暗号の攻撃法は全ての鍵をしらみつぶしに探索するBrute-force Attackと暗号アルゴリズムを解析し，統計的特性を利用して鍵の探索範囲を限定するShort-cut Attackに分類できる．
現在のところ，ある共通鍵ブロック暗号が全ての攻撃に対して安全であると証明できる実用的な方法は知られていないので，これまで知られている暗号攻撃法に対して個別に，解読に必要な計算量を評価する必要がある．
DESの解読については，次のような例が報告されている．
RSA Security社が主催した DES解読コンテスト(1997~)の第4回(1999.1)に米国の非営利団体 EFF(Electronic Frontier Foundation)が全数探索により約22時間15分で解読した． 25万ドルで開発したDES解読器とインターネット上の約10万台のPCを用いて1秒間に鍵約2,450億個を検証したといわれている．
また，DES暗号に対し暗号攻撃にかけるコストと暗号の解読時間を計算した例を表に示す．ここで，計算機の処理能力は，Mooreの法則に従い1.5年で2倍 (10倍/5年)になると仮定している．
| 攻撃者 | 個人 | 企業 | 国家 |
| 予算 | 100万円 | 10億円 | 1兆円 |
| 解読時間 | PC1000台 | FPGA/ASIC | ASIC |
| 1995年 | 1.5年 | 6分 | 0.4秒 |
| 1998年 | 135日 | 90秒 | 0.1秒 |
| 2001年 | 34日 | 23秒 | 23m秒 |
| 2004年 | 8.4日 | 6.0秒 | 6.0m秒 |
| 2007年 | 2.1日 | 1.5秒 | 1.5m秒 |
| 2010年 | 12.6時間 | 0.4秒 | 0.4m秒 |
| 2013年 | 3.1時間 | 0.1秒 | 0.1m秒 |
| 2016年 | 47分 | 25m秒 | 25μ秒 |
| 2019年 | 12分 | 6.0m秒 | 6.0μ秒 |
| 2022年 | 3分 | 1.5m秒 | 1.5μ秒 |
このように，DESの56ビットの鍵に対しては，総当り攻撃法に対しても安全とは言えなくなってきている．現状，一般的なセキュリティに対する共通鍵暗号の鍵長は128ビットあれば十分と考えられている．
公開鍵暗号の安全性
鍵サイズと解読計算量
公開鍵暗号では，攻撃の難しさが素因数分解問題や離散対数問題といった数学上の問題を解く難しさに対応している．
暗号方式による解読計算量の相違を計算した例を表に示す．同じ解読計算量に相当する鍵長を比較したものである． 1024ビットの RSA暗号と 160ビットの楕円暗号が解読計算量的には同等であることを示している．同じ安全性を保つために必要な DSA/RSA暗号のビット長が急激に増大するのが分かる．(暗号化処理の性能が低下する)．
| セキュリティレベル (bits) | 共通鍵暗号 鍵サイズ(bits) | 楕円暗号 nサイズ(bits) | DSA/RSA 法サイズ(bits) |
| 56 | 56 | 112 | 512 |
| 80 | 80 | 160 | 1024 |
| 112 | 112 | 224 | 2048 |
| 128 | 128 | 256 | 3072 |
| 192 | 192 | 264 | 7680 |
| 256 | 256 | 512 | 15360 |
また，RSA暗号に対し，暗号攻撃にかけるコストと暗号の解読時間を以下の前提の基に計算した例を表に示す．
- 1.5年で計算機の処理能力は2倍
- 200MIPSの計算機が20万円
| 攻撃コスト | 100万円 | 10億円 | 1兆円 | |||
|---|---|---|---|---|---|---|
| RSA暗号 | 512 | 1024 | 512 | 1024 | 512 | 1024 |
| 1999年 | 30年 | 3 x 10 8年 | 11日 | 3 x 105年 | 16分 | 3 x 102年 |
| 2004年 | 3年 | 3 x 10 7年 | 1.1日 | 3 x 10 4年 | 1.6分 | 30年 |
| 2009年 | 110日 | 3 x 10 6年 | 2.6時間 | 3 x 10 3年 | 9.5秒 | 3年 |
| 2014年 | 11日 | 3 x 105年 | 16分 | 3 x 102年 | 0.95秒 | 110日 |
| 2019年 | 1.1日 | 3 x 104年 | 1.6分 | 30年 | 0.095秒 | 11日 |
| 2024年 | 2.6時間 | 3 x 103年 | 9.5秒 | 3年 | 0.0095秒 | 1.1日 |
512ビットのRSA暗号に対しては，2009年時点で企業レベルの攻撃者を想定すると数時間のオーダで解読される可能性があることを示している．1024ビットであれば，今後10年程度は企業レベルの攻撃者に対しても解読は困難である．
Brentの予測式
Brent[*1]は，1960 年代から現在までに素因数分解された合成数のサイズと年次推移を調査した結果，それらのサイズの年次増加曲線は，新アルゴリズムの開発とMoore の法則 (半導体素子の集積度が 18 か月ごとに2倍という経験則) の両方に依存していることを確認した．そこで，このような傾向が今後も継続するであろうという仮定のもとでこの曲線を外挿し，将来その時点で現実的に素因数分解可能な合成数(またはその合成数の最小素因数) のサイズを与える予想式(実験式) を導出している．
- 10進数 D 桁の素因数分解問題が解かれる西暦年(数体ふるい法)
Y = 13.24 D1/3 + 1928.6
- 10進数 D 桁の素体離散対数問題が解かれる西暦年
素体離散対数問題の場合，素因数分解よりも 20 ビット分解読の手間が遅くなるという報告があり，次のようになる．Y = 13.24(D + 6)1/3 + 1928.6
これによると，ビット数と素体離散対数問題が解かれる年の関係は次のようになる．
1024ビット： 2019年
2048ビット： 2042年
4096ビット： 2070年
&bnsp;[*1] R. P. Brent, "Recent progress and prospects for integer factorisation algorithms," Proc. COCOON 2000, LNCS 1858, Springer-Verlag, pp.3-22, 2000.
公開鍵暗号の評価
情報処理進行事業協会/通信・放送機構の暗号技術評価報告書(CRYPTREC Report) の評価によれば，RSAとDSAの評価は次のようになっている．
- RSAの評価
- RSASSA-PKCS1-v1_5
電子署名法に係る指針に記載されている署名方式の1 つである． 証明可能安全性は示されていない． - RSA-PSS
RSA暗号化関数の一方向性およびランダムオラクルモデル(*1)を仮定することにより適応的選択文書攻撃に対して潜在的偽造不可能であることが証明されている． RSA-PSSの安全性は，RSA 自体の安全性，並びに素因数分解問題の困難性に大きく依存するため，これらの問題を解くアルゴリズム，及び計算機能力には，今後も十分に注意を払っていく必要がある．
(*1) ランダムオラクルモデル
理想的なランダム関数を仮定することにより安全性の証明を行う．但し，理想的なランダム関数は現実的でないため，実際にはランダム関数を実用的な一方向性関数で置き換えることにより実用的な暗号を構成する．この暗号方式は安全性が証明されたものではないが，安全性が証明された暗号方式の近似版としてある種の安全性の保証があると考える(1993 Bellare and Rogaway)．
- RSAES-PKCS1-v1_5
SSL3.0/TLS1.0 で使用実績があることから当面の使用を認める． 経験的安全性は有するが，証明可能安全性は持たず，実際に能動的攻撃が成立する可能性も無視できないので，実運用環境上における攻撃に対する対策を十分に施し細心の注意を払う必要がある． - RSA-OAEP
証明可能安全性を有する． RSAプリミティブの安全性は，n = pq 型素因数分解問題の困難 性に依存している．安全性の観点から法パラメータ n = pq のサイズは1024ビット以上のものを利用することを強く推奨する．
- RSASSA-PKCS1-v1_5
- DSAの評価
- 安全性は有限体上の離散対数問題の困難性に依存している．証明可能安全性は示されていないが経験的に安全である．
- 安全性の観点からパラメータ p のサイズは1024ビットを選択することを強く推奨する．
- 2001年10月にNISTがFIPS PUB 186-2(+change notice 1)に提示した擬似乱数生成系の修正に従うべきである．
／