椭圆曲线上的ElGamal密码系统

算法简介

• 椭圆曲线：Ep(a,b): 即y^2 = x^3 + a + b mod p
• 参数选择：生成元G(x, y)，随机整数k (0 =< k < N)，其中N为素数域的阶。
• 产生密钥：公钥Pa=Pb*G， 私钥Pb为一个小于p的非负随机整数。
• 加密运算：e(M, k) = (kG, M+kPa) = (C1, C2)
• 解密运算：d(C1, C2) = C2 - PbC1 = C2 + Pb(-C1)
• 注意：若C = (x, y)，则有-C = (x, p-y)

代码实现

# -*-coding:utf-8-*-
"""
File Name: 椭圆曲线上的ElGamal密码系统.py

Program IDE: PyCharm

Create Time: 2021-09-16 16:55

Create By Author: 陆依依

"""

# 椭圆曲线：Ep(a,b):  即y^2 = x^3 + a + b mod p
# 生成元G(x, y)，随机数k，明文M(m1, m2)  公钥Pa， 私钥Pb，
# 加密运算：e(m, k) = (kG, m+kPa) = (C1, C2)
# 解密运算：d(C1, C2) = C2 - Pb*C1



def Init():
    a = int(input("a="))
    b = int(input("b="))
    p = int(input("p="))
    x = int(input("生成元坐标x="))
    y = int(input("生成元坐标y="))
    k = int(input("随机数k="))
    Pb = int(input("私钥随机数Pb="))
    m1 = int(input("明文坐标m1="))
    m2 = int(input("明文坐标m2="))
    G = [x, y]
    M = [m1, m2]
    return a, b, p, G, k, Pb, M


# 求分数的模p同余   a/x mod p
def ModP(a, x, p):
    # 统一x为正数
    if x < 0:
        x = -x
        a = -a

    # 统一a为非负数
    while a < 0:
        a += p

    a = a % p

    i = 0
    while True:
        if (i*x) % p == a:
            return i*x
        i = i + 1


# 相加
def Add(point1, point2, a, p):
    if point1[0] == point2[0] and point1[1] == point2[1]:
        k = ModP(3*point1[0]**2 + a, 2*point1[1], p) / abs(2*point1[1])
    else:
        k = ModP(point2[1]-point1[1], point2[0]-point1[0], p) / abs(point2[0]-point1[0])
    x = ModP(k**2-point1[0]-point2[0], 1, p)
    y = ModP(k*(point1[0]-x)-point1[1], 1, p)
    return [x, y]


# 点乘k*point， 快速幂思想
def Quick(point, a, p, k):
    flag = []
    while k!=0 :
        flag.append(k%2)
        k = int(k / 2)
    temp = point
    if flag[0] == 1:
        ans = point
    else:
        ans = [-1, -1]

    for i in range(1, len(flag)):
        temp = Add(temp, temp, a, p)
        if flag[i] == 1:
            if ans[0] == -1:
                ans = temp
            else:
                ans = Add(ans, temp, a, p)
    return ans


# 加密
def Encrypy(k, G, M, Pa, a, p):
    return [Quick(G, a, p, k), Add(M, Quick(Pa, a, p, k), a, p)]


# 解密
def Decrypt(C, Pb, a, p):
    C[0][1] = p - C[0][1]
    return Add(C[1], Quick(C[0], a, p, Pb), a, p)


if __name__ == "__main__":
    # 初始化参数
    a, b, p, G, k, Pb, M = Init()

    # 计算公钥
    Pa = Quick(G, a, p, Pb)

    # 加密
    C = Encrypy(k, G, M, Pa, a, p)
    print("密文对为：C1=" + str(C[0]) + ", C2=" + str(C[1]))

    # 解密
    M1 = Decrypt(C, Pb, a, p)
    print("恢复后的明文为M1=" + str(M1))

测试数据

    # 测试数据：密文对{(8, 3), (10, 2)}
    # 1
    # 6
    # 11
    # 2
    # 7
    # 3
    # 7
    # 10
    # 9

运行结果