ElGamal算法

密鑰對產生辦法：首先選擇一個素數p和兩個隨機數g 、x （g、 x < p ），計算 y ≡ g^x（ mod p ） ，已知y，求解x是非常困難的事情（離散對數求解難題），則其公鑰為 y, g 和p ，私鑰是x ，g和p可由一組用户共享。

ElGamal用於數字簽名。被籤信息為M，首先選擇一個隨機數k ， k與 p - 1互素，計算：

a ≡ g^k ( mod p )

再用擴展 Euclidean 算法對下面方程求解b：

M ≡ xa + kb ( mod p - 1 )

簽名就是( a, b )。隨機數k須丟棄。

驗證時要驗證下式：

y^a * a^b ( mod p ) ≡ g^M ( mod p )

同時一定要檢驗是否滿足1<= a < p。否則簽名容易偽造。

ElGamal用於加密。被加密信息為M，首先選擇一個隨機數k，k與 p - 1互質，計算

a ≡ g^k ( mod p )

b ≡ y^k M ( mod p )

( a, b )為密文，是明文的兩倍長。解密時計算

M ≡ b / a^x ( mod p )

ElGamal簽名的安全性依賴於乘法羣(IFp)* 上的離散對數計算。素數p必須足夠大，且p-1至少包含一個大素數

因子以抵抗Pohlig & Hellman算法的攻擊。M一般都應採用信息的HASH值(如SHA算法)。ElGamal的安全性主要依賴於p和g，若選取不當則簽名容易偽造，應保證g對於p-1的大素數因子不可約。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻擊方法和對策。ElGamal的一個不足之處是它的密文成倍擴張。

美國的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是經ElGamal算法演

變而來。