文章总结： 本文档详细解析了一道CTF椭圆曲线密码学题目，阐述了ECC原理、点运算及倍加-相加算法。文章提供了Python实现模逆、点加和标量乘法的完整代码，演示了如何利用私钥计算公钥并获取Flag。此外，还总结了ECC的技术优势、安全威胁及实际应用场景，是一份兼具理论与实践的密码学解题教程。 综合评分： 91 文章分类： CTF,网络安全,安全培训
CTF密码学实战：椭圆曲线加密（ECC）原理与解题
原创
破镜安全 破镜安全
破镜安全
2026年1月25日 08:01 四川
CTF密码学实战：椭圆曲线加密（ECC）原理与解题
题目背景
这是一道经典的椭圆曲线密码学题目。题目给出了一组椭圆曲线参数和私钥，要求计算对应的公钥，并将公钥的两个坐标值相加得到flag。
题目文件内容：
已知椭圆曲线加密Ep(a,b)参数为
p = 15424654874903
a = 16546484
b = 4548674875
G(6478678675, 5636379357093)
私钥为
k = 546768
求公钥K(x,y)
椭圆曲线密码学基础
什么是椭圆曲线
椭圆曲线并不是椭圆，而是一种满足特定方程的曲线。在密码学中，我们使用的椭圆曲线方程为：
y² = x³ + ax + b (mod p)
这个方程定义在有限域上，所有运算都在模p的意义下进行。其中：
- p：一个大素数，定义了有限域的范围
- a, b：椭圆曲线的参数，需满足 4a³ + 27b² ≠ 0
- x, y：曲线上点的坐标
在本题中，椭圆曲线方程为：
y² ≡ x³ + 16546484x + 4548674875 (mod 15424654874903)
椭圆曲线上的点运算
椭圆曲线密码学的核心是定义在曲线上的”点加法”运算。这种运算具有以下性质：
- 封闭性：两个曲线上的点相加，结果仍在曲线上
- 结合律：(P + Q) + R = P + (Q + R)
- 单位元：存在无穷远点O，满足 P + O = P
- 逆元：对于点P(x,y)，存在-P(x,-y)，满足 P + (-P) = O
点加法的几何意义
在实数域上，点加法有直观的几何解释：
- 过P和Q两点作直线
- 该直线与曲线相交于第三点R’
- 将R’关于x轴对称，得到R = P + Q
在有限域上，虽然失去了几何直观性，但代数运算规则保持不变。
点加法的计算公式
给定椭圆曲线上两个不同的点 P(x₁, y₁) 和 Q(x₂, y₂)，计算 R = P + Q：
情况1：P ≠ Q（普通点加法）
m = (y₂ - y₁) / (x₂ - x₁) mod p
x₃ = m² - x₁ - x₂ mod p
y₃ = m(x₁ - x₃) - y₁ mod p
情况2：P = Q（点倍加）
m = (3x₁² + a) / (2y₁) mod p
x₃ = m² - 2x₁ mod p
y₃ = m(x₁ - x₃) - y₁ mod p
注意：在模运算中，除法需要通过乘以逆元来实现。
标量乘法：ECC的核心运算
标量乘法是指将椭圆曲线上的一个点P自加k次：
k×P = P + P + P + ... + P (k个P相加)
如果直接计算，需要进行k-1次点加法，当k很大时效率极低。实际应用中使用”倍加-相加”算法（Double-and-Add Algorithm）来优化。
倍加-相加算法
这个算法利用k的二进制表示来加速计算。算法思想如下：
将k表示为二进制：k = k₀ + k₁×2 + k₂×2² + … + kₙ×2ⁿ（其中kᵢ∈{0,1}）
则：k×P = k₀×P + k₁×(2P) + k₂×(4P) + … + kₙ×(2ⁿP)
算法流程：
输入：整数k，椭圆曲线上的点P
输出：k×P
1. 初始化 result = O（无穷远点）
2. 初始化 addend = P
3. while k > 0:
如果 k 的最低位为1：
result = result + addend
addend = addend + addend（点倍加）
k = k >> 1（右移一位）
4. 返回 result
复杂度分析：该算法的时间复杂度为O(log k)，相比朴素算法的O(k)有巨大提升。
举例：计算 25×P
- 25的二进制表示：11001
- 25 = 16 + 8 + 1 = 2⁴ + 2³ + 2⁰
- 25×P = 16×P + 8×P + 1×P
算法执行过程：
k=25(11001), result=O, addend=P
k&1=1 → result=O+P=P, addend=2P, k=12(1100)
k&1=0 → result=P, addend=4P, k=6(110)
k&1=0 → result=P, addend=8P, k=3(11)
k&1=1 → result=P+8P=9P, addend=16P, k=1(1)
k&1=1 → result=9P+16P=25P, k=0
ECC加密体系中的公私钥
椭圆曲线加密系统的密钥生成过程：
- 选择一条椭圆曲线E和曲线上的基点G
- 随机选择一个整数k作为私钥（1 < k < n，n为基点的阶）
- 计算公钥 K = k × G
安全性基础：椭圆曲线离散对数问题（ECDLP）
- 已知：基点G和公钥K
- 求解：私钥k，使得 K = k × G
- 困难性：目前没有高效的算法能在多项式时间内解决该问题
这种单向性保证了ECC的安全性：从私钥计算公钥很容易（多项式时间），但从公钥推导私钥在计算上不可行（指数时间）。
题目分析
问题建模
本题给出了完整的ECC参数：
椭圆曲线：y² = x³ + 16546484x + 4548674875 (mod 15424654874903)
基点：G = (6478678675, 5636379357093)
私钥：k = 546768
要求：计算公钥 K = k × G
解题思路
要解决这个问题，我们需要按照以下步骤：
- 实现模逆运算：用于计算点加法中的除法操作
- 实现点加法：包括普通加法和点倍加两种情况
- 实现标量乘法：使用倍加-相加算法高效计算k×G
- 计算公钥：运行标量乘法得到K(x, y)
- 计算flag：将公钥的x和y坐标相加
详细实现
第一步：模逆运算
在模运算中，除法 a/b mod p 等价于 a × b⁻¹ mod p，其中b⁻¹是b在模p下的乘法逆元。
我们使用扩展欧几里得算法（Extended Euclidean Algorithm）来计算模逆。
算法原理：
扩展欧几里得算法不仅能计算两个数的最大公约数gcd(a,b)，还能找到整数x和y，使得：
ax + by = gcd(a, b)
当gcd(k, p) = 1时（k和p互质），有：
kx + py = 1
两边对p取模：
kx ≡ 1 (mod p)
因此x就是k在模p下的乘法逆元。
代码实现：
def inverse_mod(k, p):
"""计算k在模p下的乘法逆元
返回值x满足：(k * x) % p == 1
要求：k ≠ 0，p为素数
"""
if k == 0:
raise ZeroDivisionError('division by zero')
if k < 0:
# k⁻¹ = p - (-k)⁻¹ (mod p)
return p - inverse_mod(-k, p)
# 扩展欧几里得算法
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = p, k
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
gcd, x, y = old_r, old_s, old_t
# 验证结果
assert gcd == 1, "k和p必须互质"
assert (k * x) % p == 1, "逆元计算错误"
return x % p
算法步骤详解：
初始化：
- s=0, old_s=1（用于计算x）
- t=1, old_t=0（用于计算y）
- r=p, old_r=k（辗转相除的两个数）
循环过程（以k=7, p=26为例）：
迭代1: quotient=26//7=3
old_r,r = 7, 26-3*7=5
old_s,s = 0, 1-3*0=1
old_t,t = 1, 0-3*1=-3
迭代2: quotient=7//5=1
old_r,r = 5, 7-1*5=2
old_s,s = 1, 0-1*1=-1
old_t,t = -3, 1-1*(-3)=4
迭代3: quotient=5//2=2
old_r,r = 2, 5-2*2=1
old_s,s = -1, 1-2*(-1)=3
old_t,t = 4, -3-2*4=-11
迭代4: quotient=2//1=2
old_r,r = 1, 2-2*1=0
(循环结束)
结果：gcd=1, x=3, y=-11
验证：7*3 + 26*(-11) = 21 - 286 = -265 = 1 - 10*26 ≡ 1 (mod 26)
因此 7⁻¹ ≡ 3 (mod 26)
第二步：椭圆曲线点运算
验证点是否在曲线上
def is_on_curve(point):
"""判断点是否在椭圆曲线上
验证点是否满足：y² ≡ x³ + ax + b (mod p)
"""
if point is None:
# None代表无穷远点（椭圆曲线群的单位元）
return True
x, y = point
return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0
点的取反
def point_neg(point):
"""计算点的相反数
点P(x,y)的相反数为-P(x,-y)
"""
assert is_on_curve(point)
if point is None:
return None
x, y = point
result = (x, -y % curve.p)
assert is_on_curve(result)
return result
点加法实现
def point_add(point1, point2):
"""椭圆曲线点加法
计算 point1 + point2
"""
assert is_on_curve(point1)
assert is_on_curve(point2)
# 处理无穷远点（加法单位元）
if point1 is None:
# O + Q = Q
return point2
if point2 is None:
# P + O = P
return point1
x1, y1 = point1
x2, y2 = point2
# 如果两点x坐标相同但y坐标相反，则相加结果为无穷远点
if x1 == x2 and y1 != y2:
# P + (-P) = O
return None
# 计算斜率m
if x1 == x2:
# 点倍加情况：P + P = 2P
# m = (3x₁² + a) / (2y₁) mod p
m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
else:
# 普通点加法：P + Q
# m = (y₂ - y₁) / (x₂ - x₁) mod p
m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)
# 计算结果点的坐标
# x₃ = m² - x₁ - x₂ mod p
# y₃ = m(x₁ - x₃) - y₁ mod p
x3 = m * m - x1 - x2
y3 = y1 + m * (x3 - x1)
result = (x3 % curve.p, -y3 % curve.p)
# 验证结果点在曲线上
assert is_on_curve(result)
return result
代码关键点说明：
- 边界情况处理：无穷远点、相反点
- 斜率计算：区分点倍加和普通加法
- 模运算：所有运算都在模p意义下进行
- 除法实现：通过乘以模逆来实现
第三步：标量乘法（核心）
def scalar_mult(k, point):
"""标量乘法：计算 k × point
使用倍加-相加算法（Double-and-Add）
时间复杂度：O(log k)
"""
assert is_on_curve(point)
if k < 0:
# k × P = (-k) × (-P)
return scalar_mult(-k, point_neg(point))
result = None # 初始化为无穷远点（加法单位元）
addend = point # 当前待加的点（初始为P）
# 从k的最低位开始遍历其二进制表示
while k:
if k & 1:
# 当前位为1，将对应的点加到结果中
result = point_add(result, addend)
# 点倍加：为下一位准备2倍的点
addend = point_add(addend, addend)
# k右移一位，处理下一个二进制位
k >>= 1
assert is_on_curve(result)
return result
算法执行过程示例（计算546768 × G）：
546768的二进制表示：10000101011101110000
初始：result = O, addend = G, k = 546768
循环第1次 (k的第0位=0):
k&1=0，不加
addend = 2G
k = 273384
循环第2次 (k的第1位=0):
k&1=0，不加
addend = 4G
k = 136692
循环第3次 (k的第2位=0):
k&1=0，不加
addend = 8G
k = 68346
循环第4次 (k的第3位=0):
k&1=0，不加
addend = 16G
k = 34173
循环第5次 (k的第4位=1):
k&1=1，result = O + 16G = 16G
addend = 32G
k = 17086
...（继续处理剩余位）
最终：result = 546768 × G
第四步：计算公钥
将所有函数组合起来，计算公钥：
import collections
# 定义椭圆曲线参数结构
EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')
# 根据题目创建椭圆曲线
curve = EllipticCurve(
'secp256k1',
p=15424654874903, # 有限域的模数
a=16546484, # 曲线参数a
b=4548674875, # 曲线参数b
g=(6478678675, 5636379357093), # 基点G
n=546768, # 私钥k（这里存储在n字段）
h=1, # 辅因子
)
def make_keypair():
"""生成密钥对"""
private_key = curve.n # 私钥k
public_key = scalar_mult(private_key, curve.g) # 公钥K = k × G
return private_key, public_key
# 计算密钥对
private_key, public_key = make_keypair()
print("私钥k:", hex(private_key))
print("公钥K: (0x{:x}, 0x{:x})".format(*public_key))
print(f"公钥K: ({public_key[0]}, {public_key[1]})")
第五步：计算flag
根据题目要求，flag为公钥的x坐标和y坐标之和：
flag = public_key[0] + public_key[1]
print(f"\nFlag = x + y = {public_key[0]} + {public_key[1]} = {flag}")
运行结果
执行完整的求解脚本，输出如下：
============================================================
题目参数:
p = 15424654874903
a = 16546484
b = 4548674875
G = (6478678675, 5636379357093)
私钥 k = 546768
============================================================
计算结果:
private key: 0x857d0
public key: (0xcb19fe553fa, 0x50545408eb4)
public key: (13957031351290, 5520194834100)
============================================================
Flag = x + y = 13957031351290 + 5520194834100 = 19477226185390
============================================================
验证公钥是否在曲线上：
x, y = 13957031351290, 5520194834100
p = 15424654874903
a = 16546484
b = 4548674875
left = (y * y) % p
right = (x * x * x + a * x + b) % p
print(f"y² mod p = {left}")
print(f"x³ + ax + b mod p = {right}")
print(f"点在曲线上: {left == right}")
输出：
y² mod p = 11249848836496
x³ + ax + b mod p = 11249848836496
点在曲线上: True
答案
Flag: 19477226185390
技术总结
ECC的核心技术点
- 有限域运算
- 模运算：所有计算都在模p意义下进行
- 模逆运算：使用扩展欧几里得算法，复杂度O(log p)
- 椭圆曲线点运算
- 点加法：通过斜率公式计算，需要模逆运算
- 点倍加：点加法的特殊情况
- 无穷远点：椭圆曲线群的单位元
- 标量乘法优化
- 朴素算法：O(k)，对大数不可行
- 倍加-相加算法：O(log k)，实用高效
- 二进制位扫描：从低位到高位或从高位到低位
- 安全性基础
- 正向计算容易：K = k × G 可快速计算
- 逆向求解困难：已知K和G求k是ECDLP问题
- 参数选择重要：曲线参数、基点阶数影响安全性
ECC相比RSA的优势
- 密钥长度更短
- 256位ECC ≈ 3072位RSA（相同安全级别）
- 节省存储空间和传输带宽
- 计算效率更高
- 密钥生成更快
- 签名和验证速度更快
- 资源消耗更小
- 适合移动设备、IoT设备
- 功耗更低
实际应用场景
- 数字签名
- ECDSA（椭圆曲线数字签名算法）
- 比特币、以太坊等区块链系统
- 密钥交换
- ECDH（椭圆曲线Diffie-Hellman）
- TLS/SSL中的密钥协商
- 加密通信
- 端到端加密
- VPN、安全即时通讯
- 身份认证
- 智能卡、USB令牌
- 移动支付认证
常见攻击与防护
- 弱曲线攻击
- 问题：某些曲线参数存在数学弱点
- 防护：使用标准曲线（如NIST P-256、secp256k1）
- 小阶数攻击
- 问题：基点阶数过小，私钥空间不足
- 防护：确保基点阶数足够大（通常≥2²⁵⁶）
- 侧信道攻击
- 问题：通过时间、功耗分析泄露私钥
- 防护：使用常数时间算法、添加随机化
- 中间人攻击
- 问题：公钥传输过程被篡改
- 防护：使用数字证书、PKI基础设施
解题思路总结
解决ECC类型的CTF题目，通常有以下几种类型：
类型1：已知私钥求公钥（本题）
- 直接实现标量乘法即可
- 难度：基础
- 考察：ECC基本原理和编程实现
类型2：已知公钥求私钥
-
需要解决ECDLP问题
-
通常利用题目中的弱点：
-
小阶数：暴力搜索或Baby-step Giant-step算法
-
弱曲线：Smart’s attack、MOV attack等
-
参数泄露：利用随机数重用、格攻击等
-
难度：中等到困难
类型3：椭圆曲线签名伪造
-
利用签名算法的漏洞
-
常见漏洞：
-
随机数k重用
-
k值可预测
-
参数选择不当
-
难度：中等
类型4：ECC实现漏洞
-
利用代码实现中的错误
-
常见问题：
-
点加法实现错误
-
无效曲线攻击
-
时序攻击
-
难度：中等到困难
进阶学习路径
如果想深入学习椭圆曲线密码学，建议按以下路径：
数学基础
- 抽象代数
- 群、环、域的概念
- 有限域理论
- 群的阶和循环群
- 数论基础
- 模运算
- 中国剩余定理
- 二次剩余
- 椭圆曲线理论
- 曲线的几何性质
- 点群的结构
- Hasse定理
密码学应用
- ECDSA（椭圆曲线数字签名）
- 签名生成和验证
- 常见攻击方法
- ECDH（椭圆曲线密钥交换）
- 密钥协商协议
- 前向安全性
- 其他应用
- EdDSA（Edwards曲线签名）
- ECIES（椭圆曲线集成加密）
攻击技术
- 理论攻击
- Pollard’s rho算法
- Baby-step Giant-step算法
- Pohlig-Hellman算法
- 实现攻击
- 时序攻击
- 功耗分析
- 故障注入
- 协议攻击
- 随机数攻击
- 无效曲线攻击
- 扭曲攻击
工具和库
- SageMath：强大的数学计算工具，内置椭圆曲线支持
- OpenSSL：工业级密码库
- Python库：ecdsa、cryptography、pycryptodome
- CTF工具：msieve、CADO-NFS等
完整求解代码
以下是完整的Python求解脚本：
import collections
# 定义椭圆曲线参数
EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h')
curve = EllipticCurve(
'secp256k1',
p=15424654874903,
a=16546484,
b=4548674875,
g=(6478678675, 5636379357093),
n=546768,
h=1,
)
def inverse_mod(k, p):
"""计算模逆"""
if k == 0:
raise ZeroDivisionError('division by zero')
if k < 0:
return p - inverse_mod(-k, p)
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = p, k
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
gcd, x, y = old_r, old_s, old_t
assert gcd == 1
assert (k * x) % p == 1
return x % p
def is_on_curve(point):
"""判断点是否在曲线上"""
if point is None:
return True
x, y = point
return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0
def point_neg(point):
"""点取反"""
assert is_on_curve(point)
if point is None:
return None
x, y = point
result = (x, -y % curve.p)
assert is_on_curve(result)
return result
def point_add(point1, point2):
"""点加法"""
assert is_on_curve(point1)
assert is_on_curve(point2)
if point1 is None:
return point2
if point2 is None:
return point1
x1, y1 = point1
x2, y2 = point2
if x1 == x2 and y1 != y2:
return None
if x1 == x2:
m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p)
else:
m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)
x3 = m * m - x1 - x2
y3 = y1 + m * (x3 - x1)
result = (x3 % curve.p, -y3 % curve.p)
assert is_on_curve(result)
return result
def scalar_mult(k, point):
"""标量乘法"""
assert is_on_curve(point)
if k < 0:
return scalar_mult(-k, point_neg(point))
result = None
addend = point
while k:
if k & 1:
result = point_add(result, addend)
addend = point_add(addend, addend)
k >>= 1
assert is_on_curve(result)
return result
def make_keypair():
"""生成密钥对"""
private_key = curve.n
public_key = scalar_mult(private_key, curve.g)
return private_key, public_key
# 计算并输出结果
print("="*60)
print("题目参数:")
print(f"p = {curve.p}")
print(f"a = {curve.a}")
print(f"b = {curve.b}")
print(f"G = {curve.g}")
print(f"私钥 k = {curve.n}")
print("="*60)
private_key, public_key = make_keypair()
print("\n计算结果:")
print("private key:", hex(private_key))
print("public key: (0x{:x}, 0x{:x})".format(*public_key))
print(f"public key: ({public_key[0]}, {public_key[1]})")
flag = public_key[0] + public_key[1]
print("\n" + "="*60)
print(f"Flag = x + y = {public_key[0]} + {public_key[1]} = {flag}")
print("="*60)
通过这道题，我们系统地学习了椭圆曲线密码学的基本原理和实现方法。掌握这些知识不仅能帮助我们解决类似的CTF题目，也为理解现代密码学应用打下了坚实基础。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全 破镜安全《CTF密码学实战：椭圆曲线加密（ECC）原理与解题》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论