今回は公開鍵暗号方式について、少し深く見ていきます。
暗号まわりのお勉強1でも若干触れましたが、どのような方式かを先におさらいします。
公開鍵暗号方式の概要
暗号化に使う鍵と復号に使う鍵が異なる暗号方式です。非対称暗号とも言います。
大まかな手順
- 受信者は、鍵ペア（秘密鍵と公開鍵のペア）を作成する。
- 受信者は、公開鍵を送信者に配布する。
- 送信者は、平文を取得した公開鍵で暗号化し、受信者へ暗号文を送信する。
- 受信者は、受け取った暗号文を秘密鍵で復号する。
メリットとデメリット
| メリット | 鍵配送問題を解決できる。 通信相手の数に関わらず、管理する鍵が1つでよい。 |
| デメリット | 共通鍵暗号方式に比べて処理速度が遅くなりがち。 |
スポンサードサーチ
公開鍵暗号方式の詳細
では、公開鍵暗号方式について、もう少し踏み込んで見ていきましょう。
構造
公開鍵暗号方式は、大きく以下の3つのアルゴリズムに分かれます。
- 鍵生成アルゴリズム（Key Generation Algorithm）
⇒鍵ペア（公開鍵と秘密鍵のペア）を作成するアルゴリズム - 暗号化アルゴリズム（Encryption Algorithm）
⇒平文を公開鍵によって暗号化するアルゴリズム - 復号アルゴリズム（Decryption Algorithm）
⇒暗号文を秘密鍵によって復号するアルゴリズム
それぞれについて見るにあたり、以下のパラメータを定義します。
- セキュリティパラメータ・・・・k
- 乱数・・・・・・・・・・・・・r
- 鍵生成アルゴリズム・・・・・・G
- 暗号化アルゴリズム・・・・・・E
- 復号アルゴリズム・・・・・・・D
- 公開鍵・・・・・・・・・・・・P
- 秘密鍵・・・・・・・・・・・・S
- 平文・・・・・・・・・・・・・M
- 暗号文・・・・・・・・・・・・C
鍵生成アルゴリズムにセキュリティパラメータと乱数を入れることで、公開鍵と秘密鍵の鍵ペアを生成します。メッセージを将来的に受信したい側がこの操作を行います。この操作で生成された鍵ペアのうち公開鍵は公開します。秘密鍵は公開しません。
G(k, r) = (P, S)
暗号化の際は、暗号化アルゴリズムに平文と公開鍵を通すことで、暗号文を作成します。平文の送信者は、予め公開鍵を取得しておく必要があります。
E(M, P) = C
復号の際は、復号アルゴリズムに暗号文と秘密鍵を通すことで、平文に戻します。
D(C, S) = M
公開鍵暗号方式に分類される暗号化手法は様々なものがありますが、それぞれの手法でG、E、Dは異なっています。
安全性の根拠
公開鍵方式の安全性は、次の2つのうちいずれかの計算困難性（計算量の非対称性）に基づいています。
素因数分解の困難性
CRYPTRECでは、素因数分解問題について次のように表現しています。
素因数分解問題とは, 合成数Nが与えられた時, その非自明な約数 d (d | N, 1 < d < N) を求める問題である. （一般的には, Nを素数の冪積で表示することを言うが, 非自明な約数が存在すればそれを求める問題に効率よく帰着されること, さらに, ２つの素数の積の合成数の場合を考える事が多いため, こう定義される事が多い.）
暗号理論の文脈で解釈すると、N = pqにおいて、「pとqからNを求めることは少ない計算量で可能」であるが、「Nからpとqを求めることは膨大な計算量が必要」であるという性質があり、これを利用するものです。Nの桁数が大きくなるほど素因数分解は困難になります。
なお、Nは必ずしも2つの整数の積ではなく3つでも4つでも構いませんが、暗号理論の文脈では2者間の通信を想定するため、暗黙的に「2つの素数の積」としてモデル化されることが多いようです。
ちなみに、大きな桁数の素因数分解が困難なのであって、素因数分解した値の素数判定は難しくはありません。実用的には、APR法やECPP法による素数判定が多く用いられています（一応、多項式時間で判定できるAKS法もありますが、一般的に時間がかかるとされているため、こちらは現代会では実用的ではありません）。
離散対数問題を解くことの困難性
CRYPTRECでは、（有限体上の）離散対数問題について次のように表現しています。
有限体上の離散対数問題とは, 有限体の乗法群F×q の二つの要素 t, u が与えられた時, u = tx なる整数 x が存在すれば, それを求める問題である. ここで,整数 x は t の位数を法として一意に定まり, logtu などと表され, t を底とした u の離散対数と呼ばれる. 有限素体上の場合に, 従来は指数と呼ばれていたものである.
暗号理論の文脈で解釈すると、u ≡ tx (mod p)において定数tと素数pが判明しているとき、「xからuを求めることは少ない計算量で可能」であるが「uからxを求めるには膨大な計算量が必要」という性質があり、これを利用するものです。素数pの値が大きいほど離散対数問題を解くことは困難になります。
u ≡ tx (mod p)は、「pを法としてuとtxは合同である」と言い、かいつまんで言うと「uとtxをそれぞれpで割った余りが等しい」ことを指します。
（注）よくある勘違い
- 公開鍵暗号方式では、公開鍵で暗号化した暗号文を秘密鍵で復号できるのと同様に、秘密鍵で暗号化した暗号文を公開鍵で復号することができる。これを利用して、電子署名が可能となる。
公開鍵で復号できるということは、一人しか知らない秘密鍵が使用されているということであり、確かにその人のものであるということを証明できる（＝電子署名）という理論です。
RSA暗号方式に関しては「公開鍵で暗号化した暗号文を秘密鍵で復号できる」という性質と「秘密鍵で暗号化した暗号文を公開鍵で復号できる」という性質が仕組み上成り立ちますが、他の公開鍵暗号方式全てに当てはまる性質ではありません。
従って、あたかも鍵ペアで相互に暗号化と復号ができる、その性質を利用して電子署名の仕組みが確立されているという記述は正しくありません。
公開鍵暗号のアルゴリズム
公開鍵暗号のアルゴリズムには、楕円曲線暗号、RSA暗号、ElGamal暗号などがあります。