PR

図4 共通鍵暗号を解読する
暗号方式そのものにとんでもない「抜け道」がない限り,地道に解読するしかない。そのための方法は大きく3 種類ある。

強度
コンピュータの処理時間で測る

 暗号で気になるのは,その「強さ」。セキュリティが気になるインターネット・バンキングのWebページには,「128ビットの鍵を使っているので信頼性は万全です」と書かれていたりする。鍵の長さだけで暗号の強度を判断できるのだろうか。暗号の解読方法を見てみよう。

共通鍵と公開鍵で解読法は違う

 暗号の解読については,共通鍵暗号と公開鍵暗号で大きく異なる。まずは共通鍵暗号からみていこう(図4[拡大表示])。

 共通鍵暗号の解読方法の基本は,「コンピュータを用いていかに効率よく鍵を探索できるか」にある。つまり,すべての鍵を片っ端から調べる「総当たり法」を基準として考える。

 総当たり法以外の手法として代表的な解読法には,差分解読法と線形解読法がある。ただし,差分解読法や線形解読法はDESに対しては有効であることが確かめられているが,ほかの共通鍵暗号でも成り立つとは限らない。

 暗号開発者は既知の解読法をすべてクリアし,総当たり法よりも効率のよい解読法がないように暗号を設計する。逆に言えば,総当たり法より効率的な解読法が見つかれば,その暗号方式は破られたことになる。実際,DESの解読で総当たり法より効率の優れた線形解読法を考え出した三菱電機の松井充氏は,「DESを破った」研究者として世界的に有名である。

共通鍵の強さは鍵の長さで決まる

 総当たり法よりも効率的な解読法がない場合,共通鍵暗号の強さは総当たり法で解読したときの時間で比べる。解読にかかる時間が長い暗号ほど強い。

 絶対的な強さは,比較的簡単に求めることができる。パラメータは2つしかない。一つは鍵の総数であり,もう一つはコンピュータが1個の鍵をチェックする時間である。鍵の総数は鍵の長さで決まる。

 1秒間に1兆個(1014)の鍵をチェックできるコンピュータがあったとしよう。このコンピュータで解読するとき,鍵の長さが40ビットなら一瞬で,56ビットでも数分で解読してしまう。ただし,128ビット長の鍵なら,鍵の総数はおよそ1038。解読するまでにかかる期間は大ざっぱに3×1019年ほどとなる。インターネット・バンキングのデータを盗聴されても,解読される心配はなさそうだ。

公開鍵暗号は数学的難しさに依存

 公開鍵暗号の解読はどうだろう。こちらの場合ももちろん鍵の総当たり法は使える。しかし,公開鍵暗号で使う鍵は通常512ビットや1024ビットといった長さである。鍵の総当たりで正解を見つけるには,共通鍵暗号のときよりさらに困難であり,とても現実的ではない。

 したがって,公開鍵暗号の解読は別の方法で議論されている。それは,「公開鍵暗号が依存している数学的な難しさを打ち破れないか」というもの。公開鍵暗号は素因数分解や離散対数問題が難しいという事実の上に成り立っている。つまり,これらを簡単に解く方法が見つかれば暗号の解読時間を劇的に短縮できるというわけだ。

 今のところ,公開鍵暗号の安全性を揺るがすほど劇的に計算時間を短縮する方法は見つかっていない。ただし,あくまでも「今のところ安全である」というだけで,将来まで安全かどうかはわからない。