Digital-Currency-and-Blockchain-Lab-1

发表于 更新于 分类于

实验目的

  1、仔细阅读 curve.py 的源代码

  2、理解每个函数之间的关系

  3、熟悉椭圆曲线上的运算操作。

实验器材

  1、编译器：Vscode

  2、操作系统：windows10

  3、编程语言：Python 3.10.11

  4、库：ecc-pycrypto

实验原理

  本次实验基于 Python 以及 ecc-pycrypto 库来实现。其中我们将使用ecc-pycrypto 库中的 P256 椭圆曲线的一个简单实现。

哈希函数

问题1

  在Setup函数中gg表示P256的生成元，kk为随机数，计算得到hh，则K=(g,h)K=(g,h)即为生成的公钥对。而在Hash(G,H,M)中，利用离散对数构造Hash函数c=gm+hrc=g^m+h^r即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from ecc.curve import P256
import random


r = random.randint(1, P256.n)


def Setup():
    k = random.randint(1, P256.n)
    g = P256.G
    h = g * k
    return g, h


def Hash(G, H, M):
    h_0 = G * M + H * r
    return h_0


m = 51631313547153435441543815468315648351471524
6813546839164381543154687315413536418136456941835
g, h = Setup()
h_0 = Hash(g, h, m)

print("r = ", r)
print("g = ", g)
print("h = ", h_0)
print("Hash(K, M) = ", h_0.x)

问题2

  对SetupInsecure函数不仅产生哈希函数的密钥K，也输出离散对数k=logg(h)k=log_g(h)，在FindCol函数中利用X2+r2∗k=X1+r1∗kX_2+r_2*k=X_1+r_1*k找到一组哈希函数的碰撞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from ecc.curve import P256
import random

r_1 = random.randint(1, P256.n)
r_2 = random.randint(1, P256.n)


def SetupInsecure():
    k = random.randint(1, P256.n)
    g = P256.G
    h = g * k
    return g, h, k


def FindCol(G, H, K):
    X_1 = 416513513415135313314146874688647846876487
    4686487468469831483619865466849646815468175647815
    X_2 = r_1 * K + X_1 - r_2 * K
    return X_1, X_2


def Hash(G, H, M, r):
    h = G * M + H * r
    return h


g, h, k = SetupInsecure()
x_1, x_2 = FindCol(g, h, k)
h_1 = Hash(g, h, x_1, r_1)
h_2 = Hash(g, h, x_2, r_2)
print("x_1 = ", x_1)
print("x_2 = ", x_2)
print("r_1 = ", r_1)
print("r_2 = ", r_2)
print("g = ", g)
print("h = ", h)
print("k = ", k)
print("Hash(K, M) = ", h_1.x)
print("Hash(H, M) = ", h_2.x)


if h_1 == h_2:
    print("True")
else:
    print("False")

零知识证明

问题3

  在Prove函数中，首先计算R=grR=g^r，然后计算z=x∗h+rz=x*h+r，最后返回R,h,zR,h,z。在Verif函数中，首先计算gzg^z和fh∗Rf^h*R，然后判断两者是否相等，若相等则返回True，否则返回False。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import hashlib
import random


p = 15161
g = 3
x = 101


def Prove():
    R = pow(g, r)
    # print(R)
    h = random.randint(1, p)  # hash函数太长了算不完，用randint替代一下
    # h=int(hashlib.md5(h).hexdigest(),16)
    # print(h)
    z = x * h + r
    return R, h, z


f = pow(g, x)
# print(f)


def Verif(z, h):
    if (pow(g, z) - pow(f, h) * R) % p != 0:
        return True
    else:
        return False


for i in range(1, 100):
    r = random.randint(1, p)
    # print(r)
    R, h, z = Prove()
    if Verif(z, h):
        print("证明失败")
        break
print("证明成功")

问题4

  假设Alice为证明者，拥有rr，Bob为验证者。Alice想要证明G=(f,g,F=fr,G=gr)G=(f,g,F=f^r,G=g^r)
是一个DDH关系，但不能透露关于r的任意消息，Bob想要验证Alice的证明。Alice和Bob
之间的交互如下：

  1、Alice随机生成一个随机数kk，并将f′=fk{f}'=f^k和g′=gk{g}'=g^k发送给Bob。

  2、Bob向Alice发送一个随机数ss。

  3、Alice计算z=s+rkz=s+rk，并将zz发送给Bob。

  4、Bob验证fz=fs+F∗f′f^z=f^s+F*{f}'和gz=gs+G∗g′g^z=g^s+G*{g}'。

  5、重复上述过程。

  如果G=(f,g,F,G)G=(f,g,F,G)不存在DDH关系，那么假设F=fr1,G=gr2F=f^{r_1},G=g^{r_2}，Alice想要通过验证，就需要让f′{f}'和g′{g}'同时对两个不同的s1s_1和s2s_2都能应答z11,z12,z21,z22z_11,z_12,z_21,z_22，那么r=z11−z12s1−s2=z21−z22s1−s2r=\frac{z_{11}-z_{12}}{s_1-s_2}=\frac{z_{21}-z_{22}}{s_1-s_2}，由于s1,s2s_1,s_2都是Bob随机选取的，于是Alice就需要以猜测穷举离散对数的空间复杂度获得满足条件的ss。因此，如果Alice能够通过验证，那么GG一定是一个DDH关系。

问题5

  在Prove函数中，首先计算f′=fk1,g′=gk2f'=f^{k_1},g'=g^{k_2}，然后计算z1=s+rk1,z2=s+rk2z_1=s+rk_1,z_2=s+rk_2，最后返回f′,g′,z1,z2f',g',z_1,z_2。在Verif函数中，首先计算fz1f^{z_1}和fs+F∗f′f^s+F*f'，然后计算gz2g^{z_2}和gs+G∗g′g^s+G*g'，最后判断两者是否相等，若相等则返回True，否则返回False。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import random

p = 15161
f = 3
g = 5
r = 101


def Prove(s):
    k_1 = random.randint(1, p)
    # print(k_1)
    k_2 = random.randint(1, p)
    # print(k_2)
    f_ = pow(f, k_1)
    # print(f_)
    g_ = pow(g, k_2)
    z_1 = s + r * k_1
    z_2 = s + r * k_2
    return f_, g_, z_1, z_2


F = pow(f, r)
# print(F)
G = pow(g, r)
# print(G)


def Verif(f_, g_, z_1, z_2, s):
    if (pow(f, z_1) - pow(f, s) * f_) % p == 0 and (
        pow(g, z_2) - pow(g, s) * g_
    ) % p == 0:
        return True
    else:
        return False


for i in range(1, 100):
    s = random.randint(1, p)
    # print(s)
    f_, g_, z_1, z_2 = Prove(s)
    if Verif(f_, g_, z_1, z_2, s):
        print("证明失败")
        break
print("证明成功")