next up previous contents
Next: 7.1.3 認証システム Up: 7.1.2 暗号 Previous: 7.1.2.2 対称暗号方式

7.1.2.3 非対称暗号方式

非対称暗号方式は別名 公開暗号鍵方式と呼ばれています。 この方式では、暗号鍵と復号鍵が異なっています。

非対称暗号方式 $K \ne K^{-1}$

このために、暗号鍵を知られても、復号鍵が分からない限り暗号は解けません。また、 最初に述べたように、復号鍵を使って暗号化したメッセージは逆に暗号鍵でないと 解けないという構造になっています。この性質がネットワーク上でこの暗号システムを 利用するのに非常に適している原因です。

一般には、暗号鍵、復号鍵という言葉を使うと混乱するので、2つのペアの鍵の内 片方を 公開鍵 と呼び、他方を 秘密鍵と呼びます。 そして、公開鍵を誰もが読めるように公開しておき、2者の間で秘密の通信をしたい 場合には以下のようにします。

\epsfile{file=auth-pubkey}

まず、送信者 A は、Bの公開鍵BKを使ってメッセージ文を暗号化します。すると、 この暗号化文はBの秘密鍵BPでしか解読出来ないものですので、この暗号化文は 誰に見られても構いません。同じようにBがA にメッセージを送る場合には、逆にAの公開鍵AKを取得し、それを使ってメッセージを 暗号化して送れば良いわけです。

また、公開鍵方式で2つの鍵は対称な関係にあることを利用して、逆方向に利用する ことで電子認証などに利用することも可能です。

公開鍵暗号方式の代表は RSAです。RSAは開発者の名前を取って名付けられたものです( Ronald Rivest, Adi Shamir, Len Adleman)。 RSAは非常に大きな数を素因数分解するのが大変であるという事実に基づいています。 実際、Rivestはこのために少しばかり小さな(それでも実は途方もない数ですが) $2^{429}$ を使ったRSA暗号の解読の懸賞を公開しましたが、この暗号は17年間 解読出来ませんでした。そして、1993年に1600台ほどのコンピュータと8ヶ月の時間を 費やして、ようやく解読出来たのです。しかし、現在RSAの鍵に使っている数字は 大体 $2^{1024}$ 程度を用いていますので、大体$10^15$倍強力だと言われています。 勿論、素因数分解のうまい方法が見つかれば、この限りではありませんが、多くの数学者 が長年かかっても、今のところ良い方法は見つかっていませんので、当面は安心して 良いでしょう。

なお、RSAは非常に強力ですが、そのために計算コストも大きく全てをRSAで行うのは 大変であると言われています。このために、多くの場合最初のやり取りのみ公開鍵 方式を使い、そこで秘密鍵を交換して、その後は秘密鍵を使うのが一般的です。 その意味で、秘密鍵方式も重要なので、先のAESにも意味はあるのです。 (ちなみに、VPNなどではDESあるいはDESを3回用いる 3DESなどが使われますが、 全てのパケットにこうした暗号を用いるのはDESであっても、かなりの計算コストが 伴います。つまり、VPNでは結構この計算に時間がかかるために、スピードが出ない 傾向にあります。)

非対称暗号方式では、RSAの他に Diffie-Hellman交換(DH)アルゴリズムがあります。 DHでは、安全でない通信路で通信しようとしている2者が、乱数を生成し、その 乱数から導かれるある値を交換することで、秘密裏にある値を共有することを可能 にします。その概略は、A が作成した乱数を$A_R$ とし、Bが作成した乱数を $B_R$ とします。それぞれの乱数は当然秘密にしておき、通信路上には、それらの 乱数をある値で割った余りを流します。これをそれぞれ $Q(A_R)$,$Q(B_R)$とすると、 Aは $A_R$$Q(B_R)$ を持ち、Bは$B_R$$Q(A_R)$をそれぞれ持つことになります。 A,Bは、この情報からある計算をすることで、共通のある値$C$を得ます(これは 数学的に保障されています)。ところが、これを盗聴していた第三者からは、 $Q(A_R)$$Q(B_R)$ しか見えないので、この2つの値から $C$ を得ようとすると、 素因数分解問題に負けず劣らず難しいとされている離散対数を計算する問題になり、 これも簡単に解く方法は見つかっていませんので、事実上 $C$ を得ることが出来ない のです。

DHは、IPsecが利用している自動鍵交換システム(IKE:Internet Key Exchange)で 利用されています。



Noriyo Kanayama