公開鍵暗号アルゴリズム
代表的な公開鍵暗号アルゴリズム (暗号化・復号) を示す．
RSA暗号
素因数分解問題の難しさを利用した公開鍵暗号である（→ RSA 暗号)．
- 鍵
- 秘密鍵： d (または，p，q)， p，q は素数
n = pq， λ(n) = LCM (p-1, q-1)
e ∈ Zλ(n) (3 ≦ e ≦ n - 1, GCD (e, λ(n)) = 1)
d = 1/e mod λ(n) - 公開鍵： e，n (n = pq)
- 秘密鍵： d (または，p，q)， p，q は素数
- 暗号化
- 対象データ M と公開鍵 e より，暗号データ
C = M e mod n
を生成する．
実際に利用される暗号では，暗号スキームにより M の長さに以下のような制約がある．- RSAES-OAEP では，n のバイト長を k とするとき，M は k - 2 - 2 hLen バイト以下でなければならない．ここで hLen は，EME-OAEP で使用されるハッシュ関数の出力バイト長である．
- RSAES-PKCS1-v1_5 では，n のバイト長を k とするとき，M は k - 11 バイト以下でなければならない．
- 対象データ M と公開鍵 e より，暗号データ
- 復号
暗号文 C と秘密鍵 d より，復号データM = C d mod n
を生成する．
Rabin暗号
素因数分解問題の難しさを利用した公開鍵暗号である．
- 鍵
- 秘密鍵： p，q (p，q は素数)
- 公開鍵： b (0 ≤ b < n)， n (n = p q)
- 暗号化
対象データ M より，暗号文
C = M (M + b) mod n
を生成する． - 復号
暗号文 C と秘密鍵 p，q より，以下の連立方程式を満たす M を計算する．
M2 + M b - C = 0 (mod p)
M2 + M b - C = 0 (mod q)
上記の方程式には 4 つの解があり，平文を一意に特定することはできない．平文を特定するには，平文に十分な冗長度を持たせる等の条件が必要となる．
Rabin暗号に以下の制限を付けると Williams暗号（制限付きRabin暗号）となる．
- 素数 p，q は，以下の条件を満たす．
p ≡ q ≡ 3 (mod 4) - 平文 M は，0 < M < n/2 とする（n = pq）．
また，(M/n) = 1 とする． （x/y) はJacobi記号を示す．
復号は，Rabin暗号の復号アルゴリズムと同じ処理を実行し，(M/n)=1 かつ 0＜M＜n/2 を満たすものを選択する．
ElGamal暗号
離散対数問題の難しさを利用した公開鍵暗号である．
- 鍵
- 秘密鍵： x (x ∈ Zp-1)
- 公開鍵： y (y = gx mod p)
- システムパラメータ：p，g (素数 p，乗法群 Zp*での原始元 g)
- 暗号化
対象データ M と乱数 r ∈ Zp-1 より，暗号文
C = (c1, c2) = (gr mod p, yr M mod p)
を生成する． - 復号
暗号文 C = (c1, c2) と秘密鍵 x より，復号データ
M = c2 / c1x mod p
を生成する．
楕円ElGamal暗号
楕円離散対数問題の難しさを利用した公開鍵暗号である． ElGamal暗号の楕円曲線版である．
- 鍵
- 秘密鍵： x (x ∈ Zn*)
- 公開鍵： P (P = x G)
- システムパラメータ
- 体 K 上の楕円曲線： E(K)
- ベースポイント： G ∈ E(K)
- G の位数：n
- 暗号化
メッセージ M と乱数 r ∈ Znに対して，暗号文 (C1, C2) を以下のように生成する．(C1, C2) = (rG, rP + M)
ここで，M は楕円点であるため，例えば平文メッセージ m を X 座標とし対応する Y 座標を求めて楕円点に変換する必要がある． ただし，m の値によっては，Y 座標が求まらない場合がある． そこで，例えば以下のような方法がとられる．
楕円曲線 y2 = x3 + ax + b (mod p) と m (0 ≤ m < p/N) が与えられるとき，m を N 倍し i（0 ≤ i < N-1）を加算して異なる N 個の xi = Nm + i を生成する．この N 個の xi から平方剰余となる xi を探して X 座標とする (N は定数で例えば N=100 とする)． - 復号
暗号文 (C1, C2) より，メッセージ M を復号する．M = C2 - x C1
楕円曲線上の点 M から 平文メッセージ m を求めるには，X 座標を N で割ればよい（余りは切り捨て)．
／