Elgamal算法由T.E1Gamal在1985年发表的一篇论文中提出，是Rabin体制的一种变型。其修正形式已被美国国家标准技术研究所作为数字签名标准(DS),其核心就是著名是数字签名方法(DSA)。与RSA密码体系既可以用于公钥加密又可以用于数字签名等计划。E1gamal数字签名计划是专门为数字签名的意图而规划的。后来有很多变型的Elgamal签名计划被提出。在1989年,Schnorr提出了一种可看做是Eigamal数字签名计划的变型的一种签名计划,其签名的长度被大大地缩短了。数字签名办法(DSA)是E1Gamal数字签名计划的另外一种变型,它吸收了Schnorr签名计划的一些思维。
Elgamal数字签名算法的理论基础是求解离散对数的困难性。基于离散对数问题的数字签名体制是数字签名体制中最为常用的一类,其中包括 Elgamal签字体制、DSA签字体制、 Okamoto签字体制等。
Elgamal数字签名方案可分为初始化进程(设置体系参数,发生密钥)、签名进程和验证进程三个部分。
1)初始化过程—设置系统参数,产生密钥
p、q为两个大素数,可使Z*q中求解离散对数为困难问题。用户A秘密密钥x∈Z*q;
用户A的公开密钥为y=gx mod p 。
2)签名过程
对于待签名的消息m,用户A执行以下步骤:
(1)计算m的散列值H(m)。
(2)选择随机数k:k∈RZ*p,计算r=gk(mod p)
其中, k∈RZ*q表示k是以Z*p中随机选取的, Z*p=Zp-{0}
(3)计算s=(H(m)-xr)k-1-(mod p-1)。(r,S)即为产生的数字签名。
3)验证过程
接收方在收到消息m和数字签名(r,s)后,先计算H(m)并按下式验证:
Ver(y,(r,s),H(m))=True台→yrrs=gH（m）(mod p)
正确性可由下式证明:
yrrs =grxgks=grx+H（m）-rx=gH(m)(mod p)
4)安全性
该方案的安全性基于求离散对数的困难性。所谓离散对数,就是给定正整数x、y、n求出正整数k(如果存在的话),使y=xk(mod n)。就目前而言,人们还没有找到计算离散对数的快速算法(所谓快速算法,是指其计算复杂性在多项式范围内的算法,即O(logn)k,其中k为常数)。
该计划的安全性根据求离散对数的困难性。所谓离散对数,就是给定正整数x、y、n求出正整数k(如果存在的话),使y=xk(mod n)。就现在而言,人们还没有找到核算离散对数的快速算法(所谓快速算法,是指其核算复杂性在多项式范围内的算法,即O(logn)k,其间k为常数)。
5)应用
此体制专门设计作为签名使用ANSIX9.30-199X已将Eigamal签字体制作为签名标准算法。
