ElGamal签名方案详解

1985年，ElGamal设计了一种既可用于加密又可以用于签名的公钥密码体制，即ElGa-mal公钥密码体制。ElGamal数字签名方案的安全性基于求解离散对数的困难性。目前，它已成为广泛应用的数字签名方案之一，极大地促进了现代密码学的发展。

1.ElGamal签名的生成与验证算法

（1）参数定义和密钥生成

●p是大素数；

●g是Z_p*的一个生成元（即本原元素）；

●x是一个随机数，且x∈Z_p*。

●计算

y≡g^x（mod p）

则公钥为k₁=（y，p，g）；私钥为k₂=x。

（2）签名算法

签名者拥有密钥（p，g，y，x），设待签名消息为m，签名者选取随机数k∈Z_p^*，计算

r≡g^k（mod p）

s≡（h（m）-xr）k^-1（mod（p-1））

生成签名（r，s），其中h（m）为消息摘要。

（3）验证算法

验证者拥有公钥k₁=（y，p，g），他收到明文m和签名（r，s）后，首先计算h（m），然后验证

y^rr^s≡g^h（m）（mod p）

若等式成立，则签名有效；否则，签名无效。

实际上，因为

ks≡（h（m）-xr）（mod（p-1））(https://www.xing528.com)

即

ks=λ（p-1）+（h（m）-xr）

于是有

利用欧拉定理g^p-1（mod p）≡1，就有

所以

又

y≡g^x（mod p）

因此有

【例6-2】 设p=19，g=2，私钥x=9，若消息m的Hash值为52，试用ElGamal数字签名方案计算对消息m的签名，并验证签名的有效性。

【解析】 发送者计算

取k=5，则有

所以得到签名（r，s）=（13，5）。

接收者收到明文m和签名（r，s）后，首先计算h（m）=52，然后计算

所以有

y^rr^s≡g^h（m）（mod p）验证了签名的有效性。

2.ElGamal签名方案的安全性

1）ElGamal数字签名方案的安全性依赖于乘法群上的求离散对数的困难性。若能求离散对数，则由y和g，可求出私有密钥x，该签名方案就不安全。

2）要求素数p必须足够大，且p-1至少包含一个大素数，第三者欲伪造一合法签名，则面临求离散对数问题。

3）ElGamal签名算法是一个非确定性的数字签名算法，对同一个消息M所产生的签名依赖于随机数k。该算法还要求随机数k不能泄露，且每次都不相同；否则，用x≡（h（m）-sk）r^-1（mod p）就可以在已知明文的情况下窃取私钥。