公開鍵暗号アルゴリズム

代表的な公開鍵暗号アルゴリズム (暗号化・復号) を示す．

素因数分解問題の難しさを利用した公開鍵暗号である（→ RSA 暗号)．

RSA 暗号の安全性や攻撃法に関しては RSA 暗号の安全性を参照．

鍵
- 秘密鍵： $d$ (または，$p$，$q$)， $p$，$q$ は素数 \[ n = pq,\ λ(n) = \mathrm{lcm}(p-1, q-1) \] \[ e \in Z_{λ(n)}\ (3 \le e \le n - 1,\ \gcd(e, λ(n)) = 1) \] \[ d = 1/e \bmod λ(n) \]
- 公開鍵： $e$，$n\ (n = pq)$
暗号化
- 平文 $M$ と公開鍵 $e$ より，暗号文 \[ C = M^e \bmod n \] を生成する．
  実際に利用される暗号では，暗号スキームにより $M$ の長さに以下のような制約がある．
  - RSAES-OAEP では，$n$ のバイト長を $k$ とするとき，$M$ は $k - 2 - 2 hLen$ バイト以下でなければならない．ここで $hLen$ は，EME-OAEP で使用されるハッシュ関数の出力バイト長である．
  - RSAES-PKCS1-v1_5 では，$n$ のバイト長を $k$ とするとき，$M$ は $k - 11$ バイト以下でなければならない．
復号
暗号文 $C$ と秘密鍵 $d$ より，復号文 \[ M = C^d \bmod n \] を生成する．

素因数分解問題の難しさを利用した公開鍵暗号である．加法準同型性を持つ．

鍵
- 秘密鍵： $p$，$q$ (または $λ$)
  ・素数 $p$，$q$ を選択し，$n = pq$ とする．また， $λ = \mathrm{lcm} (p-1, q-1)$ とする．
  ・$\mathrm{L}(u) = (u - 1) / n$
  ・$n^2$ と互いに素である $g$ で以下の条件を満たすように選択する．
  　$\gcd(\mathrm{L}(g^λ \bmod n^2), n) = 1$
  ・$μ = \{\mathrm{L}(g^λ \bmod n^2)\}^{-1} \bmod n$ とする．
  
  秘密鍵として上記の $λ$ と $μ$ を保持していれば，復号を効率化できる．
- 公開鍵： $g$，$n$
暗号化
平文 $M\ (\lt n)$ と公開鍵 $n$，$g$，および $n$ と互いに素な乱数 $r\ (\lt n)$ を用いて暗号文 \[ C = g^M \cdot r^n \bmod n^2 \] を生成する．
復号
暗号文 $C\ (\lt n^2)$ と秘密鍵より，復号文 \[ M = \{\mathrm{L}(C^λ \bmod n^2) /\mathrm{L}(g^λ \bmod n^2)\} \bmod n \] を生成する．
あらかじめ $μ = \{\mathrm{L}(g^λ \bmod n^2)\}^{-1} \bmod n$ を求めておけば， \[ M = \mathrm{L}(C^λ \bmod n^2)\cdot μ \bmod n \] で求められる．

素因数分解問題の難しさを利用した公開鍵暗号である．

鍵
- 秘密鍵： $p$，$q$ ($p$，$q$ は素数)
- 公開鍵： $b\ (0 \le b \lt n)$， $n\ (n = pq)$
暗号化
平文 $M$ より，暗号文 \[ C = M (M + b) \bmod n \] を生成する．
復号
暗号文 $C$ と秘密鍵 $p$，$q$ より，以下の連立方程式を満たす $M$ を計算する． \[ M^2 + M b - C = 0 \pmod{p} \] \[ M^2 + M b - C = 0 \pmod{q} \] 上記の方程式には 4 つの解があり，平文を一意に特定することはできない．平文を特定するには，平文に十分な冗長度を持たせる等の条件が必要となる．

Rabin暗号に以下の制限を付けると Williams暗号（制限付きRabin暗号）となる．

素数 $p$，$q$ は，以下の条件を満たす．
$p \equiv q \equiv 3 \pmod{4}$
平文 $M$ は，$0 \lt M \lt n/2$ とする（$n = pq$）．
また，$\left(\frac{M}{n}\right)=1$ とする (Jacobi記号)．

復号は，Rabin暗号の復号アルゴリズムと同じ処理を実行し，$\left(\frac{M}{n}\right)=1$ かつ $0 \lt M \lt n/2$ を満たすものを選択する．

離散対数問題の難しさを利用した公開鍵暗号である．

鍵
- 秘密鍵： $x\ (x \in Z_{p-1})$
- 公開鍵： $y\ (y = g^x \bmod p)$
- システムパラメータ：$p$，$g$ (素数 $p$，乗法群 ${Z_p}^*$ での原始元 $g$)
暗号化
平文 $M$ と乱数 $r \in Z_{p-1}$ より，暗号文 \[ C = (c_1, c_2) = (g^r \bmod p,\ y^r M \bmod p) \] を生成する．
復号
暗号文 $C = (c_1, c_2)$ と秘密鍵 $x$ より，復号文 \[ M = c_2 / c_1^x \bmod p \] を生成する．

楕円離散対数問題の難しさを利用した公開鍵暗号である． ElGamal暗号の楕円曲線版である．

鍵
- 秘密鍵： $x\ (x \in {Z_n}^*)$
- 公開鍵： $P\ (P = x G)$
- システムパラメータ
  - 体 $K$ 上の楕円曲線： $E(K)$
  - ベースポイント： $G \in E(K)$
  - $G$ の位数：$n$
暗号化
楕円点 (平文) $M$ と乱数 $r \in Z_n$ に対して，暗号文 $(C_1, C_2)$ を以下のように生成する． \[ (C_1, C_2) = (rG, rP + M) \] ここで，$M$ は楕円点であるため，例えば平文 $m$ を $X$ 座標とし対応する $Y$ 座標を求めて楕円点に変換する必要がある．ただし，$m$ の値によっては，$Y$ 座標が求まらない場合がある．そこで，例えば以下のような方法がとられる．
楕円曲線 $y^2 = x^3 + ax + b\ \pmod{p}$ と $m\ (0 \le m \lt p/N)$ が与えられるとき，$m$ を $N$ 倍し $i\ (0 \le i \lt N - 1)$を加算して異なる $N$ 個の $x_i = N m + i$ を生成する．この $N$ 個の $x_i$ から平方剰余となる $x_i$ を探して $X$ 座標とする ($N$ は定数で例えば $N=100$ とする)．
復号
暗号文 $(C_1, C_2)$ より，$M$ を復号する． \[ M = C_2 - xC_1 \] 楕円曲線上の点 $M$ から平文 $m$ を求めるには，$X$ 座標を $N$ で割ればよい（余りは切り捨て)．