【初級】暗号・認証技術を基礎から理解する　中編

鍵共有の問題を解決

2006.10.16

　70年代後半，DESの登場とほぼ時を同じくして，それとは異なる画期的な暗号の基本原理が登場した。2つの異なる数値データを暗号化と復号化の鍵として利用する「公開鍵暗号方式」である。この方式では，まず受信者が「公開鍵」を作成して公開鍵リストに登録する。送信者はリストの中の公開鍵を利用してデータを暗号化する。公開鍵暗号方式のポイントは，その公開鍵では復号化ができないという点だ。受信者が持っている秘密の鍵（秘密鍵）を使うことで，初めて暗号を復号化できるという仕組みである（図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暗号に乱数を取り入れて補強したもので，様々な標準暗号に用いられている。