一、实验要求与目的
1.复习CCC基本概念，并根据实验平台提供的资料完成验证性实验。
2.编程练习：以书上例题小模数p为例编程实现ECC的基本运算规则。
二、实验内容与步骤记录（只记录关键步骤与结果，可截图，但注意排版与图片大小）
ECC的设计思路
ECC（椭圆曲线密码学）是一种基于椭圆曲线数学的现代加密技术，其设计思路主要围绕椭圆曲线的代数结构和有限域上的运算特性展开。以下是详细的设计思路：
1.椭圆曲线的选择与点的寻找
ECC 的基础是椭圆曲线，通常表示为 y2=x3+ax+b 的形式，其中 a 和 b 是曲线参数。为了在有限域 Fp 上实现 ECC，我们需要选择一个素数 p 作为模数，并在该有限域上找到所有满足椭圆曲线方程的整数点。这些点构成了椭圆曲线上的一个有限群，是 ECC 运算的基础。通过遍历 x 的所有可能值，计算对应的 y 值，并验证其是否为二次剩余，可以准确地找到所有整数点。
2.椭圆曲线上的运算规则设计
在找到椭圆曲线上的所有点之后，需要设计椭圆曲线上的基本运算规则，这些规则是 ECC 的核心。主要包括：
点加法：定义了如何将两个点 P 和 Q 相加，得到一个新的点 R。点加法的计算涉及到斜率的计算和新的坐标公式，需要考虑点是否相同、是否为无穷远点等特殊情况。
点乘法：定义了如何将一个点 P 乘以一个标量 k，即计算 kP。点乘法可以通过重复的点加法实现，通常使用双倍和加算法来提高效率。
点的逆元求解：定义了如何找到一个点 P 的逆元 −P。在椭圆曲线上，点 P=(x,y) 的逆元是 −P=(x,−y)，这在有限域中表示为 (x,p−y)。
3.加密与解密的实现
在主函数中，利用上述运算规则实现 ECC 的加密和解密过程。具体步骤如下：
密钥生成：用户输入一个基点 G（生成元）和一个私钥 d，计算公钥 Q=dG。
加密：用户输入一个随机数 k，计算 C1=kG 和 C2=M+kQ，其中 M 是明文点。
解密：使用私钥 d 恢复明文点 M=C2−dC1。
通过上述设计思路，ECC 能够在较小的密钥长度下提供高强度的安全性，同时保持高效的计算性能。这种设计不仅确保了加密和解密过程的正确性，还通过有限域上的运算特性提供了强大的安全性保障。
实验结果如下：
三、源代码记录（关键代码需备注）
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}")四、实验思考
ECC密码算法的安全性在于什么？
答： ECC（椭圆曲线密码学）的安全性主要基于椭圆曲线离散对数问题的计算困难性。
椭圆曲线离散对数问题（ECDLP）
ECC 的安全性依赖于椭圆曲线离散对数问题的计算难度。具体来说，给定椭圆曲线上的两个点 P 和 Q，其中 Q=kP（k 是一个标量），在已知 P 和 Q 的情况下，计算标量 k 是非常困难的。这种计算困难性使得 ECC 在面对攻击时具有很高的安全性。
计算难度：与传统的离散对数问题（如在有限域中）相比，椭圆曲线上的离散对数问题被认为更加难以解决。目前，已知的最有效的算法（如 Pollard's rho 算法）在计算复杂度上仍然非常高，这使得 ECC 在较小的密钥长度下就能提供与传统加密算法（如 RSA）相当的安全性。
密钥长度优势：由于 ECDLP 的计算难度，ECC 可以使用较短的密钥长度来实现相同的安全级别。例如，一个 256 位的 ECC 密钥可以提供与 3072 位 RSA 密钥相当的安全性。这使得 ECC 在计算资源有限的环境中（如移动设备和物联网设备）具有显著的优势。