RSA 56ビットRC5暗号の解読

――インターネットが実現した巨大計算力

(『朝日パソコン』1997年)
山形浩生
 

  1997年10月19日、RSA 56ビットRC5暗号が破られた。RSA社はネットスケープ等で使われている各種暗号化ソフトで知られ、自社アルゴリズムの強さ確認のため、解読コンテストを開催。今回の解読は、これに応えてDistributed.net が世界中のインターネット上のパソコンを組織して行ったもの。所要期間200日強。56ビットの暗号鍵は、個人レベルでは十分に安全とされていたが、それがこれだけ短期間で解読されたことで、情報セキュリティの常識が再考を余儀なくされた。同時にボランティアに基づく分散処理の新しい可能性がみごとに実証されたことになる。

とけない暗号はない

 世の中、とけない暗号はない。所用時間に差があるだけだ。たとえば、ある暗号文を解読する鍵が20通りあるとしよう。順に試していけば、平均では10回試せば解読できるだろう。しかし、もし暗号文に規則性があって、平均5回で解読できてしまったら、そんな暗号化アルゴリズムはあまり優れているとは言えないわけだ。

 たとえば電子メールソフトEudora日本版最新版には、NTT のFEAL 方式によるメール暗号化プラグインが付属する。だが、このFEALは理論値よりかなり少ない手間で解読できてしまうことが理論的に証明されている。一般庶民の個人メールなら(使い込みや浮気でもしてない限り)これで十分だが、金のからむシステムに使うのは不安だ(でもこれで電子商取引のシステムを組んだりしてるんだよなー)。

インターネットでパソコン遊び時間活用

 今回解読されたRSA 56ビットRC5暗号は、2の56乗通り、つまり7.2京通りの鍵がある。ペンティアム級のパソコンだと、解読までに8000年かかる。

 Distributed.netは、これを200日でなしとげた。スーパーコンピュータなどは使用していない。かれらが使ったのは、ネット上のパソコンだった。家庭やオフィスのパソコンのほとんどは、能力の9割以上を遊ばせている。ワープロ作業にペンティアムなんか必要ないし、多くのマシンはほとんどの時間、ひたすらスクリーンセーバを走らせて寝ている。かれらはこの無駄なCPUパワーに注目した。膨大な鍵を分割して世界中のボランティアに送り、分散処理をさせる。さらに、通常のパソコン使用には影響のない、バックグラウンドで空き時間だけCPUを使う専用ソフトもあわせて配布。運良く自分のマシンが答を発見したら、RSAからの賞金一万ドルのうち千ドルがもらえる。残りの賞金は、プロジェクトグーテンベルグ(書籍の電子化・オンライン化プロジェクト)に寄付。

日本2位の貢献も世界では1200位?!!

 呼びかけに応えて、世界からボランティア4000組強が参加。ネットワーク上に分散した世界最強のコンピュータが誕生したわけだ。筆者も職場のコンピュータを10台動員し、jp(日本)ドメインでは2位となっている(でも世界では1200位くらい。世界の壁は厚い!)。解読したのは、ベルギーの大学グループ。

 解読されたメッセージの中身は「It's time to move to a longer key length」(そろそろもっと長いキーに移行しよう)――まさにその通り。今回と同じ力を注げば、たとえば46ビットの暗号は1時間で破られてしまう。ちょっとした秘密でも、かなり長い鍵がないと安心できないわけだ。

 Distributed.netは、早速、64ビット版の解読に挑戦を表明。だが、本件の意義はセキュリティだけではない。これと前後して、メルセンヌ素数や地球外知性体からのメッセージ発見など、パソコンの空き時間を使う分散処理のパワーにがぜん注目が集まるようになっている。個々のセキュリティの不安と、人類全体として手に入れた巨大な計算力――今回の解読は、インターネットの両極端の可能性を同時にかいま見せてくれる、興味深い出来事なのだ。
 

朝日系トップに戻る  YAMAGATA Hiroo トップに戻る


YAMAGATA Hiroo (hiyori13@mailhost.net)