故事讲完了，相信大家对零知识证明有了一个大概的印象。零知识证明的本质就是在不揭晓我所知道或拥有的某样东西的前提下，向别人证明我有很大几率（这点很重要，零知识证明说到底是一个概率上的证明）确实知道或拥有这个东西。

科学上网观看零知识证明相关的视频：

对于evaluation_1.pdf的理解（基于零知识证明设计的数字签名方案）

签名者的Public Key是公开的，格式如下：

$$(g,\ \ p, \ \ g^x \bmod p)$$

其中$x$是签名者独有的秘密，$p$是一个大素数

签名者将消息签名后以如下方式发出

$$c = \text{hash_function}(m^x\bmod p, \ \ m^r\bmod p,\ \ g^r\bmod p)$$

$$s=cx+r$$

$m$是消息明文$M$的哈希值，上面的$s, c, m^x, m^r, g^r$以及$\text{hash_function()}$的实现都是公开的，而$r$是发送者每次选择的一个random number

为了向 verifier证明消息的确是由签名者本人发出的，

verifier需要检验上图中(1)(2)两个等式是否成立，成立即可证明，原理是什么呢？

• Case 1：攻击者不知道$x$，他可以自己随机出一个$r$，自己计算出$(g^x)^c \cdot g^r$，但由于计算大数的离散对数是个困难问题，他无法解出$s$，也就无法对消息进行伪造签名
• Case 2：攻击者使用上次的消息的中的$c，s$，当然verifier可以检验并承认(1)式正确，从而证明这是源于签名者本人的$c, s$，但$c$通过哈希函数与$m^x, m^r, g^r$是几乎一一对应的映射，攻击者没法更换消息内容，也就无法对其它消息签名

总而言之，验证(1)(2)两个等式相当于验证了两遍 $s=cx + r$ 这个等式，第1次验证就证明了签名者的确知道这个$x$，通过哈希函数与每一次的消息相关联，第2次验证证明了两点：1.签名这条消息的$x$与等式(1)的$x$是同一个2.签名消息的$s, c$的确是根据该消息生成的，不是源于以前的消息，该方案的安全性源于计算大整数的离散对数是件很困的事情

**消息发送者在别人不知道私钥$x$的情况下让别人有充分理由相信他的确拥有$x$，并且相信签名对消息是对应、有效的，从而实现了数字签名
**

还是理解了很久，理解凭什么别人不能伪造签名，自己假设了下各种可能的欺骗方法，发现这个方案还是很严密、无懈可击的

• Code:
• 代码中的变量命名与上文理解中的变量名基本一致
• 代码实现的算法完全依照上文（不想费脑子读std，而且std运行错误？？，自己写靠谱点
• 代码中有详细注释

#Author: LRL52,  Date: 2021.10.29
#A digital signature scheme based on zero-knowledge proof and the hardness of DLP
from Crypto.Util.number import *
import mmh3

class Message: #M代表明文，后5个参数与签名相关
    M = ""
    c, m_x, m_r, g_r, s= 0, 0, 0, 0, 0

class Public_Key: #签名公钥，公开
    g, p, g_x = 0, 0, 0

class Zero_Knowledge_signature: #A digital signature scheme based on zero-knowledge proof and the hardness of DLP
    def __init__(self):
        self.Bit, self.x = 256, 0 #Bit是p的二进制长度，可修改
        self.public_key = Public_Key()
    def ksm(self, a, b, p): #快速幂算法
        ret = 1
        while b > 0:
            if b & 1: ret = ret * a % p
            a = a * a % p
            b >>= 1
        return ret
    def gen_key(self): #生成公钥, but x is secretive
        self.public_key.p = getPrime(self.Bit)
        self.public_key.g, self.x = getPrime(self.Bit // 2), getPrime(self.Bit // 2)
        self.public_key.g_x = self.ksm(self.public_key.g, self.x, self.public_key.p)
    def hash_function(self, x, y, z): #哈希函数
        x = mmh3.hash128(str(x), 666, signed=False)
        y = mmh3.hash128(str(y), 886, signed=False)
        z = mmh3.hash128(str(z), 233, signed=False)
        return x ^ y ^ z
    def signature(self, message): #为消息添加数字签名
        m = mmh3.hash128(message.M, 1314520, signed=False) #the message M is hashed to a value m
        r = getPrime(self.Bit // 2)
        message.m_x = self.ksm(m, self.x, self.public_key.p)
        message.m_r = self.ksm(m, r, self.public_key.p)
        message.g_r = self.ksm(self.public_key.g, r, self.public_key.p)
        message.c   = self.hash_function(message.m_x, message.m_r, message.g_r)
        message.s   = message.c * self.x + r # s = cx + r
    def check_signature(self, message, public_key): #check g^s == (g^x)^c * g^r and m^s == (m^x)^c * m^r
        p, m = public_key.p, mmh3.hash128(message.M, 1314520, signed=False)
        return self.ksm(public_key.g, message.s, p) == self.ksm(public_key.g_x, message.c, p) \
    * message.g_r % p and \
    self.ksm(m, message.s, p) == self.ksm(message.m_x, message.c, p) \
    * message.m_r % p


Alice = Zero_Knowledge_signature()
Alice.gen_key() #模拟Alice生成公钥并公开
print("Alice's public key = ({0}, {1}, {2})".format(Alice.public_key.g, Alice.public_key.p, Alice.public_key.g_x))
#模拟消息签名
message = Message()
message.M = "I hope to become a member of LingRui Studio."
Alice.signature(message)
print("message's basic information:")
print("M = '{}'".format(message.M))
print("m^x, m^r, g^r = {0}, {1}, {2}".format(message.m_x, message.m_r, message.g_r))
print("s, c = {0}, {1}".format(message.s, message.c))
#模拟第三方验证签名
Third_party = Zero_Knowledge_signature()
if Third_party.check_signature(message, Alice.public_key): #第三方能够知道Alice的公钥
    print("Signatrue is correct.")
else:
    print("Fake signatrue!")
#模拟用Bob的公钥验证签名，当然是不行的啦
Bob = Zero_Knowledge_signature()
Bob.gen_key()
if Third_party.check_signature(message, Bob.public_key):
    print("Signatrue is correct.")
else:
    print("Fake signatrue!")

• $\text{Output:}$

  Alice's public key = (249542897606673154489572114688846449773, 113676461334611132208836922659255894837249301332230332082471137689296790884751, 18850054335198025000289655344153439843833476203275386342201941568269810786989)
  message's basic information:
  M = 'I hope to become a member of LingRui Studio.'
  m^x, m^r, g^r = 29193128899395479134554700706506177551512734507233199731810854219962781438850, 37281303509806531793443835178450196263720377360896046628236011080102705631090, 92021597613870516427940561278154250359391450760119520019758532891077731712354
  s, c = 7903883530712082623194255323490948647806586389837157269943722969554874821557, 30598803345319416029712852041923689484
  Signatrue is correct.
  Fake signatrue!

测试截图：

写在最后：

• 本文由$\color{Red}\text{21-信软-LRL52原创撰写}$
• 题目推荐的文章看得还比较少，目前事情很多，一堆网课作业和某些工作室的招新截止日期都在10.31左右，以后有时间再学习吧
• 了解了零知识证明后让我想起 我们班有漂亮妹妹在空间发说说表示自己脱单了，让班上大受震撼，实际上是故意发的假消息，但ta成功运用零知识证明骗过了大部分人，因为ta在不让别人知道ta的npy是谁的情况下让很多人相信了这件事!!!∑(ﾟДﾟノ)ノ，原谅我对零知识证明的误解
• 写于$2021.10.29$日早