【应用暗码学】实行五公钥暗码2——ECC - qidao123.com技术社区-IT企服评测·应用市场

def findsolution(p, a, b):
"""找到椭圆曲线 y^2 = x^3 + ax + b 在有限域 F_p 上的所有点"""
s = []
cnt = 0
for i in range(p):
z = (i**3 + a * i + b) % p
if pow(z, (p - 1) // 2, p) == 1:
y1 = pow(z, (p + 1) // 4, p)
s.append((i, y1))
cnt += 1
y2 = p - y1
if y1 != y2:
s.append((i, y2))
cnt += 1
s.append((0, 0)) # 添加无穷远点
cnt += 1
s.sort()
return s, cnt
def point_addition(p, a, P, Q):
"""椭圆曲线上的点加法"""
if P == (0, 0):
return Q
if Q == (0, 0):
return P
if P == Q:
if P[1] == 0:
return (0, 0) # 无穷远点
numerator = (3 * P[0]**2 + a) % p
denominator = (2 * P[1]) % p
else:
if P[0] == Q[0] and P[1] != Q[1]:
return (0, 0) # 无穷远点
numerator = (Q[1] - P[1]) % p
denominator = (Q[0] - P[0]) % p
# 计算斜率 lambda
lambda_ = (numerator * pow(denominator, p - 2, p)) % p
# 计算新的点
x3 = (lambda_**2 - P[0] - Q[0]) % p
y3 = (lambda_ * (P[0] - x3) - P[1]) % p
return (x3, y3)
def point_negation(p, P):
"""计算点的逆点"""
return (P[0], p - P[1])
def point_multiplication(p, a, P, k):
"""椭圆曲线上的点乘法"""
result = (0, 0)
temp = P
while k > 0:
if k % 2 == 1:
result = point_addition(p, a, result, temp)
temp = point_addition(p, a, temp, temp)
k //= 2
return result
# 输入参数
p = int(input("请输入模数p："))
a = int(input("请输入椭圆曲线的参数a："))
b = int(input("请输入椭圆曲线的参数b："))
# 找到椭圆曲线上的所有点
points, point_count = findsolution(p, a, b)
print(f"椭圆曲线上的点：{points}")
print(f"点的总数：{point_count}")
# 输入生成元G和私钥d
generator = tuple(map(int, input("请输入生成元G(x,y) 中间需要英文逗号隔开x和y：").strip("()").split(",")))
private_key = int(input("请输入私钥d："))
# 验证生成元是否在椭圆曲线上
if generator not in points:
raise ValueError("输入的生成元G不在椭圆曲线上！")
# 生成公钥
public_key = point_multiplication(p, a, generator, private_key)
print(f"公钥Q = dG = {public_key}")
# 加密
plaintext_point = tuple(map(int, input("请输入明文点M(x,y) 中间需要英文逗号隔开x和y：").strip("()").split(",")))
k = int(input("请输入随机数k：")) # 用于加密过程
# 计算C1 = kG
C1 = point_multiplication(p, a, generator, k)
# 计算C2 = M + k * d * G
C2 = point_addition(p, a, plaintext_point, point_multiplication(p, a, generator, k * private_key))
print(f"加密后的密文：C1 = {C1}, C2 = {C2}")
# 解密
# 计算M = C2 - k * d * G
decrypted_point = point_addition(p, a, C2, point_negation(p, point_multiplication(p, a, C1, private_key)))
print(f"解密后的明文点：{decrypted_point}")

复制代码