ElGamal数字签名

ElGamal数字签名方案使用私钥加密，公钥解密。

ElGamal数字签名方案的基本元素是素数q和a，其中a是q的原根。用户A通过以下步骤产生公钥/私钥对：

1. 生成随机整数x,使得 1<x<q-1
2. 计算y=a^x mod q
3. A的私钥是x，公钥是{q，a，y}

要对消息M签名，用户A首先计算哈希值m=H（M），这里m是一个满足0<=m<=q-1的整数，然后A通过下列步骤产生数字签名：

1. 选择一个随机整数k，使得1<=k<=q-1，并且gcb(k,q-1)=1,即k与q-1互素
2. 计算s1=a^k mod q 
3. 计算k^(-1) mod (q-1) 即 计算k模q-1的逆
4. 计算s2=k^(-1)(m-xs1)mod(q-1)
5. 签名包括（s1，s2）对

任意用户B都能通过如下步骤验证签名：

1. 计算v1=a^m mod q
2. 计算 v2=(y^s1)(s1^s2) mod q
3. 如果v1=v2，则签名合法

举例如下：

下图是10 (mod 19)的整数幂（其中a是10）

可以理解为

由知道此处取a=10，q=19

假设Alice想用哈希值m=14来对消息进行签名：

1. 选择x=16
2. 计算y=a^x mod q = 10^16 mod 19 =4 (可查看上图查找）
3. Alice的私钥为16，公钥为{q，a，y}={19,10,4}

假设Alice想用哈希值m=14对消息进行签名：

1. Alice选择k=5，因为gcb(5,18)=1（并且，k的选择要在1-18间）
2. s1=a^k mod q = 10^5 mod 19 = 3
3. k^(-1) mod (q-1) =5^(-1) mod 18 =11 (分数模运算）
4. s2=k^(-1)(m-xs1)mod(q-1) =( (k^(-1) mod (q-1) ) ((m-xs1) mod (q-1)) ) mod (q-1) = 11 x2  mod 18 =4

Bob可以对签名进行验证

1. v1=a^m mod q = 10 ^14  mod  19 = 16
2. v2=(y^s1)(s1^s2) mod q  =(4^3) (3^4) mod 19 = 5184 mod 19 =16
3. 因此签名有效