# 零知识证明前传-基于离散对数的加密机制

By [zkware](https://paragraph.com/@zkware) · 2022-09-26

---

离散对数难题
------

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

Diffie-Hellman秘钥交换
------------------

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密码体制
-----------

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=x_g^{ab} $给Alice  
3、Alice计算$x_g^{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)

---

*Originally published on [zkware](https://paragraph.com/@zkware/AndOM6P7b1iN4y4gK1E1)*