署名アルゴリズム

代表的な公開鍵暗号を用いたディジタル署名アルゴリズムを示す．

RSA署名

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

鍵
- 秘密鍵： d (または，p，q)， p，q は素数
  n = pq， λ(n) = LCM (p-1)(q-1)
  e ∈ Z_λ(n)　(GCD (e, λ(n)) = 1)
  d = 1/e mod λ(n)
- 公開鍵： e，n (n = pq)
署名生成
署名対象データ mと秘密鍵 d より，署名 s = h(m)^d mod nを生成する．ここで， h はハッシュ関数， s は n 未満の整数である．
署名検証
署名対象データ m，署名 s および公開鍵 e より，署名の正当性を以下の関係が成立するか否かで判定する．
h(m) = s^e mod n

DSA署名

米国の連邦標準技術局(NIST)により提案されたディジタル署名標準(DSS)である (FIPS PUB 186-3)．

鍵
- 秘密鍵： x (x ∈ Z_q^*)
- 公開鍵： y (y = g^x mod p)
- システムパラメータ：p，q，g
  素数 p，q (q|p-1)
  乗法群 Z_p^*での位数が q となる g
  標準的な p のサイズは1024ビット，q のサイズは160ビット
  これらのシステムパラメータの生成方法をシステムパラメータ生成に示す．
署名生成
署名対象データ m と秘密鍵 x より，署名 (r, s) を生成する．
r = (g^k mod p) mod q

s = (k^-1 (h(m) + xr)) mod q
ここで，k は 0 < k < q なる乱数，h はハッシュ関数(SHA-1)である．
署名検証
署名対象データ m ，署名 (r, s)および公開鍵 y を与えて，署名が正しいか否かを判定する．
w = s^-1 mod q

u1 = (h(m) w) mod q

u2 = (r w) mod q

v = (g^u1y^u2 mod p) mod q

v = r ならば署名は正しい．

ECDSA署名

DSA署名の楕円曲線版である．

鍵
- 秘密鍵： x (整数)
- 公開鍵： P (楕円曲線上の点)
  楕円曲線上の加法演算 P = x * G により求める．
- システムパラメータ：E, G, n=#G
  楕円曲線 E (楕円曲線を定義するパラメータ)
  楕円曲線上のベースポイント G とその位数 n
署名生成
署名対象データ m より，署名 (r, s) を生成する．

R = (r, r') = k * G 　(k ∈ Z/nZ：乱数)

s = k^-1(h(m) + xr) mod n
ここで，h はハッシュ関数である．
署名検証
署名対象データ m，署名 (r, s) および公開鍵 P より，署名が正しいか否かを判定する．

(x, y) = (h(m) s^-1 mod n) * G + (r s^-1 mod n) * P

x = r ならば，署名は有効

Schnorr 署名

離散対数問題の難しさを利用した署名である．

鍵
- システムパラメータ：p，q，g
  素数 p，q (q|p-1)
  乗法群 Z_p^*での位数が q となる g
- 秘密鍵： x ∈ Z_q
- 公開鍵： y
  
  y = g^-x mod p
署名生成
署名対象データ m より，署名 (e, s) を生成する．

乱数 r ∈ Z_q

e = h (g^r mod p, m)

s = (r + x e) mod q
ここで，h ( , ) はハッシュ関数である．
署名検証

e' = h (g^s y^e mod p, m)

e' = e ならば，署名は有効

ECAO署名

ECAO（Elliptic Curve Abe-Okamoto signature）は，1999年に NTT が開発した安全性の高さが数学的に証明された楕円曲線上の離散対数問題に基づくメッセージ回復型デジタル署名である．

システムパラメータ
- 体 K 上の楕円曲線： E(K)
- ベースポイント： G ∈ E(K)
- G の位数：n
- ハッシュ関数 (k + t >= n)
  H₁：{0,1}^t　→　{0,1}^k
  H₂：{0,1}^k　→　{0,1}^t
  H ：{0,1}^{k + t}　→　{0,1}ⁿ
鍵生成
- 秘密鍵： x (x ∈ Z_n^*)
- 公開鍵： P (P = x G)
署名生成
メッセージ m (長さ t)に対して署名 s を以下のように生成する．
- 乱数 r ∈ Z_n を生成する．
- m' = H₁(m) || (H₂(H₁(m)) ^ m) を計算する (^ は XOR)．
- r G = (rx, ry)
- u = rx ^ m'，e = H(u)，v = (r - ex) mod n
- s = (u, v) を署名とする．
署名検証
メッセージ m，署名 s および公開鍵 P を与えて，署名が正しいか否かを判定する．
- e = H(u)，m' = u ^ (vG + eP)_x
- m = [m']_t ^ H₂([m']^k) を計算する．
  ここで，[ a]_b は a の最下位 b ビット，[a]^b は a の最上位 b ビットを示す．
- [m']^k = H₁(m) ならば署名は有効