密碼學(xué) ElGamal密碼體制

ELGamal密碼體制是T.ElGamal在1985年提出的公鑰密碼體制。它的安全性是基于求解離散對(duì)數(shù)問題的困難性，是RSA以后比較有希望的一個(gè)公鑰密碼。美國(guó)的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法就是經(jīng)ElGamal算法演變而來。目前DSA算法應(yīng)用也非常廣泛。

公鑰的生成算法

系統(tǒng)提供一個(gè)大素?cái)?shù)p和GF(p)上的本原元素g。對(duì)每一個(gè)用戶A可選擇 XA∈[ 0, 1, 2, ……,p-1] 計(jì)算YA = gXA mod p 其中，XA就是用戶的私鑰，YA就成為用戶的公鑰，將YA公開，XA保密，由A自己掌握。

加密算法

若A欲與B保密通信，設(shè)明文是m，m∈[ 0, 1, 2, ……,p-1]則可按如下步驟進(jìn)行：

（1）A找出B的公鑰YB = gXB?mod p

（2）A任意選隨機(jī)數(shù)t∈[ 0, 1, 2, ……,p-1]，A計(jì)算C1 = (g)t?mod p

（3）A計(jì)算：K = (YB)x mod p (= (gx)XB mod p)，求C2? = ( K*m ) mod p???

（4）A將（C1，C2）作為密文發(fā)送給B

解密算法

B收到密文以后解密方法如下： ??? （1）B用自己的密鑰XB計(jì)算：K = (YB)x mod p = (gx)XB mod p = (C1)XB mod p ??? （2）B計(jì)算：K-1 mod p ???

（3）求m = ( K-1*C2 ) mod p ??舉例說明如下： ??設(shè)p = 11，g = 7，在GF（11）上有70=1，71=7，72=5，73=2，74=3，75=10，76=4，77=6，78=9，79=8，710=1，因此7是GF（11）上的本原元素。 ??設(shè)A的私鑰XA = 3，公鑰YA = 2；B的私鑰XB = 5，公鑰YB = 10，假定A要將信息m = 7發(fā)送給B，A取隨機(jī)數(shù)x = 5，A計(jì)算C1 = g5 mod 11 = 10，K = (YB)5 mod 11 = 10，C2 = K*m mod 11 = 70 mod 11 = 4。 A 將（10，4）作為密文發(fā)送給B，B收到后計(jì)算K = (C1)XB mod p = 105 mod 11 = 10，K-1 = 10（根據(jù)K* K-1 = 1 mod 11），則m = K-1* C2 ?= 40 mod 11 = 7。