一.ElGamal数字签名方案
1.1 知识引用
ElGamal数字签名使用私钥进行加密，使用公钥进行解密。
基本元素是p和α，α是p的原根，用户产生私钥/公钥对的方法如下。
数字签名的过程为：
（1) 选择随机整数K，K和q-1互素。
（2）S1=α^Kmod(q)
(3) 计算K^-1mod(q-1)
(4) S2=K^-1（m-XAS1)mod(q-1)。m=H(M)，是M在哈希函数H下的哈希值，满足0<=m<=q-1的整数
(5) (S1,S2)为签名
验证签名的方法为：
证明为：
1.2 例题
ElGamal数字签名方法：模数q=19，选取随机数K=11，对消息m=4的签名（S1，S2）=（2，4）。
（1）若敌手知晓K=11，请写出计算出私钥XA的过程。
由前文数字签名的过程（4）
即得到
4=5×（4-2×XA） mod (18) XA 取值在1和18之间
XA=7
PS：
求K逆的过程比较简单的可以使用欧几里得除法，如本题可求得为5
（2）若敌手不知晓K，但敌手截获另一也选取同一随机数K的对m’=17的签名（2，15），则其也可以计算出私钥XA，请写出计算过程
解得XA=(18n-8)/22,XA=7.
二、ElGamal公钥密码算法描述
2.1算法介绍
1. 选取一个大素数p，使离散对数问题在有限域GF(p)上是难解的，选取g∈Z是一个本原元。
2. 随机选取整数x，1≤x≤p-2,计算y=g^x(mod p); y是公开的加密密钥，而x是保密的脱密密钥。
3. 明文空间为Z，密文空间为Z×Z。
4. 加密变换：对任意明文m∈Z，秘密地随机选取一个整数k，1≤k≤p-2，于是可得密文为：
c=(c1,c2)
其中
c1=g^k(mod p) , c2=my^k(mod p)
5. 脱密变换：对任意密文c=(c1,c2)∈Z×Z，明文为：
m=c2×(c1^x)^-1(mod p)
证明：
c2×(c1^x)^-1(mod p)=my^k(g^(kx))^-1 (mod p)
=mg^kx × g^(-kx) (mod p)=m (mod p)
2.2算法例题
Alice的私钥XA=11，公开参数q=19,α=5。
（1）计算Alice的公钥YA
这里介绍一种模重复平方计算法，计算过程如下：
结果是6
（2）选取k=3，计算对M=7用Alice的公钥加密后得到的密文。
（3）Alice收到密文C=（4，7），用私钥对密文解密，求其得到的明文。
文章出处登录后可见！
