Python实现椭圆曲线基础运算

代码

def extGCD(a, b):
    if b == 0:
        return 1, 0, a
    x, y, q = extGCD(b, a % b)
    x, y = y, (x - (a // b) * y)
    return x, y, q

def modReverse(a, p):
    x, y, q = extGCD(a, p)
    if q != 1:
        raise Exception("No solution.")
    else:
        return (x + p) % p

class EllipticPoint:
    def __init__(self, curve: "EllipticCurve", x: int, y: int):
        self.curve = curve
        self.x = x % self.curve.mod
        self.y = y % self.curve.mod

    def __rmul__(self, other: int) -> "EllipticPoint":
        if not isinstance(other, int):
            raise Exception("只支持左乘整数")

        temp = self
        res = None
        while other:

            if other % 2:
                if not res:
                    res = temp
                else:
                    res += temp

            temp += temp
            other //= 2

        return res

    def __add__(self, other: "EllipticPoint") -> "EllipticPoint":
        if not isinstance(other, EllipticPoint):
            raise Exception("只支持两点相加")

        if not self.curve == other.curve:
            raise Exception("不是同一个椭圆曲线")

        if self == other:
            lam = (3 * self.x ** 2 + self.curve.a) * modReverse((2 * self.y), self.curve.mod)
            x = lam ** 2 - 2 * self.x
            y = lam * (self.x - x) - self.y
        else:
            lam = (self.y - other.y) * modReverse((self.x - other.x), self.curve.mod)
            x = lam ** 2 - self.x - other.x
            y = lam * (self.x - x) - self.y

        return self.__class__(self.curve, x, y)

    def __sub__(self, other: "EllipticPoint") -> "EllipticPoint":
        if not isinstance(other, EllipticPoint):
            raise Exception("只支持点减点")

        return self + self.__class__(other.curve, other.x, -other.y)

    def __neg__(self) -> "EllipticPoint":
        return self.__class__(self.curve, self.x, -self.y)

    def __eq__(self, other: "EllipticPoint"):
        return self.x == other.x and self.y == other.y

    def __str__(self):
        return f"({self.x}, {self.y})"

    __repr__ = __str__

class EllipticCurve:
    def __init__(self, mod: int, a: int, b: int):
        self.mod = mod
        self.a = a
        self.b = b

    def __call__(self, x: int, y: int) -> EllipticPoint:
        if (y ** 2 - x ** 3 - self.a * x - self.b) % self.mod:
            raise Exception(f"({x}, {y})不在曲线上!")
        return EllipticPoint(self, x, y)

    def __eq__(self, other: "EllipticCurve"):
        return self.mod == other.mod and self.a == other.a and self.b == other.b

举例

利用椭圆曲线实现ElGamal密码体制，设椭圆曲线是E_{11}(1,6)，生成元G=(2,7)，接收方A的秘密钥n_A=7。
(1) 求A的公开钥P_A
(2) 发送方B欲发送消息P_m=(10,9)，选择随机数k=3，求密文C_m。
(3) 显示接收方A从密文C_m恢复消息P_m的过程。

# 初始化
e = EllipticCurve(11, 1, 6) # 椭圆曲线
G = e(2, 7) # 生成元
na = 7 # 密钥

# 计算公钥P_A=n_AG
Pa = na * G
print("公钥: %s" % Pa)

# 求密文C_m=\{C_1,C_2\}=\{kG,P_m+kP_A\}
Pm = e(10, 9) # 明文
k = 3
C1 = k * G
C2 = Pm + k * Pa
print("密文: {%s, %s}" % (C1, C2))

# 求明文P_m=C_2-n_AC1
print("明文: %s" % (C2 - na * C1))

```输出
公钥: (7, 2)
密文: {(8, 3), (10, 2)}
明文: (10, 9)
```