基本介紹
算法定義,密鑰產生,數字簽名方案,系統初始化,數字簽名,簽名驗證,
算法定義
ElGamal算法，是一種較為常見的加密算法，它是基於1985年提出的公鑰密碼體制和橢圓曲線加密體系。既能用於數據加密也能用於數字簽名，其安全性依賴於計算有限域上離散對數這一難題。在加密過程中，生成的密文長度是明文的兩倍，且每次加密後都會在密文中生成一個隨機數K，在密碼中主要套用離散對數問題的幾個性質：求解離散對數（可能）是困難的，而其逆運算指數運算可以套用平方-乘的方法有效地計算。也就是說，在適當的群G中，指數函式是單向函式。
密鑰產生
密鑰對產生辦法。首先選擇一個素數p，獲取一個素數p的一個原根g(若g模p的階等於φ(p)，則稱g為模p的一個原根。（其中φ(p)表示p的歐拉函式，即所有<=p的正整數中和p互質的整數的個數）) 和一個隨機數x，且g和 x 均小於 p, 計算 y = g^x ( mod p )，則其公鑰為 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的大素數因子不可約。
數字簽名方案
在系統中有兩個用戶A和B，A要傳送訊息到B，並對傳送的訊息進行簽名。B收到A傳送的訊息和簽名後進行驗證。
系統初始化
選取一個大的素數p，g是GF(p)的本原元。h：GF(p)→GF(p)，是一個單向Hash函式。系統將參數p、g和h存放於公用的檔案中，在系統中的每一個用戶都可以從公開的檔案中獲得上述參數。
數字簽名
假定用戶A要向B傳送訊息m [1,p-1]，並對訊息m簽字。第一步：用戶A選取一個x [1,p-1]作為秘密密鑰，計算y= (mod p)作為公鑰。將公鑰y存放於公用的檔案中。第二步：隨機選取k [1,p-1]且gcd(k,(p-1))=1，計算r= (mod p)。對一般的ElGamal型數字簽名方案有簽名方程（Signature Equation）：ax=bk+c(mod(p-1))。
其中(a，b，c)是(h(m),r,s)數學組合的一個置換。由簽名方程可以解出s。那么(m,(r,s))就是A對訊息m的數字簽名。第三步：A將(m,(r,s))傳送到B
簽名驗證
當B接收到A傳送的訊息(m,(r,s))，再從系統公開檔案和A的公開檔案中獲得系統公用參數p，g，h和A的公鑰y。由(m,(r,s))計算出(a，b，c)驗證等式：y^r·r^s = g^m(mod p)是否成立。
D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻擊方法和對策。ElGamal的一個不足之處是它的密文成倍擴張。
美國的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是經ElGamal算法演
變而來。
