ElGamal 数字签名

由 ElGamal密码体制 启发

素数 p，g 是原根，pg 公开

随机选取 x 作为私钥，计算 $y=g^{x}modp$ 作为公钥

对于消息 m 首先随机选 $k\in {\mathbb{Z}}_{p-1}^{\ast }$

$$r=g^{k}modp$$ $$s=(hash(m)-xr)k^{-1}mod(p-1)$$

$(r,s)$ 构成签名

验证算法：

$$y^r{r}^s\equiv g^{h(m)}(modp)$$

证明正确性：

由 s 的定义得到：

$$sk+xr\equiv h(m)(modp-1)$$

所以

$$g^{h(m)}\equiv g^{sk+xr}\equiv g^{sk}{g}^{xr}\equiv y^r{r}^s(modp)$$