最近話題の、公開鍵暗号とは・・・・

　公開鍵(public-key) という言葉は、広義には情報秘匿のほか、署名や認証などかなり広い技術を指します。以下では 公開鍵技術の狭義の意味(情報秘匿用途)を説明します。 公開鍵暗号(public-key cipher) は、公開鍵(=暗号鍵)が敵に知れても、第三者に文書の解読が出来ない技術です。 (参照→暗号)

　もちろん復号鍵(=私有鍵)は敵に知られては困りますが、共通鍵暗号(symmetric cipher) に比べて鍵の管理が簡単です。以下は、主な公開鍵暗号アルゴリズムです。

　公開鍵暗号は、大別すると巨大な数の素因数分解(prime factorization problem) がとても難しいことを安全性の根拠とする素因数分解型 と巨大な群の離散対数問題(descrete logarithm problem) が難しいことを安全性の根拠とする離散対数型 の２通りがあります。大雑把に言うと楕円暗号は離散対数型に含まれます。

　暗号化と複号化の概念図は以下のとおりです。

　BOB(受信者) は、私有鍵(private key)を生成し、次に対応する公開鍵(public-key)を計算します。 Bob は Alice(送信者) にその公開鍵(=暗号鍵)を教えます。私有鍵は、誰にも(Aliceにも) 教えません。Alice は公開鍵を使って文書を暗号化します。 Bob は 私有鍵を使って文書を複号します。 Bob さえ鍵を無くさなければ、Alice が故意に公開鍵を誰かに教えても秘密は守られます。

　(*)private key を秘密鍵と呼ぶ文献が多く見られます。秘密鍵という呼び方は多くの場合誤解を招きます。 公開鍵暗号系の復号鍵の他、共通鍵暗号系の鍵も秘密鍵と呼ぶことがあり、混同しやすいからです。 本稿では英語表記の直訳に近い私有鍵を採用します。

　一般的に、公開鍵暗号(public-key cipher) は共通鍵暗号(symmetric cipher) より低速でメモリも資源も余計に消費します。大は小を兼ねるの論法で言えば、機能的に共通鍵暗号に出来ることは公開鍵暗号ですべて出来ますから、本来ならば共通鍵暗号は要らないのですが、計算速度の差があまりにも大きいため、共通鍵暗号と併せて利用されます。

　現在、主流の公開鍵暗号は、大別すると素因数分解型と離散対数型 の２通りになります。大雑把に言うと楕円暗号は離散対数型に含まれます。ところが、最近はナップザック問題の困難さを根拠とした暗号なども見直され、改良を加えた暗号も注目を集めています。

　例えば、ラティス還元問題の困難性を根拠とする　NTRU などは（鍵が少し長いという欠点もあるようですが、）従来の公開鍵暗号の200倍の高速性と言われており、安全性検証の結果次第では新たな主流となる可能性も十分に在ります。

　1024 ビットの合成数を現実的な時間内に分解することは現在の技術ではほぼ不可能と考えられています。 また同程度の桁数に関する離散対数問題も同様に難しいと考えられています。

　しかしながら、最近話題に乗り始めた量子計算機を用いると、上記問題が多項式時間オーダーで計算が可能となるため、 最近は新しいパラダイムを用いた公開鍵暗号も真剣に考えられ始めているようです。