5.5.3 ElGamal数字签名
ElGamal签名方案是由ElGamal在1985年提出的，其安全性是基于有限域上离散对数求解的困难性。该算法既可用于签名，也可用于加密，且该数字签名是随机化的签名方案，即对于给定的消息其签名结果不是确定值。
1.发送方密钥的生成
（1）随机产生一个大素数p，以及乘法群
上的一个生成元g；
（2）随机选择整数a，1≤a≤p-2，计算y=ga mod p，则公钥是p，g，y（），私钥是a。
2.签名过程
（1）随机选择一个数k，并满足1≤k≤p-2和gcd（k，p-1）=1，计算r=gk mod p；
（2）计算k-1 mod（p-1）；
（3）计算s=k-1{h（m）-ar}mod（p-1），则对消息m的签名为（r，s）。
3.验证过程
（1）获得公钥p，g，y（），验证1≤r≤p-1，否则拒绝该签名；
（2）计算v1=yrrs mod p；
（3）计算h（m）和v2=gh（m）mod p，当且仅当v1=v2时接受签名。
例5-6 利用ElGamal签名方案完成签名。
密钥生成过程如下。
（1）发送方选择素数p=2 357和Z*p上的生成元g=2；
（2）发送方选择私钥a=1 751，并计算
y=ga mod p=21751 mod 2 357=1 185
则公钥为p=2 357，g=2，y=1 185（）。
签名生成过程如下。
为简单起见，选择Hash函数为h（m）=m。
（1）发送方选择随机数k=1 529，计算
r=gk mod p=21529 mod 2 357=1 490
（2）计算k-1 mod（p-1）=245；
（3）计算
s=k-1{h（m）-ar}mod(p-1)=245{1 463-1 751×1 490}mod 2 356=1 777
则对消息m=1 563的签名为r=1 490，s=1 777（
）。
签名验证过程如下。
（1）接收方计算
v1=yrrs mod p=1 1851490×1 4901777 mod 2 357=1 072
（2）计算
h（m）=1 463和v2=gh（m）mod p=21463 mod 2 357=1 072
因为v1=v2，所以接受签名。
4.ElGamal签名的安全性
（1）在ElGamal签名方案中，伪造一个签名成功的概率为1/p，当p很大时，成功的概率可以忽略。其中，Hash函数起到了重要的作用，因为若不采用Hash函数，则签名很容易被伪造成功。
（2）对于不同的消息，必须选择不同的随机数k，因为多次使用相同的随机数，可以推算出私钥。
（3）签名的验证者需要验证0＜r＜p，因为不满足此条件的系统，可以根据一个有效的签名为任意的消息生成有效的签名。
（4）在签名前，必须使用Hash函数对消息m进行计算。否则攻击者很容易成功伪造出其他消息的有效签名：任选一整数对（u，v），gcd（v，p-1）=1。计算r=auyv mod p=au+av mod p和s=-rv-1 mod（p-1）。则（r，s）就是对消息m=su mod（p-1）的一个有效签名，因为
。