鍵長をどのように選択していくか 〜等価安全性と鍵長の関係：デファクトスタンダード暗号技術の大移行（5）（1/3 ページ）

[神田雅透，NTT情報流通プラットフォーム研究所]

　暗号を選択するということは、計算手法となる「アルゴリズム」と安全性の上限を決める「鍵長（ハッシュ関数ならばハッシュ長）」の両方を決めるということである。このうち、アルゴリズムについては、本連載の第3回や第4回で紹介したようなアルゴリズムを中心に選択していけば、国際的なトレンドから見てもまず問題はないであろう。

　残る問題は「鍵長（ハッシュ長）をどの程度に設定するか」である。鍵長を長くすることは、安全性の上限を高くする効果がある一方で、処理性能の低下につながることが多い。従って、必要な「安全性の上限」を確保しつつ、「処理性能の低下」を許容範囲内に抑えるようにすることが、鍵長を設定するうえで重要となる。

　今回は、この安全性の上限と鍵長の関係について紹介したい。なお、安全性の上限という言葉は耳慣れないと思うが、ここでは「暗号アルゴリズムに脆弱性が含まれておらず、仕様上期待される安全性が確保されている状態」のことを意味しているものと解していただきたい。つまり、たとえ完ぺきな暗号アルゴリズムであっても「これ以上安全」ということは理論上あり得ず、逆に暗号解読が成功したり脆弱性が見つかったりすれば必ず安全性が劣化するということである。

安全性の上限を求めるための最良の攻撃方法

　共通鍵暗号や公開鍵暗号では「秘密鍵を求める」ことが暗号解読の攻撃目標であり、またハッシュ関数では「衝突するような異なるメッセージ組を求める」ことが攻撃目標となる。これらの攻撃目標を達成するに当たり、アルゴリズム個別の脆弱性の存在には期待せずに、（効率は非常に悪いかもしれないが）確実に攻撃を成功させることができる方法のことを「最良の攻撃方法」という。

　例えば、共通鍵暗号では差分解読法［参考文献1］や線形解読法［参考文献2］などが強力な暗号攻撃方法として知られているが、これらはアルゴリズム個別の脆弱性を利用した攻撃方法である。このため、アルゴリズムに脆弱性がなければこれらの攻撃方法は有効ではない。

　これに対して、鍵全数探索法は鍵候補を1つ1つ検査して、求める秘密鍵かどうかを判定するため、アルゴリズムに依存することなく、どんな共通鍵暗号に対しても有効な攻撃方法である。このため、鍵全数探索法が共通鍵暗号に対する最良の攻撃方法ということになる。

　つまり、「最良」というのは、ある個別のアルゴリズムに対して攻撃効率がよいという意味ではなく、どのアルゴリズムに対しても攻撃方法として外れがないという意味であり、理想的なアルゴリズムであってもこの攻撃方法で必ず攻撃が成功するということである。このことから、安全性の上限は最良の攻撃方法を利用したときの強度で評価されることになる。

　表1は、それぞれの暗号技術に対して、現在知られている最良の攻撃方法をまとめたものである。

暗号技術分野 最良の攻撃方法 共通鍵暗号 鍵全数探索法 鍵候補を1つ1つ検査して秘密鍵を見つける方法 公開鍵暗号 デジタル署名 素因数分解型 数体ふるい法 合成数を効率的に素因数分解するためのアルゴリズム 離散対数問題型 指数計算法 有限体上の離散対数問題を効率的に解くためのアルゴリズム 楕円曲線型 ρ法（Pollard法） 楕円曲線上の離散対数問題を効率的に解くためのアルゴリズム ハッシュ関数 誕生日攻撃 バースデー・パラドックスの理論（母集団の平方根程度の個数の要素をランダムに選び出すと、その中に同一の要素となるものが少なくとも一組存在する可能性が高いという理論）に基づいた攻撃

表1　暗号技術別の最良の攻撃方法