鍵交換 (配送) アルゴリズム
代表的な公開鍵暗号を用いた鍵交換 (配送) アルゴリズムを示す.
DH
離散対数問題の難しさを利用したW. DiffieとM. Hellmanにより考案された鍵共有方式であり,Diffie-Hellman法 (DH法)と呼ばれている.
- 鍵
- 秘密鍵: $x\ (x \in Z_{p-1})$
- 公開鍵: $y\ (y = g^x \bmod p)$
- システムパラメータ:$p$,$g$
素数 $p$,乗法群 ${Z_p}^*$ での原始元 $g$
- 鍵共有
利用者 $A$ と $B$ が鍵を共有したければ,互いに相手の公開鍵 $(y_A, y_B)$ を入手し,それを "自分の秘密鍵 $(x_A, x_B)$" 乗して $p$ で割った余りを求めることで同じ鍵
$K_{AB}$ を共有することができる.
\[ K_{AB} = y_A^{x_B} \bmod p = y_B^{x_A} \bmod p = g^{x_A x_B} \bmod p \]
ECDH
DH法の楕円曲線版である.
- 鍵
- 秘密鍵: $x$ (整数)
- 公開鍵: $Y$ (楕円曲線上の点)
楕円曲線上の点のスカラー倍演算 $Y = x P$ により求める.
- システムパラメータ:$E$, $P$
楕円曲線 $E$ (楕円曲線を定義するパラメータ)
楕円曲線上のベースポイント $P$
- 鍵共有
利用者 $A$ と $B$ が鍵を共有したければ,互いに相手の公開鍵 $(Y_A, Y_B)$ を入手し,それを自分の秘密鍵 $(x_A, x_B)$ を用いて以下の関係から鍵 $K_{AB}$
を共有することができる.
\[ K_{AB} = x_B Y_A = x_A Y_B = x_A x_B P \]
RSA-KEM
RSA-KEM は,共通鍵暗号で利用するセッション鍵の配送を行う RSA 暗号を用いた鍵カプセル化メカニズム (KEM:Key Encapsulation Mechanism) である.
- 暗号化
鍵長 $keyLen$ のランダムな鍵 $K$ と暗号文 $C_0$ を生成する.
- 乱数 $r \in \{0,1,\ldots, n-1\}$ を生成する.
- $y = r^e \bmod n$
- $K = \mathrm{KDF}(\mathrm{I2OSP}(r, nLen), keyLen)$
- $C_0 = \mathrm{I2OSP}(y, nLen)$
- 暗号文 $C_0$ と鍵 $K$ を出力する.
- 復号
暗号文 $C_0$ を復号し,鍵 $K$ を生成する.
- $|C_0| = nLen$ でない場合,エラー終了.
- $y = \mathrm{OS2IP}(C_0)$
- $y \lt n$ でない場合,エラー終了.
- $r = y^d \bmod n$
- $K = \mathrm{KDF}(\mathrm{I2OSP}(r, nLen), keyLen)$
- 鍵 $K$ を出力する.
PSEC-KEM
PSEC-KEM は,楕円曲線を用いた鍵カプセル化メカニズム (KEM:Key Encapsulation Mechanism)である(PSEC-KEM仕様書).
KEMは,暗号化関数の入力が受信者の公開鍵のみである点を除いて,公開鍵暗号のように働く.
次の 3 つのアルゴリズムから構成される.
- 鍵生成アルゴリズム: $\mathrm{Keygen()}$
公開鍵,秘密鍵のペア $(P_k, S_k)$ を出力する.
- 暗号化アルゴリズム:$\mathrm{Encrypt}(P_k, Option)$
公開鍵 $P_k$ を入力し,データ暗号化鍵,暗号文の組 $(K, C_0)$ を出力する.$Option$ は,楕円点の圧縮形式を示すパラメータである.
- 復号アルゴリズム:$\mathrm{Decrypt}(S_k, C_0)$
秘密鍵 $S_k$ と暗号文 $C_0$ を入力し,データ暗号化鍵 $K$ を出力する.
KEM を用いて,利用者 $A$ と $B$ は以下の手順で鍵共有を行うことができる.
- 利用者 $A$ は,暗号化アルゴリズムを用いて,暗号化鍵 $K$ と暗号文 $C_0$ を作成する.このとき,鍵の共有相手 $B$ の公開鍵を用いる.
- 暗号文 $C_0$ を鍵を共有すべき相手 $B$ に送る.
- 暗号文 $C_0$ を受け取った $B$ は,自身の秘密鍵を用いて復号アルゴリズムにより $C_0$ を復号し,暗号化鍵 $K$ を求める.
- $A$ と $B$ は,暗号化鍵 $K$ を共有する.