Digital-Currency-and-Blockchain-Lab-2

实验目的

  1、实现数字签名算法。

  2、实现加密算法。

实验器材

  1、编译器：Vscode

  2、操作系统：windows10

  3、编程语言：Python 3.10.11

  4、库：ecc-pycrypto

实验原理

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

数字签名算法

问题1

  在TrapGen函数中，首先生成两个大素数p和q，然后计算$n=p*q，td=K$的逆。在Eval函数中，首先计算$y=x^K\%$n，然后返回y。在Invert函数中，首先计算x=$y^td\%n$，然后返回$x$。在$is\_prime$函数中，首先判断n是否小于等于1或者$n$是否为偶数且大于2，如果是则返回False，否则判断$n$是否能被2到sqrt(n)之间的奇数整除，如果能则返回False，否则返回True。在generate_large_prime函数中，首先生成一个10**5到10**6之间的随机数$p$，然后判断$p$是否为素数，如果是则返回p。在main函数中，首先调用generate_large_prime函数生成两个大素数$p$和$q$，然后计算$n=p*q$，然后调用TrapGen函数生成陷门，然后调用Eval函数计算单向函数输出，然后调用Invert函数计算信息，最后判断信息是否等于单向函数输出。

import random


def TrapGen(p, q):  # 生成计算密钥与陷门
    K = p
    td = pow(K, -1, (p - 1) * (q - 1))
    return K, td


def Eval(K, x):  # 利用计算密钥和信息生成单向函数输出
    y = pow(x, K, n)
    return y


def Invert(td, y):  # 根据单向函数输出以及陷门，计算信息
    x = pow(y, td, n)
    return x


def is_prime(n):
    if n <= 1 or (n % 2 == 0 and n > 2):
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True


def generate_large_prime(start, end):
    while True:
        p = random.randrange(start, end)
        if is_prime(p):
            return p


# 生成两个大素数
p = generate_large_prime(10**5, 10**6)
q = generate_large_prime(10**5, 10**6)

n = p * q
m = 4314141445
print("明文为：", m)
K, td = TrapGen(p, q)
print("密钥为：", K, "陷门为：", td)
Y = Eval(K, m)
print("输出密文为：", Y)
X = Invert(td, Y)
print("解密得到的明文为：", X)

问题2

  在createMatrix函数中，首先生成一个rows*cols的矩阵，然后将矩阵中的每个元素都设置为0到2**15-1之间的随机数，最后返回矩阵。在BitInvert函数中，首先遍历0到q之间的每个数x，然后判断$g*x$是否等于$y$，如果是则返回$x$，否则返回0。在Eval函数中，首先计算$y\_=M*x\%q$，然后遍历0到n之间的每个数i，然后计算$y[i]=g*y\_[i]$，最后返回y和$y\_$。在TrapGen函数中，首先计算$td=M$的逆，然后返回$td$。在Invert函数中，首先计算$c\_=td*y\_$，然后遍历0到n之间的每个数$i$，然后遍历0到$n$之间的每个数$j$，然后计算$c[i]=y[j]*td[i*n+j]+c[i]$，最后返回$c$和$c\_$。

import sympy
from random import randint
from ecc.curve import P256

k = 152
q = P256.n
g = P256.G
# n = int(math.log(q / 15)) + 1
n = 7


def createMatrix(rows, cols):
    arr = []
    for i in range(rows):
        col = [randint(0, pow(2, 15) - 1) for _ in range(cols)]
        arr.append(col)
    return sympy.Matrix(arr)


def BitInvert(y):
    for x in range(0, q):
        if g * x == y:
            return x
    return 0


def Eval(M, x_, y):
    y_ = M.multiply(x_) % q
    for i in range(0, n):
        y[i] = g * int(y_[i])
    # print(y,y_)
    return y, y_


def TrapGen(M):
    td = M.inv_mod(q)
    # print(M*td%q)
    return td


def Invert(td, y, y_, c):
    c_ = td.multiply(y_) % q
    for i in range(0, n):
        for j in range(0, n):
            c[i] = y[j] * td[i * n + j] + c[i]
        # c[i]=g* int(c_[i])
        # print(c[i],g* int(c_[i]))
    # print(c)
    return c_, c


# M = createMatrix(n, n)
M = sympy.Matrix(
    [
        [20263, 29624, 7140, 25192, 29950, 27715, 15590],
        [1868, 15776, 19457, 2504, 422, 29323, 21231],
        [21599, 6717, 7771, 31738, 3894, 3913, 15075],
        [772, 7756, 9507, 10095, 11506, 20200, 2480],
        [426, 22745, 21254, 19868, 24297, 28397, 204],
        [19932, 705, 14881, 26242, 14933, 17205, 22213],
        [28822, 12266, 9567, 10557, 22165, 41, 8349],
    ]
)
if __name__ == "__main__":
    x_ = sympy.Matrix([randint(0, pow(2, 15) - 1) for _ in range(int(n))])
    y = [g for _ in range(int(n))]
    c = [g - g for _ in range(int(n))]
    g_ = [g for _ in range(int(n))]

    Y = g * k
    X = BitInvert(Y)
    print("离散对数为：", X)
    y, y_ = Eval(M, x_, y)
    print("单项陷门函数的输出为：", y)
    td = TrapGen(M)
    for i in range(0, n):
        g_[i] = g * int(x_[i])
    # print(y)
    x1, x = Invert(td, y, y_, c)

    # print(x_ % q)
    # print(x1 % q)
    # print((x1 - x_) % q)

    print("g^x为：", g_)
    print("验证获得的数为：", x)
    print("验证结果", x == g_)

问题3

  问题3在问题2代码的基础上，增加了签名和验证的功能。签名时首先调用 Eval函数计算单向函数输出，然后调用 TrapGen函数生成陷门，最后返回单向函数输出。验证时首先调用 TrapGen函数生成陷门，然后调用 Invert函数计算信息，最后判断信息是否等于单向函数输出。

import Q2
import sympy
from random import randint


def encode_DDT(x_, y):
    y, y_ = Q2.Eval(Q2.M, x_, y)
    return y, y_


def decode_DDT(y, y_):
    td = Q2.TrapGen(Q2.M)
    x1, x = Q2.Invert(td, y, y_, c)
    return x1, x


if __name__ == "__main__":
    x_ = sympy.Matrix([randint(0, pow(2, 15) - 1) for _ in range(int(Q2.n))])
    y = [Q2.g for _ in range(int(Q2.n))]
    c = [Q2.g - Q2.g for _ in range(int(Q2.n))]
    g_ = [Q2.g for _ in range(int(Q2.n))]

    for i in range(0, Q2.n):
        g_[i] = Q2.g * x_[i]
    print("明文为：", x_)
    print("陷门为：", Q2.M)
    print("g^x_： ", g_)

    y, y_ = encode_DDT(x_, y)
    print("签名：", y)

    x1, x = decode_DDT(y, y_)
    print("验证：", x)

    print("验证结果：", x == g_)

加密算法

问题4

  在KGen函数中，首先生成一个随机数k，然后计算$pk=g*k$，$sk=k$。在Enc函数中，首先计算$c1=g*k$，然后计算$c2=m*pk$，最后返回$c1$和$c2$。在Dec函数中，首先计算$m=c2*sk$的逆，然后计算$m=c1*m$，最后返回m。

from ecc.key import gen_keypair
from ecc.curve import P256, Point
from ecc.cipher import ElGamal


def KGen():
    sk, pk = gen_keypair(P256)
    return pk, sk


def Enc(pk, m):
    cipher_elg = ElGamal(P256)
    c1, c2 = cipher_elg.encrypt(m, pk)
    # print(c1,c2)
    return c1, c2


def Dec(sk, ct):
    cipher_elg = ElGamal(P256)
    m = cipher_elg.decrypt(sk, ct[0], ct[1])
    return m


if __name__ == "__main__":
    pk, sk = KGen()
    # print(pk,sk)

    m = "hello world!".encode("utf-8")
    print("明文为", m)
    ct = Enc(pk, m)
    print("公钥和私钥分别为：", ct)
    m = Dec(sk, ct)
    print("解密获得的明文为：", m)

问题5

  在Prove函数中，首先生成一个随机数k，然后计算$f\_=g*k$，$g\_=g*(a-b)$，$z=s+r*k$，最后返回$f\_,g\_,z$。在Verif函数中，首先判断$g*z$是否等于$g*s+f\_$，然后判断$g*z$是否等于$g*s+g\_$，如果两个条件都满足，则返回True，否则返回False。

from ecc.curve import P256
from random import randint

g = P256.G


def Prove(s, a, b):
    k = randint(1, P256.p)
    f_ = g * k
    # print(f_)
    g_ = g * (a - b)
    # print(g_)
    z = s + r * k
    return f_, g_, z


def Verif(f_, g_, z, s):
    if g * z == g * s + f_ and g * z == g * s + g_:
        return True
    else:
        return False


def encrypt(v, r, m):
    return g * v, g * r, g * (v + r) * m


if __name__ == "__main__":
    r = randint(0, P256.n - 1)
    m = 5415453
    a = randint(0, P256.n - 1)
    b = randint(0, P256.n - 1)
    ct_1 = encrypt(a, r, m)
    ct_2 = encrypt(b, r, m)
    # print(ct_1)
    # print(ct_2)

    F = g * r
    # print(F)
    G = g * (a - b)
    # print(G)

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