更新:2025/02/05

数学的な視点で見た公開鍵暗号方式について

はるか
はるか
公開鍵暗号方式、秘密鍵と公開鍵の2つを使う。
ふゅか
ふゅか
そうそう!送る側は公開鍵で暗号化、受け取る側は秘密鍵で復号するの!

1. 公開鍵暗号方式とは?

公開鍵暗号方式とは、通信の安全性を確保するための暗号技術の一つであり、インターネット上でのデータのやり取りに広く利用されています。この方式では、受信者の「公開鍵」と「秘密鍵」の2つの鍵を使用してデータの暗号化と復号を行います。

2. 公開鍵暗号方式で必要な関数

公開鍵暗号方式は、大きく分けて以下の3つの写像(関数)によって構成されると考えることができます。

  1. 鍵生成関数 KeyGen
    秘密鍵 $SK$ と公開鍵 $PK$ のペアを生成する写像です。
    $$ (PK, SK) = KeyGen(1^n) $$
    ここで $1^n$ は鍵の長さなどを表します。
  2. 暗号化関数 Enc(PK, m)
    公開鍵 $PK$ を引数として受け取り、平文(メッセージ) $m$ を暗号文 $c$ に変換する写像です。
    $$ c = Enc(PK, m) $$
  3. 復号関数 Dec(SK, c)
    秘密鍵 $SK$ を引数として受け取り、暗号文 $c$ から平文 $m$ を取り出す写像です。
    $$ m = Dec(SK, c) $$

はるか
はるか
Enc関数。公開鍵を使ってメッセージを暗号文に変換する。

ふゅか
ふゅか
そして復号するのがDec関数ね!秘密鍵を使って元のメッセージに戻すんだ!

3. $\mathcal{M}$ と $\mathcal{C}$ について

公開鍵暗号方式においては、暗号化対象のメッセージ(平文)を表す集合を$\mathcal{M}$(メッセージ空間)
暗号化によって得られる暗号文を表す集合を$\mathcal{C}$(暗号文空間)として、それぞれ有限集合であると考えます。

4. 公開鍵暗号方式を「写像」で表すとどうなるか

公開鍵暗号方式を写像(関数)の組で表すと、以下のようになります。

  1. 鍵生成写像
    $$ KeyGen : \{0,1\}^* \to K_{pub} \times K_{sec} $$
  2. 暗号化写像
    $$ Enc : K_{pub} \times \mathcal{M} \to \mathcal{C} $$
  3. 復号写像
    $$ Dec : K_{sec} \times \mathcal{C} \to \mathcal{M} $$

正しい鍵ペア $ が与えられているなら、暗号化したメッセージは復号によって元に戻るという次のような性質が成り立ちます。

$$ \forall m \in \mathcal{M}, \quad Dec(SK, Enc(PK, m)) = m $$

5. RSAの流れ

代表的な公開鍵暗号方式であるRSA暗号は、次のステップで動作します。

  1. RSAの鍵生成 ($KeyGen$):
    • 大きな素数 $p, q$ をランダムに生成し、$n = pq$ を計算する。
    • $\varphi(n) = (p-1)(q-1)$ を計算する。(オイラー関数を利用)
    • $1 < e < \varphi(n)$ で $\gcd(e, \varphi(n)) = 1$ を満たす $e$ を選ぶ。
    • $ed \equiv 1 \pmod{\varphi(n)}$ を満たす $d$ を計算する。
    • 公開鍵を $PK = (n, e)$、秘密鍵を $SK = (n, d)$ とする。
  2. RSAの暗号化 ($Enc(PK, m)$):
    $$ c = m^e \mod n $$
  3. RSAの復号 ($Dec(SK, c)$):
    $$ m = c^d \mod n $$

このように、公開鍵暗号方式は「鍵生成」「暗号化」「復号」という3つの写像の組で定義されます。

 

PR