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簽字體製作為簽名標準算法。