Elgamal

EIGam以公鑰密碼是一種國際公認的較理想公鑰密碼體制，是網絡上進行保密通信和數字簽名的較有效的安全算法。EIGam以公鑰密碼體制在網絡安全加密技術中應用受到密碼學界的廣泛關注。

ElGamal算法，是一種較為常見的加密算法，它是基於1985年提出的公鑰密碼體制和橢圓曲線加密體系。既能用於數據加密也能用於數字簽名，其安全性依賴於計算有限域上離散對數這一難題。在加密過程中，生成的密文長度是明文的兩倍，且每次加密後都會在密文中生成一個隨機數K，在密碼中主要應用離散對數問題的幾個性質：求解離散對數（可能）是困難的，而其逆運算指數運算可以應用平方-乘的方法有效地計算。也就是説，在適當的羣G中，指數函數是單向函數。

ElGamal加密算法由三部分組成：密鑰生成、加密和解密 ^[1]  。

密鑰生成的步驟如下：

Alice利用生成元g產生一個q階循環羣G的有效描述。該循環羣需要滿足一定的安全性質。

Alice從

中隨機選擇一個 x。

Alice計算

。

Alice公開h以及G,q,g的描述作為其公鑰，並保留x作為其私鑰。私鑰保密 ^[1]  。

使用Alice的公鑰(G,q,g,h)向她加密一條消息m的加密算法工作方式如下：

Bob從

隨機選擇一個y，然後計算

。

Bob計算共享秘密

。

Bob把他要發送的秘密消息m映射為G上的一個元素m'。

Bob計算

。

Bob將密文

發送給Alice。

值得注意的是，如果一個人知道了m'，那麼它很容易就能知道

的值。因此對每一條信息都產生一個新的y可以提高安全性 ^[1]  。

利用私鑰x對密文

進行解密的算法工作方式如下 ^[1]  ：

Alice計算共享秘密

然後計算

，並將其映射回明文 m，其中

是s在羣G上的逆元。（例如：如果G是整數模n乘法羣的一個子羣，那麼逆元就是模逆元）。

解密算法是能夠正確解密出明文的，因為

在使用EIGamal加密算法時，模運算是實現公鑰密碼加解密運算速度的關鍵，如何提出並實現一個有效的大整數冪模運算算法是實現公鑰密碼體制的關鍵，所有使用者可以選取使用同樣的素數 p 和生成元，在這種情況下，p不必作為公鑰的一部分而發佈，這可使公鑰的長度小一些。使用固定元素還有另外的優點：可以通過預計算來加快取冪運算，但使用共同系統參數一個潛在的缺點是必須保證模 p足夠大 ^[3]  。

EIGamal公鑰密碼是目前國際公認的較理想公鑰密碼體制，是目前網絡上進行保密通信和數字簽名的較為有效的算法。ElGamal公鑰密碼體制在網絡安全加密技術中應用得到密碼學界的廣泛關注 ^[3]  。

在系統中有兩個用户A和B，A要發送消息到B，並對發送的消息進行簽名。B收到A發送的消息和簽名後進行驗證。

選取一個大的素數p，g是GF(p)的生成元。h：GF(p)→GF(p)，是一個單向Hash函數。系統將參數p、g和h存放於公用的文件中，在系統中的每一個用户都可以從公開的文件中獲得上述參數 ^[4]  。

假定用户A要向B發送消息

，並對消息m簽名 ^[4]  。

第一步：用户A選取一個

作為秘密密鑰，計算

作為公鑰。將公鑰y存放於公用的文件中。

第二步：隨機選取

且

.

第三步：計算

，及

.

第四步：A將

發送到B。

B接收到A發送的消息

，從系統公開文件和A的公開文件中獲得系統公用參數p，g，h和A的公鑰y。

第一步：B計算

.

第二步：B計算

.

第三步：比較left和right，相等則通過驗證 ^[4]  。

ElGamal公鑰密碼算法的加密效率相對於其它公鑰密碼來説是比較慢的，下面對其進行分析 ^[3]  。

(1)加密過程需要兩次模指數運算，即

和

；通過選取具有某種附加結構的隨機指數可加速指數運算，在計算過程中，可以使用一些冪算的乘方等一些算法，也可以對固定的代數結構，制定相應的冪運算表，使得計算起來比較簡單，加密、解密的速度比較快，從而使信息傳遞的速度加快 ^[3]  ；

(2)ElGamal加密算法的一個缺點是傳遞密文的長度是明文長度的二倍，使得傳遞密文的過程中，通信的信息量增大。同時ElGamal加密算法一個最大的特點是在加密過程中進行隨機方式的加密方法，這種方法有着很好的抗攻擊性，可以用以下一個或多個方法隨機增加加密過程的密碼安全性 ^[3]  。

1.增加明文消息空間的長度，即增加所選代數結構中的元素個數；

2.通過一個到多個的明文到密文的映射來減小選擇明文攻擊的有效性；

3.通過統計先驗概率分佈的方法來減小統計攻擊的有效性。

關於EIGamal加密的安全性分析，通常都從兩個方面考慮加密體制的安全性，安全目標和攻擊者的類型 ^[4]  。

加密的安全目標一般看下面兩個：不可區分性(IND)：敵手選擇兩個明文，加密者隨機選取一個，返回其密文，則敵手不能以明顯大於1/2的概率正確猜測選擇的是哪一個明文。語義安全性(SEM)：敵手在知道密文的條件下能有效計算出的有關明文的信息量並不比他不知道密文時的多，除了明文的長度 ^[3]  。

密碼體制的安全性是主要是根據攻擊來定義的，攻擊可分為被動攻擊和主動攻擊，其中被動攻擊，敵手只是監視通信信道，阻止信息傳輸在通信信道上傳輸，被攻擊者只能威脅數據的機密性；主動攻擊，敵方企圖刪除、增加或以其他方式改變信道上的傳輸內容，它會威脅數據的完整性、認證性及機密性，主動攻擊的方法通常分為以下幾種 ^[3]  ：

(1)選擇明文攻擊(CPA)：攻擊者選擇明文消息並得到加密的服務，產生相應的密文，攻擊者的任務是利用所得到的明文．密文對來降低目標密碼體制的安全性；

(2)選擇密文攻擊(CCA)攻擊者選擇密文消息並得到解密服務，產生相應的明文，攻擊者的任務是利用所得到的明。密文對來降低目標密碼體制的安全性，在解密服務停止後，即在得到目標密文之後，解密服務立即停止，如果攻擊者能夠從“目標密文"中得到保密明文的信息，則就説攻擊是成功的；否則攻擊者就是失敗的。

ElGamal加密體制具有選擇明文攻擊下的不可區分性(IND-CPA)，當且僅當計算Diffie-Hellman問題是困難的 ^[3]  。