ElGamal算法既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴于計算有限域上離散對數(shù)這一難題。
密鑰對產(chǎn)生辦法。首先選擇一個素數(shù)p，兩個隨機數(shù), g 和x，g, x < p, 計算 y = g^x ( mod p )，則其公鑰為 y, g 和p。私鑰是x。g和p可由一組用戶共享。
ElGamal用于數(shù)字簽名。被簽信息為M，首先選擇一個隨機數(shù)k, k與 p - 1互質(zhì)，計算
a = g^k ( mod p )
再用擴展 Euclidean 算法對下面方程求解b：
M = xa + kb ( mod p - 1 )
簽名就是( a, b )。隨機數(shù)k須丟棄。
驗證時要驗證下式：
y^a * a^b ( mod p ) = g^M ( mod p )
同時一定要檢驗是否滿足1<= a < p。否則簽名容易偽造。
ElGamal用于加密。被加密信息為M，首先選擇一個隨機數(shù)k，k與 p - 1互質(zhì)，計算
a = g^k ( mod p )
b = y^k M ( mod p )
( a, b )為密文，是明文的兩倍長。解密時計算
M = b / a^x ( mod p )
ElGamal簽名的安全性依賴于乘法群(IFp)* 上的離散對數(shù)計算。素數(shù)p必須足夠大，且p-1至少包含一個大素數(shù)
因子以抵抗Pohlig & Hellman算法的攻擊。M一般都應采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依賴于p和g，若選取不當則簽名容易偽造，應保證g對于p-1的大素數(shù)因子不可約。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻擊方法和對策。ElGamal的一個不足之處是它的密文成倍擴張。
美國的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是經(jīng)ElGamal算法演變而來。