密码学的简单实现：求椭圆曲线上的点 | 平方剩余的点 | ECC加密解密 的python实现_椭圆曲线平方剩余

有代码注释以及运行时的过程注释，有助于理解，可自行删除

代码如下

from fractions import Fraction
 
 
# 求x模y, 防止负数
def QiuMo(x, y):
    while x < 0:
        x += y
    return x % y
 
 
# 欧几里得算法
def Exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = Exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q
 
 
# 求逆元，防止负数
def Inf(a, p):
    x, y, q = Exgcd(a, p)
    if q != 1:
        raise Exception("No solution.")
    else:
        return (x + p) % p  # 防止负数
 
 
# 椭圆方程，需要初始化参数a，b，p
class Equation:
    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p
        self.pfx = int((p - 1) / 2)
        self.pfy = int((p + 1) / 4)
        print(f"z=x^3+{a}x+{b}, p={p}, (p-1)/2={self.pfx}, (p+1)/2={self.pfy}")
 
    # 求在椭圆上的平方剩余的点
    def EquationResult(self, x):
        z = int(pow(x, 3) + self.a * x + self.b)
        z2 = z % self.p
        result = 1
        for i in range(self.pfx):
            result *= QiuMo(z2, self.p)
            result = QiuMo(result, self.p)
        result = int(QiuMo(result, self.p))
        r_string = f"x={x}时, z = {z}, z^(p-1)/2 mod p = {result}"
        if result == 1:
            y1 = int(QiuMo(pow(z, self.pfy), self.p))
            y2 = self.p - y1
            r_string += f" 是平方剩余, 点为({x},{y1})和({x},{y2})"
        else:
            r_string += " 不是平方剩余"
        return r_string
 
    # 计算椭圆曲线上的P + Q, 可传入提示信息
    def GetR_FromPQ(self, P, Q, string):
        print(f"{string}:\tP={P}, Q={Q}")
        s = "过程:"
        x1, y1 = P
        x2, y2 = Q
        if P == Q:
            l = Fraction(3 * x1 * x1 + self.a, 2 * y1)
            s += f"l={l}"
        else:
            assert x1 != x2, f"输入出错，过程出错：string={string},P={P},Q={Q},x1==x2，除数为零！"
            l = Fraction(y2 - y1, x2 - x1)
            s += f"l={l}"
        l_final = QiuMo(l.numerator * Inf(l.denominator, self.p), self.p)
        s += f"\tl_final={l_final}"
        x3 = QiuMo(int(-x1 - x2 + l_final * l_final), self.p)
        y3 = QiuMo(int(-y1 + l_final * (x1 - x3)), self.p)
        s += f"\tGF:{(x3, y3)}"
        print(s)
        return x3, y3
 
    # 计算椭圆曲线上的nG, 可传入提示信息
    def GetNG(self, n, G, string):
        nG = G
        for i in range(n - 1):
            nG = self.GetR_FromPQ(nG, G, string)
        return nG
 
    # 求逆元-G
    def getNi(self, G):
        x, y = G
        return x, -y
 
    # ECC加密，传入生成元G、私钥d，k，以及明文M，打印过程
    def ECCEncode(self, G, d, k, M):
        Y = self.GetNG(d, G, "正在计算Y=(d或x)G")
        c1 = self.GetNG(k, G, "正在计算c1=kG")
        kY = self.GetNG(k, Y, "正在计算kY")
 
        c2 = self.GetR_FromPQ(M, kY, "正在计算c2=M+kY")
        c = (c1, c2)
        return c
 
    # ECC解密，传入c2，c1，x，返回明文M
    def ECCDecode(self, c1, c2, x):
        return self.GetR_FromPQ(c2, self.getNi(self.GetNG(x, c1, f'求xc1:x={x},c1={c1}')), "ECC解密")
 
 
if __name__ == '__main__':
    a, b, p = 1, 6, 11
    equation = Equation(a, b, p)
    print("正在进行求平方剩余的点")
    # 举例求平方剩余的点
    for i in range(p):
        print(equation.EquationResult(i))
    # 举例ECC加密
    print("正在进行ECC加密")
    G = (2, 7)
    d = 7
    k = 6
    M = (9, 1)
    # 加密
    C = equation.ECCEncode(G, d, k, M)
    c1, c2 = C
    # 解密
    M2 = equation.ECCDecode(c1, c2, d)
    print(f'\n对于G={G},d={d},k={k},M={M}')
    print(f"ECC加密结果:{C}")
    print(f"ECC解密结果:{M2}")

运行结果如图：