PGP Technical research Return to Parent Menu　
Last Updated by 04/14/98(Tue) 　
　
− Contents −
　

　
− 公開鍵暗号 −
　

　公開鍵暗号 (Public key cryptography) は、今までの暗号技術（慣用暗号）とは異なり、暗号化と復号化に対になる 2 つ（公開鍵、秘密鍵）の鍵を用いる方法であることは、 PGP History と How to use PGP を読まれた方には理解して頂けたと思います。

　ここでは、その公開鍵暗号を実現する数学的な技術情報を紹介します。プログラム的な技術については、ソースファイルが公開されていますので、そちらの方をご覧の上、がんばって理解してみてください・・・？
▲ TOP　

　
− RSA 公開鍵暗号 −
　

　公開鍵暗号を実現するアルゴリズムはいくつか考えられますが、ここでは RSA のアルゴリズムを取り上げたいと思います。
　今回述べる RSA の公開鍵暗号アルゴリズムは、現在の RSA Data Security Inc. の創立者 Headquarters M.I.T. Laboratory for Computer Science. 教授 の R. L. Rivest と A. Shamir, L. Adleman の 3 人によって書かれた「 A Method for Obtaining Digital Signatures and Public-Key Cryptosystems 」によるものです。

　 PGP の技術情報に RSA の公開鍵暗号アルゴリズムを紹介するのはおかしいと感じられるかもしれませんが、それで良いのです。 Philip R. Zimmermann が作成した PGP には RSA の RSAREF(tm) という暗号化のプログラム・ルーチンが使われているからです。

　米国内で RSA を使用する場合には、この暗号化ルーチンを使用しなければなりません。（Ståle Schumacher 氏らの開発チームにより作成された国際版の PGPi には RSAREF(tm) は使用されず、 Philip R. Zimmermann による MPILIB が使われています。）

　まず、 RSA アルゴリズムを紹介する前に、 RSA 公開鍵暗号を実現する上での特徴（絶対条件）を理解しておく必要があります。

　　　 01. 暗号化、及び復号化が容易な計算で導き出せること
　　　 02. 暗号文が破られないこと
　　　 03. 暗号化の鍵から復号化の鍵が生成できないこと
　　　 04. 暗号化と復号化ができること

　この条件が全て満たされているという条件下でのみ、公開鍵暗号は現在最高級の暗号技術であることが証明されます。
▲ TOP　

　
− RSA 暗号化アルゴリズム −
　

　実際に数学式を交えながら RSA のアルゴリズムを紹介して行くわけですが、これに関しては『C MAGAZINE '97.2　暗号化プログラムＰＧＰ　SOFTBANK』に非常にわかりやすい説明がありましたので、補足しながら説明していきます。

　はじめに、任意の非常に大きな 2 つの素数を選びます。
　 2 つの素数を P, Q とし、その積を N とします。

N = PQ ..... ( a )

　次に、関数Ф(N) を定義します。この Ф(N) は『オイラーの定理』から導いた関数で、オイラー関数と呼ばれています。

Ф(N) = ( P - 1 )( Q - 1 ) ..... ( b )

　そして、 Ф(N) と互いに素となる数 E を選びます。さらに次式となるような D を選びます。

ED = 1 ( mod Ф(N) ) ..... ( c )

　上式の D は "mod Ф(N)" （モジュロ＝オイラー関数の剰余）を取ったうえでの E の逆元となる値をとります。

D = ( 1 ( mod Ф(N) ) ) / E ..... ( d )

　ここまでは、計算に使うものの下準備で、上記のものを使って暗号化、復号化を行うわけです。

　 1 つの数 M (Message) を暗号化する例を以下に示します。暗号化には次の数式を使用します。
　 M を暗号化して得られる数を C (Ciphertext) とすると、 C は次の式で導くことができます。

C = ME ( mod N ) ..... ( e )

　上の式では、 M を E 回掛けた後 N で割ったときの剰余が暗号文そのものということになります。
　この暗号文を復号化しようとするときには、この計算の逆を行います。

　復号化には E の逆元 D を使用して C から M を導きます。

M = CD ( mod N ) ..... ( f )

　 RSA の暗号化の心臓部は上記の動作をしています。

　この RSA アルゴリズムで最も重要なのは、上記の ( e ) 式です。

　この式での演算が、文書 M から暗号化の鍵 E を使って、暗号文である C を算出します。
　このとき、 N が非常に大きな数であれば M と E から C を生成するのは容易な作業となりますが、 C と E から M を生成するのは非常に難解であることが数学的に証明されています。

　 C と E から M を得るのは、 mod N のうえでの対数（離散対数）を求めなければなりませんので、非常に困難な計算となります。この離散対数の困難さを利用していることが RSA アルゴリズムの特徴となっています。
▲ TOP　

　
− メッセージダイジェスト −
　

　メッセージダイジェスト (message digest) とは、個々のメッセージから固有の値を算出させる方法をいいます。非常に複雑な「チェックサム」であるともいえます。

　有効なメッセージダイジェスト関数は、コリジョンプルーフ性と呼ばれる特性を持ち、異なるメッセージには異なったメッセージダイジェスト値を生成させるという動作を行います。

　その有効なメッセージダイジェスト関数に PGP で使われている MD5 と呼ばれるものがあります。
　この MD5 は、任意のバイト列に対して 16 Bytes のダイジェスト値を発生させます。

　 MD5 は非常に複雑なビット演算を行い、テキスト文書内の 1 bit でも修正／改竄が行われると、修正前後で全く異なるダイジェスト値を生成します。

　 PGP では「電子署名 (digital signature) 」や「鍵の指紋 (key fingerprint) 」でこの MD5 が使用されます。

　国際版 PGP のパッケージには MD5 の演算を行える md5sum.exe が含まれます。コマンドラインから md5sum.exe に続き、ファイル名を指定することで、そのファイル固有のダイジェスト値を表示させることができます。
▲ TOP　

e-mail: mist@e-net.or.jp
Structured Anchor Tree　Return to Menu　Return to Parent Menu　
Powered by Unit Missing Link.