PR

 70年代後半,DESの登場とほぼ時を同じくして,それとは異なる画期的な暗号の基本原理が登場した。2つの異なる数値データを暗号化と復号化の鍵として利用する「公開鍵暗号方式」である。この方式では,まず受信者が「公開鍵」を作成して公開鍵リストに登録する。送信者はリストの中の公開鍵を利用してデータを暗号化する。公開鍵暗号方式のポイントは,その公開鍵では復号化ができないという点だ。受信者が持っている秘密の鍵(秘密鍵)を使うことで,初めて暗号を復号化できるという仕組みである(図5)。

図5●公開鍵方式の基本的な仕組み
図5●公開鍵方式の基本的な仕組み
公開鍵方式では,受信者は複数の送信者との間で暗号をやり取りできる。
受信者は公開鍵と秘密鍵をペアで作成し,公開鍵だけを送信者に渡す。
暗号の復号化は,受信者が持つ秘密鍵でしか行えない

 DESを含む,それまでのあらゆる暗号方式は「データの送信者と受信者がいかにして秘密の鍵を共有するか」という課題を抱えていた。公開鍵暗号方式ならば,両者が秘密鍵を共有する必要はなく,受信者だけが持っていればよい。暗号の歴史の中でこれは画期的なことであった。

 この斬新なアイデアは,1976年に,スタンフォード大学の研究者ディフィ(Diffie)氏とヘルマン(Hellman)氏によって生み出された。そのアイデアを翌年に現実のものとしたのが,マサチューセッツ工科大学(MIT)にいた3人の研究者,リベスト(Rivest)氏,シャミア(Shamir)氏,エイドルマン(Adleman)氏であった。彼らが作り出した暗号は,3人の頭文字をとって「RSA暗号」と呼ばれ,現在も公開鍵暗号技術の基盤となっている。

素因数分解の難しさを利用

 公開鍵暗号は,「計算量的に困難な数学の問題(数論問題)」を安全性の根拠として利用している。「計算量的に困難」であることの厳密な説明はここでは行わないが,「計算量があまりにも膨大で,現実的には解くことが不可能である」ことと捉えてほしい。現在ではRSA暗号のほかにいくつかの公開鍵暗号が提案されているが,いずれも計算量的に困難な数論問題を利用している。

 RSA暗号が利用している数論問題は,素因数分解問題である注2)。これは,「大きな数の素因数分解は難しい」という原理に基づいている(囲み記事「RSA暗号の心臓部は逆算困難な関数」参照)。素因数分解問題は人類が最も長い間,チャレンジしてきた計算問題だ。長い研究の成果として楕円曲線を用いた方法や,「数体ふるい法」と呼ばれる素因数分解法が構築されているが,今後,しばらくの間はこれらを劇的に上回る効率的な分解法は簡単には発見されないだろうと考えられている。これらの方法のすべてを使っても天文学的な時間がかかるような大きさの鍵サイズにしておけば,かなり安心できるというわけである。

 RSA暗号では,素因数分解の対象となる数(合成数)として,2の1000乗かそれ以上の大きさの数を用いることが推奨されている。2の500乗程度の合成数は,7~8カ月の計算で素因数分解できた,つまり暗号の鍵が見つけられたという報告がある。

 しかし2の1000乗では,その約1600万倍の計算量が必要となる。よって単純に計算すると2の1000乗の合成数の素因数分解は,少なくとも約1千万年必要ということになり,事実上安全であると考えられる。

 ただし,いくら困難な数論問題を利用していても,「その数論問題が解けない限り絶対にその暗号が安全」とは言い切れない。実際のところ,従来の方式においては暗号の強さに思わぬ「抜け」が生じ解読され得るという欠陥がいくつも発見された。そのため90年代に入ると,数論問題を解くことと同等に解読が困難なことが証明された公開鍵暗号方式,いわゆる「安全性証明可能方式」が望まれることになった。

 安全性証明可能方式としては,RSA暗号をベースにした「RSA-OAEP暗号」が有名だ。RSA-OAEPは基本的なRSA暗号に乱数を取り入れて補強したもので,様々な標準暗号に用いられている。

デジタル署名でデータを保証

 電子データは複製や変更を行ってもその痕跡が残らない。それは扱いやすさという点でメリットになる反面,データおよびデータ作成者の正当性や,データの完全性を保証しようとする場合には大きな弊害となる。そこで活用されているのが,電子的な印鑑とも言える「デジタル署名」技術である注3)。

 デジタル署名の基本的な仕組みは次のとおり。まず元のデータ(平文)をハッシュ関数注4)を用いて圧縮し,それに対して署名生成関数を適用して署名を生成する。署名の生成時には秘密鍵を用い,署名の検証時には公開鍵を用いる(図6)。

図6●ハッシュ関数を用いたデジタル署名の仕組み
図6●ハッシュ関数を用いたデジタル署名の仕組み
メッセージからデジタル署名を生成する仕組みを示した。
メッセージをサイズの小さなハッシュ値に置き換えて,そのハッシュ値に対してデジタル署名を生成。
メッセージのハッシュ値とデジタル署名のハッシュ値を照合することで,メッセージの正当性を確認する

 前述したように,通常の公開鍵暗号方式では送信者が公開鍵を用い,受信者が秘密鍵を用いる。デジタル署名では,この関係が逆になる。

 公開鍵暗号は,通常,不特定多数(n人)の送信者と1人の受信者との間の通信で用いられる。その際,送信者が用いる公開鍵は秘密に保持されているのではなく,公開されている。そのため,本来はデータを送信する資格のない誰かが公開鍵のコピーを入手して,暗号文を送ってくる可能性があり得る。

 一方,デジタル署名では1人の送信者が秘密鍵を保持し,n人の受信者に公開鍵をコピーして配る暗号通信の関係を作る。このようにすると,n人の受信者の誰もが,1人しかいない送信者を認証できる。

 現在では図6ように単純にメッセージを暗号化して復号化するという形でデジタル署名を実現すること以外に,デジタル署名専用に設計された方式も多く提案されている注5)。

宝木 和夫(たからぎ かずお)/日立製作所システム開発研究所 主管研究長
1977年東京工業大学大学院修士課程修了。同年,日立製作所に入社し,以来,システム開発研究所で衛星放送暗号方式,楕円曲線暗号など情報セキュリティ技術の研究開発に従事。著書に「インターネットセキュリティ」,「ファイアウォール」(共著)など

三村 昌弘(みむら まさひろ)/日立製作所システム開発研究所 主任研究員
1997年東京工業大学大学院物理情報工学専攻博士課程修了。同年日立製作所に入社し,以来,システム開発研究所において指紋照合装置およびバイオメトリクス認証システムなどの研究開発に従事
次回に続く