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