ITpro: 『なぜ暗号は当事者しか読めないのか？』

ITpro の『なぜ暗号は当事者しか読めないのか？』(2008年11月12日公開)という解説記事より。

タイトル通り、暗号の性質とアルゴリズムが紹介されているのですが、このお題に対する内容としてはおなじみの流れになっています。共通鍵暗号についてはふんふんといった感じで読み進められたのですが、公開鍵暗号(RSA暗号)にきては、どうしても突っ込みたくなる記述が出てきました。

一つ目は

100けたを超える整数の素因数分解を，効率よく行う方法がまだ発見されていない

という部分。「効率よく」の意味が、多項式時間アルゴリズムという意味であれば、整数の桁数が何桁であれ、この記述に誤りはありません。しかし、実用的な時間内で分解するという意味であれば、そしてRSA暗号の現実的な安全性を議論するのであればこちらの意味でなければいけないのですが、100桁程度の整数の素因数分解は事実としてすぐに求められるのですから、この記述はまぎらわしいと言わざるを得ません。こんな感じの記述をしたいのならば、整数はせめて300桁(1024ビット)を越えないと、現実的な難しさを主張できません。

二つ目は

最先端のコンピュータでも，256けたの整数を素因数分解するには，1000万年から数百万年かかるといわれている

という部分。1000万年から数百万年って何？というつっこみは置いておくにしても、想定している計算機の性能や台数がわからないものの、256桁(850ビット)程度の整数の素因数分解にこれだけの時間がかかるとは到底思えないのです。

などと思いながら記事を最後まで読むとオチがありました。この記事は2004年に書かれたものなのですね。どうりで共通鍵暗号に AES が登場しないなど、何となく内容の古さを感じたのはそのせいだったのですね。いや、でも2004年だとしても、たった4年前ですので、上の指摘はまったく成立するはずです。どうしたらこの辺の感覚をわかってもらえる、というか、CRYPTREC レポートの内容を受け入れてもらえるのでしょうかねえ。