私自身は暗号理論の専門家ではありません。なるべく嘘は書かないようにしたつもりですが、間違いがあれば御指摘下さると嬉しいです。
暗号とは第三者に知られることなく情報を伝達するものです。古典的な例としてはシーザー (Caesar) 暗号と呼ばれるものがあります。 文章において、アルファベットを3文字ずつずらして暗号化する方法です。
A B C D E ... W X Y Z | | | | | ... | | | | ↓ D E F G H ... Z A B C
例えば ANGOU なら DQJRX になります。
復号化するには逆に3文字ずらします。
ずらす文字数を変化させれば暗号文はいろいろ変化します。この場合、「何文字かずらす」という手順はアルゴリズム、「ずらす文字数」は鍵と言っていいでしょう。
さて、かつては軍事目的に使われることの多かった暗号も、インターネットに代表される通信網の発達によって、個人のプライバシー保護や、商取引などの目的に使われることが多くなりました。
このような目的の場合、暗号のアルゴリズムを秘匿しておくことにはいろいろ問題があります。アルゴリズムがばれてしまった場合に強度を保てませんし、暗号ソフトの開発元には情報を秘匿できなくなります。むしろ利便性のためにはアルゴリズムは公開されるべきものです。特に広く利用するために標準暗号を定めようとするなら、公開は必須でしょう。また、暗号の安全度をアルゴリズムの秘匿に頼ったりすると、思わぬしっぺ返しをくらったりもするかもしれません。
このように現代では鍵のみを秘匿し、なおかつ十分な強度を持つような暗号が必要となります。
対称鍵暗号 (共通鍵暗号, 秘密鍵暗号)とは、暗号化と復号化に使う鍵が共通の暗号のことです。 次に説明する公開鍵暗号が発明されるまでは、暗号と言えば、この対称鍵暗号のことでした。例えば、前節で紹介した Ceasar 暗号では、暗号化する鍵と復号化する鍵は3で共通だと言えます。
このような暗号で A が B に暗号メールを送ろうとする場合、A は B と共有する鍵を作成し、前もって他人に見られることのない経路を使って B に送っておく必要があります。(あるいは逆に B が鍵を作成して A に送っておいてもよい。) そして A はその鍵でメールを暗号化して B に送ることになります。
![[説明図]](symkey1.jpg)
現在のアルゴリズム公開型の暗号では、米国政府の標準である DES (Data Encryption Standard) が有名ですが、これは 1976 年に採用が決定された規格で、松井充氏の線形解読法などの攻撃方法や、計算機の性能などが進歩した現在、既に安全ではなくなっています。 今のところ安全と思われる共通鍵暗号としては、例えば、PGP-2 で使われている IDEA や、DES を3重にかける Triple DES、日本製では例えば MISTY などが挙げられます。 というか本当はもっといろいろあるはずですが、この辺は最近の事情を追ってないですし、時間と共に事情は変化しますので、詳しく知りたい方は御自分でお調べ下さい。 なお Triple DES は現在の計算機でも多少重かったりするので、米国の NIST (U.S. National Institute of Standards and Technology; 米国国務省標準技術局) では DES の後継として、より安全でかつもっと効率の良い暗号を AES (Advanced Encryption Standard) として、米国政府標準の対称鍵暗号に採用しようとしているところです。 2000/03/15 現在、最終候補が5つに絞られ、秋には決定されるようです。 [1]
対称鍵暗号を使って暗号文をやりとりしようとすると、鍵の配送が問題になります。n 人の人がお互いに他人に知られずに暗号をやりとりしようとすると、鍵の数は nC2 = n(n-1)/2個も必要になります。元が1000人でも、鍵は499500個です。その全てを他人に知られることなく相手に送らなければなりませんし、鍵の使い分けも面倒です。これは管理運用や安全性の面で大きなネックになります。
信頼できる第三機関を置いてそこに鍵を預けるなど、工夫の余地はありますが、いろいろな問題が残ります。
公開鍵暗号 (非対称暗号)とは、暗号化と復号化で異なる鍵を使う暗号のことです。 もう少し正確に言うと、暗号化する鍵から復号化する鍵を計算するのが極めて困難で、現実問題としてはまず不可能であるということです。公開鍵暗号では各人が二つの鍵のペアを用意して、そのうち一つは隠し、もう一つは公開します。前者は秘密鍵、後者は公開鍵と呼ばれます。 (従って公開鍵暗号と言っても全ての鍵を公開するわけではありません。)
公開鍵暗号を用いて A が B に暗号メールを送ろうとする場合、A は B の公開鍵を使って暗号化します。この暗号を複号するには B の秘密鍵が必要なので、B のみがこの暗号文を解読できるというわけです。
![[説明図]](pubkey1.jpg)
公開鍵暗号は、共通鍵暗号の持つ鍵配送にまつわる問題を完璧に解決してくれます。鍵は各人が一組ずつ持てばよいですし、相手に渡すのは公開鍵の方なので、配送のときに鍵が第三者に知られるのを気にする必要はありません。
また、公開鍵暗号を利用すれば、電子署名といって、電子的な情報の内容が改竄されていないことや、その情報が特定の人からのものであることを保証することもできるようになります。これについては電子署名の節でもう少し詳しく説明します。
1976 年に、Diffie と Hellman によって、暗号史上もっとも革新的とも言える公開鍵暗号のアイディアが提案されてから、それを実現するアルゴリズムがいろいろ提案されてきました。 Diffie-Hellman 自身は公開鍵のアイディアと共に、離散対数問題を利用した鍵配送アルゴリズムを提出していますし、翌年の 1977 年には MIT の Rivest, Shamir, Adleman によって素因数分解の困難性を利用した RSA 暗号が、また、1982 年には ElGamal によって離散対数問題を利用した ElGamal 暗号が発表されています。 (これは Diffie-Hellman の鍵配送の一種の変形とも言える。) その後、楕円曲線における離散対数問題を利用した、楕円 Diffie-Hellman 鍵配送や楕円 ElGamal 暗号、また、楕円曲線版の RSA 暗号なども提案されています。
楕円暗号は、単純に乗法群の離散対数問題 (or RSA) を楕円曲線の離散対数問題 (or RSA) に置き変えたというだけではなく、ある程度の根拠もあります。
この他にも様々なアルゴリズムが提案されてきたのですが、そのほとんどが安全性に問題があることが指摘され、消えていきました。[2]
実際には、素因数分解の困難性も離散対数問題の困難性も、現在知られているアルゴリズムでは困難という意味で、これらの安全性が証明されているというわけではありません。 が、この二つの問題は数論の長い歴史を背負っています。そういうこともあって、RSA 暗号や ElGamal 暗号が使われることが多いようです。 ただし、これらの問題に関する革新的なアルゴリズムが見つかった場合に備えて、新しい暗号アルゴリズムを見つける努力は必要ですし、 また現在よりも効率が良く、強度の高いアルゴリズムを開発することも大切です。
上に挙げた楕円曲線を使った暗号は既に実用段階にありますが、その次の世代の暗号として、より種数の高い曲線のヤコビアンを使った暗号などについても様々な研究がなされています。
公開鍵暗号が全ての点で対称鍵暗号よりも優れているというわけではありません。現時点では、
ということが言えます。そこで PGP や GnuPG では次節で説明するハイブリッド暗号が使われています。
対称鍵暗号と公開鍵暗号を組み合わせて使うものです。ハイブリッド暗号は、強度的にはそれが用いている公開鍵暗号や対称鍵暗号そのものより強いわけではありません。 が、対称鍵暗号における鍵配送の問題と、公開鍵暗号における速度的な低下を同時に克服しているという点ではやはりハイブリッドと言えます。 PGP や GnuPG などでは、暗号を送る際の対称鍵暗号に使うセッション鍵を公開鍵暗号で暗号化する方法を取っています。
なお、セッション鍵はその都度ランダムな数字を使って生成されるので、仮にセッション鍵が解読されても、その時に送られたメッセージが解読されるだけで、他の暗号文の解読はまた一からやらなければいけません。
ハッシュ関数 (hash function) の定義は本によって違ってますが、値域が有限集合の関数、特に定義域より値域がずっと小さな関数をさすことが多いようです。簡単な例としては、整数に対して、それをある数 q で割った剰余を対応させる関数
h: Z -> Z/qZ; n -> n mod q (Z は整数環)
などがあります。
ハッシュ関数を使う目的にはメモリやデータベースの効率的な検索などがありますが、暗号への応用では、一方向ハッシュ関数 (one-way hash function) が使われます。 一方向性として、
h(x)=h(y) となる異なる x、y を見つけるのが困難。
という性質を持つものは衝突困難ハッシュ関数 (collision intractable hash function, strongly collision free hash function) と呼ばれます。また、この条件を少し緩めた
x と h(x) が与えられたときに、h(x)=h(y) となる x と異なる y を見つけるのが困難。
なハッシュ関数は汎用一方向関数 (universal one-way hash function, weakly collision free hash function) と呼ばれます。
上の例で挙げた剰余を対応させる関数では、勝手な r mod q に対して n mod q = r mod q となるような n はいくらでも簡単に見つけられるので、全く駄目ですね。
さて、このような一方向性を持つハッシュ関数を使えば、例えばファイルのハッシュ値によって、ファイルが改竄されていないか手軽にチェックできることがお分かりでしょう。 ただし、ハッシュ値も含めて改竄される危険はまだ残ります。これを防ぐには、もう少し複雑な仕組がいります。これは次の電子署名の項で説明します。電子署名で使うには、汎用一方向関数で十分といえます。
例えば素因数分解が困難という仮定の下で衝突困難ハッシュ関数を構成できることが知られています。[3] が、それは速度の面から考えて実用的といえるものではありません。そこで、いろいろなハッシュ関数が提案されています。 有名なところでは MD5 などがそうです。PGP-5 や GnuPG では基本的には SHA-1 (secure hash algorithm) が用いられてます。
紙などの媒体と違い、電子的な文書では偽造や改竄が簡単に行えます。また、改竄された文書を見てもその物理的な証拠はそのデジタルデータ自体には何も残っていません。
従って、ある電子的な文書が確かに特定の人が作成したものであることや、途中で改竄されていないことを確認できるようにするには、そのための仕組が必要になります。それが電子署名と呼ばれるものです。
公開鍵暗号を用いれば、電子署名 (Digital signature) が行えます。 安直にはメッセージを秘密鍵を用いて暗号化して送るという方法が考えられます。 受信者は公開鍵を用いてそのメッセージを解読できるか見ることで、本当にその人が送ったメッセージか認識できます。 この用途に用いる公開鍵暗号は、公開鍵と秘密鍵の両方を公開鍵として用いることが可能という性質が必要ですが、RSA はこの性質を持ってます。 それが RSA 署名と呼ばれる方式です。実際には次に述べるようにハッシュ関数と組み合わせます。 (そうしないと文書によっては偽造が不可とは言えなくなる。)
一方、ElGamal 暗号では、公開鍵と秘密鍵の役割は対称ではないので、単純に上の方法は使えません。 が、少々変形すれば、署名にも使えます。それが ElGamal 署名と呼ばれるものです。 [4]
ただし、上に挙げた方法では本文の長さが長いと計算に時間がかかって非効率ですし、鍵の長さも長くなります。 そこで ハッシュ関数の出番です。
例えばドキュメントのハッシュ値を署名とし、それを公開鍵暗号の秘密鍵で暗号化したものを添付したとします。 受信側は公開鍵で署名を解読して、ドキュメントのハッシュ値と比較することで改竄されていないことを確認できます。 また、その公開鍵で解読できるハッシュ値を作れるのは対応する秘密鍵を持つ人だけなので、第三者が別の文章をその人の名で署名することはできません。ハッシュ値を改竄することも不可能というわけです。
ElGamal 署名の場合、単純にハッシュ関数を用いても署名の長さは選んだ素数の2倍の長さになります。 (これは同程度の強度の RSA 署名の長さの2倍、現在安全と考えられるレベルでは 2048 bit)。ICカードなどの単純な媒体で認証を行う場合には署名の長さは結構問題になります。 そこでもう少し工夫して署名長を短くしたものが DSA (Digital Signature Algorithm) と呼ばれる方法です。これだと署名の長さは(鍵の選び方にもよりますが、現在安全と考えられるレベルでは) 320 bit くらいに抑えられます。またその分、計算の負担も少なくてすみます。
アメリカ連邦政府での標準を定める DSS (The Digital Signature Standard) では、以前は DSA しか採用していなかったのですが、最近 (1999) RSA 署名も含まれるようになったようです。ただ、特許の問題から GnuPG では DSA が使われています。 もっとも、DSA についても、以前は特許も含めていろいろ論争があったみたいですが。
その他には ESIGN 署名と呼ばれるものもあります。これは RSA と同じく素因数分解の困難性に基づくものですが、署名生成速度が早く、IC カードなどでも使えるものです。
[1] ここに名前の挙がっている暗号を見れば、最近の事情とかが分かるかもしれません。検索エンジンで「暗号」と「AES」をキーワードにして検索すれば、いろいろ引っかかります。NTT の E2 も良い暗号だと思うのだけど、NIST の評価方法のミスなどもあって残れなかったようですね。ただ、AES 関連の記事を見ると目茶厳しい世界らしく、ここである程度評価されたということは、それだけで十分安全かつ効率的と言ってよいのではないかと思われます。
[2] RSA や、ElGamal にも問題点がないわけではないです。例えば、RSA にしても素数の組の選び方によっては簡単に因数分解ができてしまったりするわけなので、実際にプログラムを作る場合にはそういった点を考慮する必要があります。
[3] 何の仮定もなしに一方向性関数が作れるなら NP 問題も解けるはずなので、今のところはある種の仮定は避けられないでしょう。
[4] 従って ElGamal 暗号と、ElGamal 署名とは、共に離散対数問題に立脚しているし、実際似てはいるものの、一応アルゴリズムとしては別物です。 対して RSA 暗号と RSA 署名のアルゴリズムは一緒です。