在一个循环群$G$上，群元素 $y=a^x$，已知y和a，求x是一个非常困难的事情，但验证x是不是满足该等式却比较简单，这就是一个NP类问题。这个问题被称之为离散对数难题DLP，根据选择的不同的群，有椭圆曲线离散对数难题ECDLP，也有有限域$F_q$上的乘法群对数难题等等。

Alice和Bob是需要进行秘密通信的双方，可以选择一个公开的有限群G，$P\in G$，P和G是公开信息
1、Alice随机选择一个正整数a，并发$P^a$给Bob
2、Bob随机选择一个正整数b，并发$P^b$给Alice
3、Alice和Bob就可以 分别计算出来$P^{ab}$作为他们的秘密通信的共同秘钥
这个算法成立是基于任何攻击者，如果只得到$P^a$ 或者$P^b$，是无法求出来a或b的，也就是基于上文的离散对数难题。

DH秘钥交换的应用场景非常多，在HTTPS/SSL等常见协议中，通信双方就是利用这个机制来交换加密通信所需的秘钥。

ElGamal加密算法是一个基于DH密钥交换的非对称加密算法。它在1985年由塔希尔·盖莫尔提出。GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法。美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演变而来。ElGamal加密算法可以定义在任何循环群G上，它的安全性取决于G上的离散对数难题。其基本原理如下：

Alice和Bob是需要进行秘密通信的双方，可以选择一个公开的循环群G，$g\in G$，g是G的生成元，g和G都是公开信息
1、Alice随机选择一个正整数a，并发$g^a$给Bob
2、Bob随机选择一个正整数b，秘密信息x，并发$g^b，x*(g^a)^b=xg^{ab} $给Alice
3、Alice计算$xg^{ab}/((g^b)^a)$，即可得到解密后的原文x
可以看出这个加密机制，跟上文的DH思想是如出一辙的，通信双方在发送公钥$g^a,g^b$的时候，不需要担心有人可以知道私钥a或b，这一点由DLP来保证
选择不同的循环群，就有不同的Elgamal算法，例如在区块链里常见的基于椭圆曲线 EC Elgamal，基于$F_p$素域的实现等等。

p = 2357
g = 2
priv_a = 88
pub_a = 2priv_a % p
priv_b = 99
pub_b = 2priv_b % p
x = 1234
def DH():
shared1 = pub_a ** priv_b % p
shared2 = pub_b ** priv_a % p
#print(shared1, shared2)
assert(shared1 == shared2)

DH()

def Elgamal_encode(msg, pubk, privk):
return (2privk %p, msg*(pubkprivk) %p)

def Elgamal_decode(msg, pubk, privk):
#根据费马小定理算出pubkprivk的逆元
a = (pubkprivk)**(p-2) %p
return (msg*a %p)

pub, y = Elgamal_encode(x, pub_a, priv_b)
x2 = Elgamal_decode(y, pub, priv_a)
#print(y, x2)
assert(x == x2)