ElGamal数字签名算法需要使用随机数，它是一种非确定性的签名方案，但它的运算过程并非是ElGamal加密算法的逆过程。
1.用户选择密钥
系统先选取一个大素数p及p的本原根a，用户A选择一个随机数x（1xp-1）作为自己的私钥，计算y=axmod p，将y作为自己的公钥。整个系统公开的参数有大素数p、本原根a以及每个用户的公钥；而每个用户的私钥x则严格保密。
2.签名过程
给定消息M，用户A进行下述计算来实现签名。
(1)选择随机数k∈Zp*,且k与p-1互素(注意：随机数k需要保密)。
(2)签名方A对消息M进行散列压缩后得到消息散列码H(M),再计算
r=ak mod p
s=（H(M)-xr）k-1mod(p-1)
将(r,s)作为用户A对消息M的数字签名,与消息M一起发送给接收方。
3.验证签名的过程
接收方B在收到消息M与数字签名(r,s)后,先计算消息M的散列码H(M)。然后计算
yrrs mod p=aH(M) mod p
如果上式成立,则可确信(r,s)为有效签名,否则认为签名是伪造的。
4.证明验证签名的正确性
若(r,s)为合法用户采用 ElGamal数字签名算法对消息M的签名,则
yrrs=(ax)r(ak)s=axr+ksmod p
又因为
s=(H(M)-xr)k-1mod(p-1)
两边乘k再移项得
ks+xr=H(M)mod(p-1)
根据模运算规则有
axr+ks=aH(M)mod pmod p
由费马定理的推论,ak=ak mod（p-1）mod p,将k替换成H(M),有
axr+ks=aH(M)mod p
因此有
yrrs=aH(M)mod p
