ElGamal署名

table:離散

有限体 離散対数問題(DLP) ElGamal署名 DSA

秘密鍵

x

公開鍵

p 素数

g 原始元

$ y = g^x \mod p

署名

M めっせーじ(のハッシュ?)

k を選ぶ 1 から p-1の数 gcd(k, p-1) = 1 ? 複数署名で衝突しないこと

$ r = g^k \mod p

$ t = (M - xr)k^{-1} \mod p - 1

検証

$ g^M ≡ y^rr^t (\mod p)

gに戻す

g^M = g^{xr+kt}

べき乗で比較

M = xr + k(M-xr)k^-1

kが消えて成立

M = xr + M - xr

変形ElGamal署名