更新:2025/02/05
数学的な視点で見た公開鍵暗号方式について
はるか
公開鍵暗号方式、秘密鍵と公開鍵の2つを使う。
ふゅか
そうそう！送る側は公開鍵で暗号化、受け取る側は秘密鍵で復号するの！
目次
1. 公開鍵暗号方式とは？
公開鍵暗号方式とは、通信の安全性を確保するための暗号技術の一つであり、インターネット上でのデータのやり取りに広く利用されています。この方式では、受信者の「公開鍵」と「秘密鍵」の2つの鍵を使用してデータの暗号化と復号を行います。
2. 公開鍵暗号方式で必要な関数
公開鍵暗号方式は、大きく分けて以下の3つの写像（関数）によって構成されると考えることができます。
- 鍵生成関数
KeyGen
秘密鍵 $SK$ と公開鍵 $PK$ のペアを生成する写像です。
$$ (PK, SK) = KeyGen(1^n) $$
ここで $1^n$ は鍵の長さなどを表します。 - 暗号化関数
Enc(PK, m)
公開鍵 $PK$ を引数として受け取り、平文（メッセージ） $m$ を暗号文 $c$ に変換する写像です。
$$ c = Enc(PK, m) $$ - 復号関数
Dec(SK, c)
秘密鍵 $SK$ を引数として受け取り、暗号文 $c$ から平文 $m$ を取り出す写像です。
$$ m = Dec(SK, c) $$
はるか
Enc関数。公開鍵を使ってメッセージを暗号文に変換する。
ふゅか
そして復号するのがDec関数ね！秘密鍵を使って元のメッセージに戻すんだ！
3. $\mathcal{M}$ と $\mathcal{C}$ について
公開鍵暗号方式においては、暗号化対象のメッセージ（平文）を表す集合を$\mathcal{M}$（メッセージ空間）、
暗号化によって得られる暗号文を表す集合を$\mathcal{C}$（暗号文空間）として、それぞれ有限集合であると考えます。
4. 公開鍵暗号方式を「写像」で表すとどうなるか
公開鍵暗号方式を写像（関数）の組で表すと、以下のようになります。
- 鍵生成写像
$$ KeyGen : \{0,1\}^* \to K_{pub} \times K_{sec} $$ - 暗号化写像
$$ Enc : K_{pub} \times \mathcal{M} \to \mathcal{C} $$ - 復号写像
$$ Dec : K_{sec} \times \mathcal{C} \to \mathcal{M} $$
正しい鍵ペア $ が与えられているなら、暗号化したメッセージは復号によって元に戻るという次のような性質が成り立ちます。
$$ \forall m \in \mathcal{M}, \quad Dec(SK, Enc(PK, m)) = m $$
5. RSAの流れ
代表的な公開鍵暗号方式であるRSA暗号は、次のステップで動作します。
- 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)$ とする。
- RSAの暗号化 ($Enc(PK, m)$):
$$ c = m^e \mod n $$ - RSAの復号 ($Dec(SK, c)$):
$$ m = c^d \mod n $$
このように、公開鍵暗号方式は「鍵生成」「暗号化」「復号」という3つの写像の組で定義されます。
PR
