NY駐在員報告 「暗号技術の現状と課題（その2）」 1996年3月
先月に引き続き「暗号技術の現状と課題」について報告する。
解読されたRSA暗号
先月のレポートにRSA公開鍵暗号はこれまで解読されたことがないと書いたが、これは間違いだった（ごめんなさい）。94年4月26日にBellcore研究所（7つの地域ベル電話会社がサポートする研究所）のDr. Arjen Lenstraが率いるグループが、RSA129と呼ばれる暗号の解読に成功したと発表している。この暗号の公開鍵の一つ（二つの素数を掛け合わせた数字）は129桁の数なのだが、Lenstraが率いるグループはこれを素因数分解して、復号化のための鍵を手に入れた。
この暗号はRSA公開鍵暗号の発明者であるDr. Ronald Rivestなどが、100ドルの賞金付きの懸賞問題としてScientific American誌に掲載したものだ。Lenstraによれば、1MIPSのコンピュータで129桁の数字を素因数分解するには5000年必要だという。Lenstraは、この問題を解くために、インターネット上でボランティアを募集し、24カ国にまたがる600人を超える暗号解読チームを編成した。そして、平行して作業できるように問題を数多くの部分に分解し、インターネットを利用して素因数分解用のプログラムをメンバーに送付し、計算を依頼したのである。使われたコンピュータは約1600台、そのほとんどはパソコンとワークステーションだったと言われているが、中にはスパコンも含まれている。それから8カ月後に、600人以上のボランティアから結果がベルコアに送られ、2日かけてその結果をチェックし、それを統合して暗号が解読された。
参考までに、素因数分解された結果は以下のとおりである。
114,381,625,757,888,867,669,235,779,976,146,612,010,218,296,721,242,362,562,561,842,935,706,935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541＝
3,490,529,510,847,650,949,147,849,619,903,898,133,417,764,638,493,387,843,990,820,577 × 32,769,132,993,266,709,549,961,988,190,834,461,413,177,642,967,992,942,539,798,288,533
しかし、これでRSA公開鍵暗号の信頼性が損なわれたわけではない。600人以上のボランティア、1600台のコンピュータと8カ月の時間をかけてたった一つの暗号鍵が破られたにすぎない。現実に使われているRSA暗号の二つの素数を掛け合わせた数字は、通常150桁のものが利用されており、これを素因数分解することは129桁に比べて少なくとも数千万倍難しいと言われている。94年4月27日付けのニューヨーク・タイムズ紙でRivestもRSA公開鍵暗号の信頼性を保証すると述べている
心配があるとすれば、このグループを率いたLenstraが指摘するように、コンピュータウィルスを用いた暗号解読方法の可能性である。特定の計算をして結果を送り返すコンピュータウィルスを使えば、Lenstraのグループのように暗号が解読できるかもしれない。つまり、インターネットに接続された数百万台のコンピュータに暗号解読のためのウィルス（プログラム）を送り込み、コンピュータが遊んでいる時間に必要な計算を行い、その結果をインターネット経由であるコンピュータに送り返させる。そして、その結果をまとめて暗号を解読すればよい。Lenstraがボランティアを募集して行った作業を、コンピュータウィルスを送り込み、コンピュータの所有者の許可を得ないでコンピュータを利用すること（つまりCPU時間泥棒）によって実現するわけだ。あまり現実味がないように思えるが、可能性はあるだろう。インターネットに接続しているコンピュータの所有者は注意した方がよいかもしれない。
それから余談だが、Lenstraのグループは、賞金の100ドルをFree Software Foundationに寄付したそうである。
Kerberos
KerberosはMITによって開発された対称鍵暗号を利用したネットワーク型の認証システムである。暗号アルゴリズムにはDES (Data Encryption Standard) が採用されている。（ちなみに、「ケルベロス」はギリシャ神話に登場する冥界の入り口を守る頭が三つある犬だ。ネットワークのセキュリティを守るには適任かもしれない）
Kerberosは、公開鍵暗号を利用した認証システムと異なり、電子署名を作成しないで発信者認証を行っている。つまり、Kerberosはドキュメントの著者の認証をするために作られたのではなく、ネットワーク上のリソースにアクセスする際の本人認証のために使われるように設計されている。したがって、ネットワーク上でリアルタイムの認証処理はできるが、ネットワーク上にある書類などの第三者認証をオフラインで行うことはできない。
たとえば、Aさんがネットワークに接続されているワークステーションにログインする際には、通常ユーザIDとパスワードを入力する。Aさんがアカウントを持っている別のサーバーからファイルを取り出そうとするとき、普通ならまたAさんはユーザIDやパスワードを入力するなどの方法で、自分が本当にAである証明をする必要がある。しかし、Kerberosを利用しているネットワークでは、Aさんのワークステーションがそれを代行してくれる。
Kerberosシステムでは、ネットワーク上に鍵を集中して管理するKerberosサーバーと呼ばれる特定のサイトがある。このサーバーは、全てのユーザーの秘密鍵が入ったデータベースをもっており、ネットワーク上のユーザー間で安全な通信をしたい時、随時セッション・キーを発行したり、必要な時にユーザーの本人認証を行う。したがって、万が一、悪質なハッカーがこのサーバーに侵入した場合、ネットワークシステム全体が安全なものでなくなってしまう。
Kerberosは、これまでに5つのバージョンが開発されている。最初の3つはもう使われておらず、バージョン4とバージョン5の両方が利用されている。基本的には同じ機能をもっているが、バージョン4はTCP/IPネットワーク上でしか動かない。バージョン5は、95年5月に公開された最新版で、より機能が豊富になっている。
このKerberosは、大学だけでなく、金融機関などの企業や政府機関でも利用されており、非常に信頼性のある暗号システムであると信じられてきた。ところが、96年2月、パデュー大学の二人の学生が、バージョン4の暗号を解読することに成功した。バージョン4は、暗号鍵を作る際に用いる乱数が短く、容易に推測できるという欠陥を持っていたのだ。二人の学生は、乱数を推測し、それを用いて秘密のはずのセッション・キーを手に入れたのである。MITのネットワーク管理者であり、Kerberosの開発者の一人であるJeffrey Schillerは「セキュリティシステム、暗号プログラムといったものに、バグや弱点があってもおかしくない。最近の複雑なプログラムに人間の過失を加味すれば、どうなるかわかるだろう」と述べている。おまけに、MITの関係者は、バージョン4の乱数発生部分が弱点であることに、89年の時点で気付いていたというのだ。乱数発生のプログラムの欠陥から暗号が解読された事件は95年にも起きている。95年9月にカリフォルニア大学の学生が、ネットスケープ社の暗号を解読したのも、乱数発生のメカニズムが容易に推測できたからであった。
暗号アルゴリズムが十分に信頼できても、それをプログラムするときにミスを犯せば、その暗号システムは信頼できないものになる。この二つの事件から得られる教訓である。
IDEAとRC2、RC4
IDEA (International Data Encryption System)は、スイスのXuejia LaiとJames L. Masseyによって発明された暗号で、当初はIPES (Improved Proposed Encryption Standard) と呼ばれていた。この暗号化システムは一般に流通しているブロックアルゴリズムの中でもっとも安全性が高い暗号の一つであると考えられている。IDEAは64ビットのブロック暗号システム、つまりメッセージを64ビット単位で分割し、そのブロック毎に128ビット長の暗号鍵で暗号化して、64ビットの暗号化されたテキストを出力する暗号アルゴリズムである。暗号化のアルゴリズム自体はDESによく似ている。
IDEAは、ハードウェア・ソフトウェア上どちらでも簡単に適用できるようになっている。IDEAとDESの処理速度を比較すると、両方をソフトウェアで処理した場合、IDEAはDESより1.5から2倍程度処理速度が速い。また、IDEAの鍵の長さは128ビットで、DES（56ビット）と比べると2倍以上長い。もし、順次可能性のある鍵をテストする方法が、現実的な暗号解読法であると仮定した場合、この方法では平均して2の127乗回の暗号鍵をテストしないと鍵が解からないことになる。DESの場合には2の55乗回であるから、4.7×（10の21乗）だけDESより強力だということになる。これは恐ろしく強力な暗号だと言える。
IDEAは、さらに洗練された暗号解読方法（例えば、differential/related- key cryptanalysisなど）にも耐えられるようだが、これまで何度となく、絶対に安全と思われていたアルゴリズムが新しいタイプの解読方法で破られていることから、IDEAについても専門家は同様の可能性は否定できないと述べている。ただ、現在のところ、多くの大学研究機関や軍関係のグループがIDEAを分析しているが、いまだに誰にも欠陥は発見されていない。
IDEAはヨーロッパで特許が申請・認可され、米国で現在特許申請中である。この特許はAscom-Tech AG社 (Solothurn, Switzerland)が所有しており、商用目的以外の場合はライセンス料金が不必要となっている。
RC2とRC4は、RSA公開鍵暗号の開発者の一人であるRon Rivestによって設計された大量データを短時間で暗号化する可変長鍵暗号方式である。これらはDESに代わる暗号として、DESと処理速度が同程度か速くて、DESよりも長い鍵を使うことができる暗号として開発された。もちろん、DESと比べて短い鍵を使うこともできるが、この場合にはDESより安全性で劣ることになる。
RC2は、可変長の対称鍵暗号であり、輸出規制などでDESが使えない場合に代替用の暗号方式として使われることがある。RC2はソフトウェア上ではDESに比べて約2倍早い。RC4も、鍵の長さが自由になる対称鍵暗号であるが、RC2がブロック方式であるのに対して、RC4はストリーム方式の暗号化を採用している。RC4は、ソフトウェア上ではDESに比べて約10倍早い。両方ともプログラムのサイズは非常にコンパクトになっている。
RC2とRC4は、RSA社の所有するアルゴリズムで、その詳細については発表されていない。
PGP (Pretty Good Privacy)
PGP (Pretty Good Privacy)は、暗号アルゴリズムではなく、二つの暗号アルゴリズムを組み合わせた暗号ソフトウェアである。具体的には、IDEAをデータの暗号化に使い、RSA公開鍵暗号を使ってIDEAの鍵を暗号化して送信する方式を採用したソフトウェアの名前である。
PGPの発明者Philip Zimmermannは、この暗号ソフトウェアを開発した功績を評価され、インターネット関係の様々な賞を受賞している。このPGPはパーソナルコンピュータで利用できる非常に強力な暗号ソフトウェアであり、ほとんどすべての機種（パソコン及びワークステーション）で利用できる（PGPについては、1年前のレポートも参照されたい）。Zimmermannは、すべての個人がプライバシーを守れるようにと、このソフトウェアを無償で公開した。この無償で公開されたソフトウェアを、誰かがインターネット上のanonymous FTPサイトに置いたため、PGPは、またたく間に世界中のインターネット・ユーザに広まり、電子メールやコンピュータ上のデータの暗号化に利用されるようになってしまった。実は、現在もPGPは世界中のFTPサイトに置かれているが、いくつかのサイトにはこのソフトウェアが武器輸出の規制対象であることを警告するreadmeファイルが備えられておらず、ダウンロードする人に警告がなされないという問題がある。これは、最初にインターネット上にPGPをポストしたユーザがこの事（連邦政府によれば、このようなソフトに対して輸出規制を課している事を明記しなくてはいけないと定めている）を守らなかったためだと考えられる。この行為そのものは、（PGP暗号化ソフトは強力な暗号ソフトであるため、武器技術と見なされるので）米国の輸出規制法違反である。
実際、Zimmermannは93年9月以降、なんと28カ月間にわたって連邦政府によって取り調べを受けてきた。しかし、ついに96年1月、連邦政府は「インターネットを用いてPGPを不法に海外に持ち出した罪でZimmermannを起訴することはない」ことを明らかにした。しかし、Zimmermannの起訴が見送られたからといって、インターネットを通じて高度な暗号プログラムを自由にやりとりしてよいということにはならない。連邦政府が起訴を断念した理由は明らかにされていないが、多くの人々がZimmermannをサイバースペースの自由を守るために身を捧げたヒーローだと見ていることも理由の一つかもしれない。
ちなみに、PGPの商用バージョン（最新はVer.2.7）はViaCrypt社 (Phoenix, Az)から提供されているが、個人ユーザのための無料バージョンがあちこちのサイトに置かれている。注意が必要なのは、いくつかのバージョンが存在し、あるものは他のバージョンと互換性がないことである。MITから配布されているPGP2.6は94年9月1日以降に出力フォーマットを変更するように設計されているため、2.6で暗号化されたファイルの中身は、世界的に流通しているPGPのオリジナル・フリーウェアのバージョン2.3aで読めない。そこで2.3aを改良して2.6のファイルも読めるようにしたのが、非公式な国際バージョン(2.6ui)である。しかし、この2.6uiも新たに開発された国際バージョン (pgp262i) に置き換えられつつある。これもPGP2.6と互換性がある。ちなみに、これらのバージョンには「ITAR規則によりPGPのMITバージョンを国外でダウンロードすることが禁止されています」と言う責任を回避する文書（disclaimer）がソフトに添付されている。
暗号技術の輸出規制問題
1年前のレポートでも書いたように、連邦政府は暗号技術を利用した製品（ソフトウェア及びそれを組み込んだチップなどのハードウェア）の輸出を厳しく規制している。これは、こうした製品が武器等の輸出を規制するITAR (International Traffic in Arms Regulation) に定める軍需品に該当するためである（Code of Federal Regulations : Title 22, Chapter I, Subchapter M, Parts 121に記載されている）。
暗号技術製品の輸出を実際に管理しているのは国務省と商務省であるが、神経を尖らせているのは、NSA (National Security Agency) である。連邦政府は、暗号技術製品は、証明や認証(authentication)を目的としたものあるいは、輸出向けに作られた弱い暗号方式の製品のみに限って輸出を許可する方針を堅持している。具体的には、鍵の長さが原則40ビットを超える暗号製品の輸出はできない。暗号鍵の長さが40ビットの暗号であれば、最新のスーパーコンピュータを使えば、短時間で暗号を解読できるからだ。DESと比べれば、6万5000分の1の時間で十分だという計算になるからだ。これが64ビットになると、40ビットに比べて1600万倍の時間が必要になる。
95年8月に発表された輸出規制緩和策では、鍵の長さが64ビットまで拡大されたが、この場合は復号化のための鍵を第三者に寄託することが条件になっている。
ロータス・デベロップメント社のLotus Notesは、グループウェアの代表的な製品であり、この最新バージョンであるNote4.0は64ビットの暗号を用いているのだが、この新しい緩和策を利用して輸出許可をとりつけている。この事実は96年1月のRSA社主催の暗号関係の会議で明らかになり、関係者を驚かせた。というのは、64ビットの鍵全体を寄託するのではなく、64ビット中の40ビットを超える24ビット分のみを寄託するという条件で輸出許可を得ているからである（実際には、NotesはNSAが指定する24ビットを独自の40ビットに付加している）。ロータス社がどのような交渉をしたかは明らかではないが、これは確かに理にかなっている。元来、鍵の長さが40ビットの暗号は輸出できるのだから、24ビット分が入手できれば、条件は変わらない。
さて、連邦政府のこの輸出規制は、効果があるのだろうか。産業界によれば、この政府の方針の目的は、強力な暗号方式の輸出と拡散を制限することにあるが、実際にはあまり効果を上げていない。
例えば、SPA (Software Publishers Association) がTrust Information Systems社に依頼して行った調査によれば、海外で作成されている392種のソフトウェア製品になんらかの暗号方式が採用されていて、そのうち166 製品にはDESが組み込まれていることが判明した。そして、これら海外で作られたほとんどの製品は米国に輸入され、米国市場で販売されているのである。
つまり、そもそも米国の製造業者の暗号技術の使用を制限するために作られた規制政策が、世界市場を相手にした米国企業とその暗号技術を利用した製品の競争力を不利にしているばかりでなく、海外の製造業者に米国市場への進出を許してしまう結果を招いている。
商務省の調査とCSPPのレポート
連邦政府もこうした事実を知らないわけではない。96年1月17日には、商務省の貿易管理局とNSAが、暗号を含むコンピュータソフトウェア市場の現状と展望に関する調査レポートをまとめたことが明らかになった（この98ページの報告書は1月19日以降、無料で配布されている）。これは、94年末にクリントン大統領が商務省とNSAに調査を命じたものである。この報告書は、暗号技術を含む製品に対する厳しい輸出規制は、米国企業の海外市場への浸透を遅らせると同時に、こうした技術を用いた国際市場の拡大を阻害していると結論している
この調査では海外における米国企業の市場シェアや輸出規制の影響、外国企業の暗号技術を用いたソフトウェア製品の実態などを調べている。たとえば、スイス、デンマーク、英国の3カ国では、94年中に米国企業のシェアが低下したこと、7カ国では輸出規制の影響は問題になるほど大きくないが、14カ国では明らかに米国企業製品の販売拡大の足枷になっていること、米国企業のシェアは拡大する市場の中である水準を保ってはいるが、ほとんどの国で、輸出バージョンの米国製品はセキュリティ上満足できる水準にないと認識されていることなどが明らかにされている。
主要コンピュータ関係企業13社のCEOで構成されるグループ、CSPP (Computer Systems Policy Project) は96年1月17日、"Perspectives on Security in the Information Age"と題する23ページのレポートを発表した。このレポートは、以下の4点について暗号技術製品の輸出規制政策の変更を求めている。
(1) 世界市場における競合製品を考慮して、米国企業の商用暗号製品の輸出規制緩和を行うこと。
(2) 政府がはっきりと危険を示せない限り、より強力な暗号技術製品の基準をみたした商用エンドユーザへの輸出を、複合鍵の第三者寄託といった技術的制約なしに認めること。
(3) 合法的な理由で政府が暗号を解読できる仕組みを備えた、より強力な暗号の輸出について協議していくこと。
(4) テロリストの国には暗号技術製品の輸出を禁止すること
まず、(1) は、連邦政府が極めて弱い暗号しか輸出を認めていないにも関わらず、海外市場には十分強力な暗号製品が流通しているという事実を踏まえ、意味のない規制は止めようと提案しているものだと考えられる。つまり、海外で入手可能な暗号製品と同等の強さを持った暗号製品の輸出を無条件で認めるように提案している。
(2) は(1)以上に強力な暗号であっても、最終ユーザが信頼のできる企業や組織である場合には、輸出を許可するように求めている。これは、GIIの利用を考えると、医療データなどの個人情報のプライバシー保護や、極めて機密性の高いトレード・シークレットの保護のためには、現在海外市場で入手可能な暗号よりさらに強力な暗号が必要であるとの認識に基づいている。つまり、個人のプライバシーや企業の情報資産（"cyberproperty"と呼ばれている）を、組織的な窃盗、詐欺、改竄、あるいはスパイ活動から守る方が、（明らかな危険性が無い限り）暗号製品の輸出をコントロールすることより重要であるとCSPPは主張している。
(3)は、(2)に該当しない場合、より強力な暗号を用いた製品の輸出に関するCSPPの方針を示している。つまり、法に従って手続きがとられた場合には、政府が暗号を復号化できる仕組みを備えていれば、それが連邦政府の提案する鍵の第三者寄託方式でなくても、輸出できるようにしようという提案である。そして、その仕組みの開発は、鍵の第三者寄託方式を否定するものではないが、民間企業に任せてもらいたいと提案している。
最後の項目については説明は不要だろう。まさしくNSAはこれを一番恐れているのだから。
輸出規制緩和法案
こうした動きを受けて、議会には暗号技術製品の輸出規制緩和法案が提出されている。96年3月5日、Patrick J. Leahy上院議員（民、バーモント州）は"Encrypted Communications Privacy Act of 1996"と名付けられた法案を上院に、Bob Goodlatte下院議員（共、バージニア州）は"Security and Freedom through Encryption (SAFE) Act"という法案を下院に提出した。
この二つの法案のポイントは以下のとおりである。
(1) 米国民は自分自身の情報を守るために、暗号方式、鍵の長さ、暗号システムを自由に選ぶ権利を持っていることを確認すること
(2) 連邦政府が無制限に個人や企業の情報にアクセスすることを可能にする「鍵の第三者寄託」の強制を禁止すること
(3) 「鍵の第三者寄託」を選択した個人や企業の情報の安全を保障すること
(4) 犯罪の実効や犯罪の隠匿のために暗号技術を利用することを法的に禁止すること
(5) 海外の企業から入手可能な暗号技術製品と同程度（あるいは同程度以下）の暗号技術製品（ソフトウェアであるかハードウェアであるかを問わない）の輸出を認めること
Patty Murray上院議員（民、ワシントン州）やConrad Burns上院議員（共、モンタナ州）などもこの法案の支持を表明している。この法案提出と同時に法案提出議員などから発表されたプレスリリースには、既に紹介した商務省の調査結果やCSPPのレポートが引用されている。たとえば、Leahy上院議員のプレスリリースには「最近発表されたCSPPのレポートによれば、米国企業は世界市場において時代遅れの輸出規制というハンディキャップを負っているために、2000年には本来得られるべき300〜600億ドルの売上げと20万人の雇用機会を失うことになる」と書かれている。
輸出規制の行方
既に述べたように、暗号技術を用いた製品の輸出規制は、95年8月に発表された方針によって多少緩和されたものの、まだ連邦政府は基本的な姿勢を崩してはいない。産業界からは、規制を緩和あるいは廃止すべきだという意見が強く、96年3月には、さらに緩和を求める法案が議会に提出された。米国の暗号技術製品の輸出規制はどうなるのだろう。
ちなみに、国内における暗号技術の利用は、米国民及び米国の永住者である限り、まったく自由になっている。したがって、米国内での犯罪捜査に支障をきたさないようにするために、つまり合法的な盗聴が通信の暗号化によって妨げられないように、暗号技術製品の輸出規制をしているわけではない。もし、国内犯罪対策なら、国内における暗号の利用を規制しなければならない。
輸出規制は、あくまでも国外への高度な暗号技術の流出を防止しようという目的でなされていると考えなければならない。しかし、すでに見てきたとおり、米国外にも高度な暗号技術は存在しており、一部は米国に輸入すらされている。
もし、連邦政府（特にNSA）が言うように、ナショナル・セキュリティのために高度な暗号技術の利用を制限する必要があるなら、世界的なコンセンサスを得て、高度な暗号技術を持つ（あるいは持つ可能性がある）国々が協調して暗号技術の利用と輸出を規制しなければ意味をなさない。OECDなどの場で、米国が暗号技術問題を扱おうとしているのも、こうした背景がある。しかし、国際的な規制は、現実に可能なことなのであろうか。米国が危険視する国々において高度な暗号製品がつくられる可能性はあるし、暗号技術に関する情報の流通までは国際的に規制できないだろう。強力な暗号アルゴリズムであるRSA公開鍵暗号の（理論は多少複雑だが）仕組みは比較的シンプルで、プログラム化することは難しくない。とすれば、米国の産業界が言うように、連邦政府の輸出規制は、現実にはほとんど無意味で、単に米国の情報技術関連企業の輸出の足を引っ張っているにすぎない。
こうしたことを考えると、そう遠くなく連邦政府はこの輸出規制を大幅に緩和することになるだろう。暗号ソフトは単独で用いられるケースは希である。おそらく、電子メールやWWWのブラウザに組み込まれて使われることになる。とすれば、インターネット関連のソフト市場で圧倒的なシェアを持っている米国企業が、この暗号システムの世界でも市場を制覇することになるのだろうか。