ElGamal密码算法既可以用于加密又可以实现数字签名。

选p是一个大素数，p-1含有大素数因子。α是一个模p的本原元，将p和α公开。用户随机地选择一个整数x作为自己的秘密密钥，1≤x≤p-1，计算y≡αx mod p，取y为自己的公开密钥。公开参数p和α可以由一组用户共用。

1.产生签名

设用户A要对明文消息M签名，0≤m≤p-1，其签名过程如下：

•用户A随机地选择一个整数k，1＜k≤p-1，且（k，p-1）=1；

•计算r=αk mod p；

•计算s=（m-xA r）k-1 mod（p-1）；(www.daowen.com)

•取（r，s）作为M的签名，并以＜m，r，s＞的形式发给用户B。

2.验证签名

用户B验证αm=yrA rs，是否成立，若成立则签名为真，否则签名为假。签名的可验证性证明如下：

因为s=（m-xA r）k-1 mod（p-1），所以m=xA r+ks mod（p-1），故αm=αxAr+ks=yrA rs mod p，签名可验证。

对于上述E1Gamal数字签名，为了安全，随机数k应当是—次性的。否则，可用过去的签名冒充现在的签名。由于取（r，s）作为M的签名，所以ElGamal数字签名的数据长度是明文的两倍，即数据扩展一倍。