NewsInsight

日伊の研究者らが発案、ベンチャー企業を設立

「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは

2008/04/11

　すべての暗号はいずれ破られる。2000年前のシーザー暗号の時代から高度な暗号技術が一般化したデジタル通信の現代に至るまで、それが暗号通信の歴史が証明し続けた事実であると同時に、もっとも人口に膾炙したクリシェでもあった。例えば、鳴り物入りでリリースされたDVDのコンテンツ暗号技術「CSS」（Content Scramble System）が、リリースからわずか数年で10代のノルウェー人ハッカーに破られたことは記憶に新しい。

---

【追記】（2008年4月15日）

この記事は取材に基づいて執筆したものですが、一部専門家らから「CAB方式暗号は解読不能」というのは誇大表現ではないかとの疑義が呈されています。アルゴリズムの公開や第三者による検証がない現在、この記事に登場するCAB方式が発案者・実装者の主張通り画期的な暗号方式で、本当に解読が不可能であるかどうか分かりません。現在、専門家の協力を呼びかけて東京理科大学の大矢雅則教授はじめ入山聖史博士に追加取材を依頼中です。記事中、不明瞭だった部分も含めて改めて続報を掲載させていただきます。

【追記】（2008年4月21日）

続報記事掲載は5月半ばを予定しております。

【追記】（2008年6月6日）

追加取材を5月29日に行いました。続報記事を予定していましたが、以下の理由で続報記事の掲載を延期させていただきます。

理由の1つは同席する予定だった暗号研究者が欠席したためです。その結果、当記事作成に当たった編集部の西村が単独で追加の取材を行う形となりました。追加取材の場では、再度、CAB暗号方式の概要および現在進めている安全性検証について話を聞きました。

また、ビジネス面での進捗や情報の公開準備についても確認しました。クリプト・ベーシック社が特許申請を今後3カ月程度をめどに行う予定で弁理士と検討を進めていること、それに引き続き早ければ年内から年明けにも、いずれかの学会で学会発表を行う予定もあることが判明しました。

このため、最短で3カ月、最長でも2年程度で、CAB暗号方式のアルゴリズムに関する情報がオープンとなることが分かりました（特許庁に出願した特許申請は、出願から1年半後に公開特許公報に掲載されて、パブリックになります）。実装のオープンソース化も視野に入れているとのことです。

以上のことから、肝心の発明部分が非公開の状態のままにさらなる追加取材を行うよりも、専門家が客観的判断を下せるだけの十分な情報が公開された段階で、追加取材および記事掲載を行うべきと判断いたしました。

今後もクリプト・ベーシック社の情報公開準備に関する進捗については、随時同社に問い合わせ、このページに追記していきます。

---

　現在、ネット上の商取引や機密情報の扱いに広く使われている暗号方式の1つ、RSA暗号も原理的には解読が可能だ。RSA暗号は、大きな数の素因数分解の難しさに、その安全性の基礎を置いている。計算量が膨大になるため、事実上解読が困難だが、その困難さの度合いは利用する暗号鍵の長さに依存する。

　鍵長を長くすれば解読は困難になる。しかし、鍵が長いと今度は鍵生成や暗号化、復号化の計算コストが大きくなる。このためRSA暗号は、計算コストと必要な暗号強度のバランスを取りながら運用し続けるという宿命を背負っている。暗号方式はRSAとは異なるが、DVDの暗号が破られたのも鍵長が40ビットと短かったことが1つの原因とされるが、それはDVDプレーヤーの限られた処理能力を考慮してのことでもあった。

偶然の出会いから生まれたアイデア

　こうした暗号技術利用の常識を打ち破る、まったく新しい暗号方式が現れた。

　「われわれの開発した暗号方式は、数学的に解読が不可能であると証明されています」。

　こう言い切るのは、ローマII大学のアカルディ教授とともに新暗号「CAB方式」（Crypto Alarm Basic：仮称）の基礎となる数学理論を考案した東京理科大学理工学部長 量子生命情報研究センター長の大矢雅則博士だ。従来の暗号のように「解読が困難」なのではなく「解読が不可能」だという。

　「野球のピッチャーにたとえると、こういうことです。これまで行ってきた暗号アルゴリズム研究は時速140キロの記録を破って150キロ、155キロを目指すというものです。われわれの暗号方式は人間のピッチャーの代わりにピッチングマシーンを使って、いきなり時速200キロを出してしまったという感じです」。

　東京理科大学情報科学科助教で東京理科大学量子生命情報研究センターの入山聖史博士はそう語る。従来の方式とはまったく異なる地平を開いたという暗号方式は偶然の出会いから生まれたという。

　「われわれはもともと数学研究者であって、暗号とかソフトウェアとは関係がないんです。ローマ大学のルイジ・アカルディ教授とある数学分野の共同研究をしてきたのですが、後にアカルディ教授からその数理を聞いたソフトの専門家であるマッシモ・レゴリー准教授が、これは暗号に使えるのではないかと言い出したんです。それが始まりです。暗号研究者たちが活発に議論している場所とは全然かけ離れた地点での研究が、偶然暗号に使えることが分かった。ですから、従来の暗号方式とは枠組みがまったく異なるのです」（大矢教授）

実験実装を行い、ベンチャーを起業

　CAB方式の将来性に着目し、実験実装を行ったのが2006年。それから約2年間、学会発表やメディアへの公表、特許申請などは一切行わず、さまざまな用途に合わせたプロトコルの開発を進めてきたという。東京大学理学部を卒業後、米ロチェスター大学大学院へ進んだほか、ローマ大学、ハイデルベルグ大学など欧米の大学から招待を受けてきた大矢教授だが、その行動も欧米流だ。

　「学会で発表をして名誉だけを受けるという選択肢もありましたが、われわれはまず特許をとること、社会に出すことを考えました」（大矢教授）。

　日本法人のクリプト・ベーシックは昨年の10月に起業。現在立ち上げの段階で、大矢教授、入山博士らは技術参与として携わっている。一方、2年前に設立したイタリアのクリプト・アラーム社は、銀行や通信キャリアとの共同開発、契約を進めており、あるヨーロッパの大手通信キャリアとは、すでに携帯電話端末のBluetooth通信でCAB方式暗号の実装を終えている。

　現在、パフォーマンスの改善やアルゴリズム開発を日伊共同で研究しており、どういう形態でCAB方式暗号を世の中に出していくかを検討中だという。

ほかの公開鍵暗号方式はCAB方式の特殊な場合

　量子暗号など原理段階にとどまる基礎研究を除くと、現代の暗号研究は関数探しの競争となっている。

　RSA暗号は素数のかけ算と、その逆の素因数分解という1種の関数を利用した暗号方式だ。これは楕円曲線暗号やElGamalといった公開鍵暗号方式か、DESやAESといった共通鍵暗号方式かを問わず同じで、暗号化には何らかの関数を使う。

　CAB方式では、その関数自体が無限個の中から利用者が自由に選べて、いつでも変えられるのだという。

　「例えば、xのm乗というのも1つの関数ですし、2xも関数です。実際には逆関数の計算が極めて難しい関数の集合を利用していますが、こうした関数からなる無限集合から鍵となる関数をピックアップします。盗聴者の探索しなければならない鍵空間は無限大ですから、鍵を推定できる確率はゼロです」（大矢教授）。

　CAB方式は、適当な初期値を取ることで任意の長さのランダムなバイナリ列を生成するアルゴリズムや、公開鍵分配アルゴリズムからなる。CAB方式で使われる公開鍵配分アルゴリズムは、Diffie-Hellmanやそれらの変形を包含する一般化とは異なる、はるかに複雑性の高いものだという。「ほかの公開鍵暗号方式は、表現方法や公開鍵の数を変えることでCAB方式に含まれることが数学的に証明されています。ほかの公開鍵暗号方式はCAB方式の特殊な場合なのです」（大矢教授）。

　また鍵だけでなく、暗号に使う関数自体も毎回異なるため、攻撃者が任意のテキストを入力してそのアウトプットから関数やパラメータを推定する攻撃、いわゆるクリアテキストアタックもCAB方式暗号では無効だという。

解読困難と解読不能の違い

　RSA暗号では現在、一般的には1024〜2048ビットの鍵が用いられており、用途によっては十分な安全性がある。例えばRSAセキュリティ社自身が1991年から継続して行っていた暗号破りコンテストでは2005年に663ビットの鍵が破られているが、これには80台のOpteronサーバ（2.2GHz）を使い、3カ月を費やしたという。RSA暗号で最も広く使われている1024ビットの鍵（10進数で309桁の素数）については10万ドル（約1000万円）の賞金が掛けられていたが、誰も素因数分解に成功していない。

　1000万円では見合わないのだろう。しかし、数億円なら見合うかもしれない。2003年に2人の研究者が発表した理論上の専用解読器「TWIRL」を数億円かけて実際に製作すれば、1024ビットの鍵も解読できるかもしれない。このことから現在、RSA暗号では鍵は少なくとも2048ビット以上が望ましいとする暗号研究者がいる。

　RSAセキュリティは2007年になって、この解読コンテストを終了させている。それは、解読コストが十分大きければ、必要な暗号強度は確保できるという社会的な認知が得られたからだという。

　ただ、最終的に暗号技術の恩恵にあずかるべき消費者や一般市民にとって「事実上十分安全だ」という言い方しかできない現在の暗号技術では、心理的な不信感をぬぐうのは難しい。例えばSSLを使ったオンラインショッピングでクレジットカード番号の入力を躊躇するユーザーは、まだ多い。

　1994年、アメリカ人研究者のピーター・ショアは量子コンピュータを使って素因数分解が比較的容易に解けることを理論的に示し、暗号研究者たちに衝撃を与えた。さらに2001年にはIBMの研究者らが「15＝5×3」という素朴な問題ではあるものの、量子コンピュータのプロトタイプを使って素因数分解を実演してみせたことで、RSA暗号は破られうると実証されている。

　「RSA暗号では鍵長を長くして、例えばNASAのようなところでは解読に1億年かかるようなものを使っています。しかし、量子コンピュータというのは、例えば通常のコンピュータで2の100乗秒かかる計算を、100秒に短縮してしまうような技術ですから、1億年の1億倍のさらにその1万倍の時間が数十秒になるということです」（大矢教授）

　もちろん量子コンピュータの実現は、まだ当面先の話だが、量子コンピュータを使っても解くことができないというCAB方式は、RSA暗号に取って代わる次世代の暗号方式なのだという。ムーアの法則に従ってコンピュータの計算能力が爆発的に上がっても、あるいは量子コンピュータが実現されても、それでも「解読不能」と言い切れるのがCAB方式の強みだ。

鍵生成や暗号化処理の軽さでストリーミングにも対応

　暗号化の処理速度の速さもCAB方式のウリだという。

　「例えば4MBほどある聖書のテキストを、その聖書に含まれるビット数と同じ長さの鍵を使って暗号化するのに、一般的なPCでも1秒もかかりません」（入山博士）

　CAB方式はブロック暗号だが、処理が高速であるためストリーミング映像への適用も可能だという。入山博士はデモンストレーションで一般的なノートPC2台を使って映像ストリーミングを実演。数MbpsのビットレートのMPEG映像を8ギガビットと非常に長い鍵を使って暗号化し、サーバ・クライアントで送受信してみせた。再生は滑らかで、CPU負荷も15％前後と映像コーデックの処理以上に高くない。

　「デジタルコンテンツの保護強化や、企業のビジネス文書保護など、応用はいろいろと考えています。基本的にRSAで行っていることはすべてCABで代替できると思っています」（入山博士）

　鍵生成も高速だ。RSA暗号における鍵生成は、大きな素数の組み合わせを見つける比較的重たい処理だ。鍵長が長くなればなるほど処理に時間がかかる。しかし、CAB方式では「10万ビットの鍵でも1秒未満で生成できます。携帯電話のように処理能力の低い端末にも向いています。例えば128ビットの鍵を生成するのに2MHzのプロセッサで60ミリ秒程度しかかかりません」（入山博士）。現在の実装はJavaによるもので、プログラムサイズは約60KBとコンパクト。非力なデジタルガジェットでも利用できるのがRSA暗号と比較したときのCAB方式の強みという。

　長い鍵が簡単に生成できるため、任意のタイミングでユーザーは鍵を変えることができるのだという。

公開鍵暗号を超える暗号技術の革新となるか

　CAB方式は、まだ実績がなく事実上未公表の技術だ。情報が公になっていくにつれて、専門家たちがどう反応するかは未知数だ。

　また、その安全性についても、理論的裏付けがあるとはいえ今後は専門家による検証が欠かせない。ランダムな数列生成ではNIST（米国立標準技術研究所）で使われるテストで検証済みだが「今のところCAB方式を正当に評価できる方法や機関は存在しない」（大矢教授）のが現状だ。

　専門家による検証やビジネスでの展開を考えると、どんなに早くても実利用がスタートするには、まだ数年かかるだろう。しかし、もし今後、「CAB方式は解読不能と証明済み」ということが第三者によって確かめられ、その実用性が認められれば、CAB方式は公開鍵暗号方式の発明に匹敵するインパクトをデジタル社会に与える可能性があるかもしれない。

---

【訂正】（2008年4月17日）

• 初出時、理論発見者が大矢教授単独だったように書かれていた個所がありましたが、ローマII大学のアカルディ教授との共同研究の成果です。本文を訂正しました。
• 初出時、会社の起業メンバーに大矢教授が含まれるという表現がありましたが、これは誤りです。「学会で発表をして名誉だけを受けるという選択肢もありましたが、われわれは会社にしました」とした表現を、「学会で発表をして名誉だけを受けるという選択肢もありましたが、われわれはまず特許をとること、社会に出すことを考えました」と改めました。

以上、訂正するとともに関係者と読者の皆様ににお詫び申し上げます。

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）